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

$\displaystyle \{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

$\displaystyle 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

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

The previous paragraphs of this proof show that

$\displaystyle 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

$\displaystyle \{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$


David Joyner 2007-09-03