The Euclidean algorithm

The following result has been known for thousands of years. The method is named for the Greek mathematician Euclid who decribed it in book 7 of this ``Elements'', written about 2300 years ago. For more details on his life, see the award-winning web site [MacOR].

Theorem 1.4.3 (``Euclidean algorithm'')   Let $a>0$ and $b>0$ be integers. Then

$$\{ma+nb\ \vert\ m,n \in \mathbb{Z}\}=gcd(a,b)\mathbb{Z}.$$

Furthermore, there are integers $x,y$ such that $ax+by=gcd(a,b)$.

proof 1: We first show that there are integers $x,y$ such that $ax+by=gcd(a,b)$.

Let $S$ be the set of all positive integers of the form $sa+tb$, where $s$ and $t$ are integers. Since $S$ is not empty, it has a smallest element by the well-ordering principle. Let $d=xa+yb$ be the smallest element of $S$. The division algorithm (theorem 1.2.7) tells us that there are integers $q$ and $r$ satisfying $a=dq+r$ and $0\leq r<d$. But $r=a-dq=(1-qx)a+(-qy)b$ is in $S$, contradicting our choice of $d$ as the smallest element of $S$. Therefore, $r=0$ and $a=dq$ is divisible by $d$. Similarly, $d \mid b$, and so it is a common divisor of $a$ and $b$. If $c$ is another common divisor of $a$ and $b$, then $c\mid d=xa+yb$, so $c<d$ and this implies $d=gcd(a,b)$.

For the proof of the first statement of the theorem, see the proof below. $\Box$

proof 2: We can (and do) assume without loss of generality that $0<b<a$. First we show that there are integers $x,y$ such that $ax+by=gcd(a,b)$. The proof of this is constructive and follows an algorithm called the Euclidean algorithm.

Let $r_{-1}=a$ and $r_0=b$. Let $i=0$.

(1)

Use the division algorithm (theorem 1.2.7) to compute integers $q_{i+1}$ and $0\leq r_{i+1}<r_i$ such that

$$r_{i-1}=r_iq_{i+1}+r_{i+1}.$$

(2)

If $r_{i+1}\not= 0$ then increment $i$ and go to step 1. If $r_{i+1}=0$ then stop.

Since $0\leq ...<r_1<r_0=b<r_{-1}=a$, at some point the above algorithm must terminate. Suppose that $r_k=0$ and $k$ is the smallest such integer.

Claim: $gcd(a,b)=r_{k-1}$.

To see that, we first show that $r_{k-1}=ax+by$ for some integers $x,y$. Indeed, we claim that every $r_i$ ( $-1\leq i <k$) is a integral linear combination of $a,b$. This may be proven by mathematical induction. (The details are left to the reader as an exercise. The cases $i=-1,0,1,2$ follow from $a=bq_{1}+r_{1}$, $b=r_1q_{2}+r_{2}$.) Thus $r_{k-1}=ax+by$. The fact $r_{k-1}=ax+by$ implies $gcd(a,b)\vert r_{k-1}$.

Next, to finish the proof of the above claim, we show that $r_{k-1}\vert a$ and $r_{k-1}\vert b$. Indeed, we claim that $r_{k-1}$ divides every $r_i$ ( $-1\leq i <k$) (The details are left to the reader as an exercise. The cases $i=k-1,k-2,k-3$ follow from $r_{k-3}=r_{k-2}q_{k-1}+r_{k-1}$, $r_{k-2}=r_{k-1}q_{k}$.) The fact $r_{k-1}\vert a,r_{k-1}\vert b$ implies $r_{k-1}\vert gcd(a,b)$.

The claim follows.

It remains to prove

$$\{ma+nb\ \vert\ m,n \in \mathbb{Z}\}=gcd(a,b)\mathbb{Z}.$$

The previous paragraphs of this proof show that

$$gcd(a,b)\mathbb{Z}\subset \{ma+nb\ \vert\ m,n \in \mathbb{Z}\}.$$

For any integers $m,n$ we note $gcd(a,b)\vert(ma+nb)$, so

$$\{ma+nb\ \vert\ m,n \in \mathbb{Z}\}\subset gcd(a,b)\mathbb{Z}.$$

This implies the equality above, and completes the proof of the theorem. $\Box$