Greatest Common Divsor And Linear Diophantine Equations

This notebook explores how to compute greatest common divisors and solve linear diophantine equations in the integers.

Algorithms For Finding The GCD

Listing All Divisors

To find the greatest common divisor (GCD) of two numbers, one naive method is to list all divisors of each number and find the largest common divisor. For example:

Prime Factorizations

Another naive method is to find the prime factorizations of the two numbers. For example:

The gcd is computed as $2^2\cdot 3 = 12$.

The Euclidean Algorithm

The Euclidean algorithm is another method for finding the GCD. It is based on the principle that the GCD of two numbers also divides their difference. The algorithm can be described as follows:

1. Divide the larger number by the smaller number and take the remainder.
2. Replace the larger number with the smaller number and the smaller number with the remainder.
3. Repeat until the remainder is zero. The last non-zero remainder is the GCD.

Example

Find the GCD of 48 and 20 using the Euclidean algorithm.

We apply the division algorithm repeatedly:

$$48 = 20 \cdot 2 + 8$$ $$20 = 8 \cdot 2 + 4$$ $$8 = 4 \cdot 2 + 0$$

The last non-zero remainder is $4$, so $\gcd(48, 20) = 4$.

Comparing Runtime: Factorization vs Euclidean Algorithm

When we have large integers, it can take quite a while to factor them.

However, we can still find the gcd efficiently!

Linear Diophantine Equations

A linear Diophantine equation is an equation of the form: $$ax + by = d$$ where $a, b, d$ are integers and we seek integer solutions for $x$ and $y$.

A fundamental result is that this equation has integer solutions if and only if $\gcd(a, b)$ divides $d$.

The Extended Euclidean Algorithm

When we use the Euclidean algorithm to find $\gcd(a, b)$, we can back substitute to express the GCD as a linear combination of $a$ and $b$. This process allows us to solve linear Diophantine equations.

Example: Solving $13x + 17y = 1$

First, we apply the Euclidean algorithm to find $\gcd(13, 17)$:

$$17 = 13 \cdot 1 + 4$$ $$13 = 4 \cdot 3 + 1$$ $$4 = 1 \cdot 4 + 0$$

The GCD is $1$, which divides $1$, so the equation has integer solutions.

Now we back substitute to express $1$ as a linear combination of $13$ and $17$:

From the second equation: $$1 = 13 - 4 \cdot 3$$ Substitute $4 = 17 - 13 \cdot 1$ from the first equation: $$1 = 13 - (17 - 13 \cdot 1) \cdot 3$$ $$1 = 13 - 17 \cdot 3 + 13 \cdot 3$$ $$1 = 13 \cdot 4 + 17 \cdot (-3)$$

Therefore, one solution is $x = 4$ and $y = -3$.

We can verify: $13(4) + 17(-3) = 52 - 51 = 1$ ✓

General Solutions

Once we have one particular solution $(x_0, y_0)$ to $ax + by = d$, we can find all solutions using:

$$x = x_0 + \frac{b}{\gcd(a,b)} \cdot t$$ $$y = y_0 - \frac{a}{\gcd(a,b)} \cdot t$$

where $t$ is any integer.

Exercise

Prove that every solution to the linear Diophantine equation $ax + by = d$ is of the form:

$$x = x_0 + \frac{b}{\gcd(a,b)} \cdot t$$ $$y = y_0 - \frac{a}{\gcd(a,b)} \cdot t$$

where $(x_0, y_0)$ is a particular solution and $t$ is any integer.

Hint: If $(x_1, y_1)$ is another solution, consider $a(x_1 - x_0) + b(y_1 - y_0)$ and what this equals.

Practice Problem

1. Solve $84x + 33y = 12$. Then use the following SageCell to verify your answer.

1. Pick several different random values of $a,b,d$ and solve the diophantine equation

$$ ax + by = d$$ Verify your answer in Sage.