The Euclidean algorithm

The following result has been known for thousands of years.

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$. Now $r=a-dq=(1-x)a+(-y)b$ would be in $S$ if it were positive, which would contradict 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$

Theorem 1.4.4   The linear equation $ax+by=c$ has no solutions if $gcd(a,b)$ does not divide $c$. If $gcd(a,b)$ does divide $c$ then there are infinitely many solutions

$$x=r+\frac{b}{gcd(a,b)}t,\ \ \ x=s-\frac{a}{gcd(a,b)}t,$$

where $x=r,y=s$ is any solution and $t$ is any integer.

proof: First we prove the case when $gcd(a,b)=1$. We see from the previous theorem that the equation $ax+by=c$ does have a solution since $gcd(a,b)=1$. Let $x=x_0$, $y=y_0$ be any solution. Let $x=r$, $y=s$ be any other solution. We want to show that $r=x_0+bt$ and $y=y_0-at$. We have

$$0=c-c=ar+bs-(ax_0+by_0)=a(r-x_0)+b(s-y_0).$$

Therefore, $a$ divides $b(s-y_0)$. But $a$ and $b$ are relatively prime, so $a$ divides $s-y_0$. Therefore, there is a $t$ such that $at=y_0-s$. Then

$$0=a(r-x_0)+bat.$$

This implies $r=x_0+bt$. This completes the proof in the case when $gcd(a,b)=1$.

The general case follows easily from this special case. It is left to the reader as an exercise. $\Box$