The Euclidean Algorithm computes greatest common divisors quickly, but also, with only slightly more work, yields a very useful fact: $gcd\left(a\text{,}b\right)$ can be expressed as a linear combination of $a$ and $b\text{.}$ That is, there exist integers $x$ and $y$ such that $gcd\left(a\text{,}b\right)=ax+by\text{.}$ For example,

The Extended Euclidean Algorithm will tell us how to find $x$ and $y\text{.}$ Rather than give a set of equations, we’ll show how it works with the two examples we calculated in Subsection 3.1.3.

When we computed $gcd\left(12345\text{,}11111\right)\text{,}$ we did the following calculation:

For the Extended Euclidean Algorithm, we’ll form a table with three columns and explain how they arise as we compute them.

We begin by forming two rows and three columns. The first entries in the rows are the original numbers we started with, namely 12345 and 11111. We will do some calculations so that we always have

where $x$ and $y$ are integers. The first two lines are trivial: $12345=1\cdot 12345+0\cdot 11111$ and $11111=0\cdot 12345+1\cdot 11111\text{:}$

The first line in our $gcd\left(12345\text{,}11111\right)$ calculation tells us that $12345=1\cdot 11111+1234\text{.}$ We rewrite this as $1234=12345-1\cdot 11111\text{.}$ Using this, we compute

yielding the following:

In effect, we have done the following subtraction:

Therefore, the last line tells us that $1234=12345\cdot 1+11111\cdot (-1)\text{.}$

We now move to the second row of our gcd calculation. This says that $11111=9\cdot 1234+5\text{,}$ which we rewrite as $5=11111-9\cdot 1234\text{.}$ This tells us to compute (2nd row) $-9\cdot$(3rd row). We write this as

The last line tells us that $5=12345\cdot (-9)+11111\cdot 10\text{.}$

The third row of our gcd calculation tells us that $4=1234-246\cdot 5\text{.}$ This becomes

Finally, we obtain

This tells us that $1=12345\cdot (-2224)+11111\cdot 2471\text{.}$

Notice that as we proceeded, we were doing the Euclidean Algorithm in the first column. The first entry of each row is a remainder from the gcd calculation, and the entries in the second and third columns allow us to express the number in the first column as a linear combination of 12345 and 11111. The quotients in the Euclidean Algorithm tell us what to multiply a row by before subtracting it from the previous row.

Let’s do another example using 482 and 1180 and our previous calculation that $gcd\left(1180\text{,}482\right)=2\text{:}$

The end result is $2=1180\cdot (-29)+482\cdot 71\text{.}$

To summarize, we state the following.

The property of primes stated in the corollary holds only for primes. For example, if we know a product $ab$ is divisible by 6, we cannot conclude that $a$ or $b$ is a multiple of 6. The problem is that $6=2\cdot 3\text{,}$ and the 2 could be in $a$ while the 3 could be in $b\text{,}$ as seen in the example $60=4\cdot 15\text{.}$ More generally, if $n=ab$ is any composite, then $n|ab$ but $n\nmid a$ and $n\nmid b\text{.}$ Therefore, the primes, and 1, are the only integers with the property of the corollary.