Bezout's Equation and The GCD

For integers $a,b$ consider the linear form $ax + by$. It takes on all multiples of $a$, all multiples of $b$ and all sums and differences of those numbers. Notice that when $a,b$ have a common factor (e.g. they are both even) then every value the linear form takes on will also be a multiple of that common factor.

It turns out that the smallest positive value this form takes on is the greatest common divisor of $a$ and $b$. The best way to see this is along with the algorithm to compute it. In fact we'll present an algorithm to compute $x,y,(a,b)$ (the notation $(a,b)$ denotes the gcd of the two numbers) in $ax + by = (a,b)$

Combining linear equations

Starting with

$a \cdot 1 + b \cdot 0 = a$ $a \cdot 0 + b \cdot 1 = b$

then, supposing $a > b$ we can get represent a smaller number $c = a - b$ with this form by subtracting so that we now have:

$a \cdot 0 + b \cdot 1 = b$ $a \cdot 1 + b \cdot (-1) = c$

continuing in this way you find the integers $x,y$ that produce the minimum positive value.

Example

Here's an example of running this procedure for the form $6x + 4y$, to be more compact I'll write the equations as a table of numbers.

$\begin{pmatrix} 1 & 0 & 6 \\ 0 & 1 & 4 \end{pmatrix}$ $\begin{pmatrix} 1 & -1 & 2 \\ 0 & 1 & 4 \end{pmatrix}$ $\begin{pmatrix} 1 & -1 & 2 \\ -1 & 2 & 2 \end{pmatrix}$ $\begin{pmatrix} 1 & -1 & 2 \\ -2 & 3 & 0 \end{pmatrix}$

Upon reaching 0 the algorithm is complete, and the result is that $(6,4) = 2$ and $6 \cdot 1 + 5 \cdot (-1) = 4$

Proof

There are two facts which are used to justify the correctness of algorithm.

Lemma 1: $(a,0) = a$.

Lemma 2: $a > b$ implies $(a,b) = (a-b,b)$.