Prove the Euclidean Algorithm

本文将故意采用同余符号（\(a\equiv c\pmod b\)），让本文看起来酷炫一点。

When a and b are integers and \(b \neq 0\) we say “a divides b”, and write \(a|b\). In other words, b/a is an integer.

Treat “b/a is an integer” literally, do not have to consider its English meaning. This phrase is used when proving Lemma D.

Lemmas

Obvious in common sense. Proof omitted.

Proof: a|a (it’s ok because a>0), and a|b, so we have gcd(a,b)=a.

Because of Lemma B.

Proof:

Due to a|b, we have “b/a is an integer”. Due to a|c, we have “c/a is an integer”. Then “(b/a + c/a) is an integer”.

Since x and y are integers, “\(\frac{b}{a}x + \frac{c}{a}y\) is an integer”. That is, “\(\frac{bx+cy}{a} \) is an integer”. That is a|(bx+cy).

Proof:

Employ a temporary notion divisors(a,b), which returns a set of all divisors of b and a. \(\mathrm{gcd}(a,b) \in \mathrm{divisors}(a,b)\). gcd(a,b), by definition, is the greatest element in divisors(a,b).

Let \(m \in \mathrm{divisors}(a,b)\), then we have m|b, m|a.

Leave the right-hand side gcd(c,b) for a while, let’s work on the assumption that \(a\equiv c\pmod b\).

Recall the definition of congurence. If and only if we have a-c=bk (a,b,c,k are all integers), then we cay say \(a\equiv c\pmod b \), we can also say \(a\equiv c\pmod k \).

The assumption says \(a\equiv c\pmod b\), so we know a-c=bk, and also c=a-bk.

We already know m|b, m|a, then, due to Lemma D, we get m|(a-bk) which is m|c.

Since we know m|c and m|b, we get \(m \in \mathrm{divisors}(c,b)\). m could be any element in the set, and m of course can be the greatest element, i.e., gcd. Therefore we get gcd(a,b)=gcd(c,b).

Constructing the Euclidean Algorithm

Now let use use Lemma A, B, C, and E to construct the Euclidean Algorithm for finding the greatest common divisor.

gcd(a,b)

if a=b, gcd(a,b)=a=b. For other cases of gcd(a,b), let’s assume a>b (with the help of Lemma A).

Due the assumption that a>b, we can always find an integer \(q_1\) such that \(a=bq_1+r_1\) and \(0 \leqslant r_1<b\). (If a and b are close such as 5 and 3, \(q_1\) could be 1, which is totally fine.)

From \(a=bq_1+r_1\), we get \(a-r_1=bq_1\), then by the definition of congurence get \(a \equiv r_1 \pmod b\). To compute gcd(a,b), with the help of Lemma E it’s ok to compute \(\mathrm{gcd}(r_1,b)\) instead.

gcd(a,b)=\(\mathrm{gcd}(r_1,b)\)

From \(\mathrm{gcd}(r_1,b)\) where \(a>b>r_1\), we can always find an integer \(q_2\) such that \(b=r_1q_2+r_2\) where \( 0\leqslant r_2<r_1\).

Similarly, from \(b=r_1q_2+r_2\), we get \(b-r_2=r_1q_2\), then by the definition of congurence get \(b \equiv r_2 \pmod{r_1}\). To compute \(\mathrm{gcd}(r_1,b)\), with the help of Lemma E it’s ok to compute \(\mathrm{gcd}(r_2, r_1)\) instead.

gcd(a,b)=\(\mathrm{gcd}(r_1,b)=\mathrm{gcd}(r_1,r_2)\)

To compute \(\mathrm{gcd}(r_1,r_2)\), we do the same operation, and after some iterations we get \(\mathrm{gcd}(r_1,r_2)=\cdots=\mathrm{gcd}(r_n,r_{n+1})\). Notice the requirement that \(a>b>r_1>r_2>\cdots>r_n>r_{n+1}\geqslant 0 \).

We can’t iterate infinite times because \(r_{n+1}\) eventually becomes 0. Then \(\mathrm{gcd}(a,b)=\cdots=\mathrm{gcd}(r_n,r_{n+1})=\mathrm{gcd}(r_n,0)=r_n\), due to Lemma C.

The termination property of the Euclidean Algorithm is also proved.

References

1. Samuel Wagstaff. Proof that the Euclidean Algorithm Works. . [2024-05-26]. (archived on 2022-11-06)
2. Patrick Keef and David Guichard. 3.3 The Euclidean Algorithm. Whitman College. 2023-05-13 [2024-05-26].