1st Course for high Diploma, Number Theory Lecture 3: The Euclidean Algorithm

2.1 The Euclidean algorithm
The Euclidean algorithm can be described as follows:
Theorem 2.1.1 (The Euclidean algorithm). Let a and b be two integers whose greatest common divisor is desired. Because gcd(|a|,|b|) = gcd(a,b), with a ? b > 0. The ?rst step is to apply the division algorithm to a and b to get
a =q1b+r1, 0? r1 < b.
If it happens that r1 =0, then b|a and gcd(a,b)=b.
When r ? 0, divide b by r1 to produce integers q2 and r2 satisfying b =q2 r1 + r2, 0? r2 < r1. If r2 =0, then we stop; otherwise, proceed as before to obtain r1 =q3r2 +r3, 0? r3 < r2 This division process continues until some zero remainder appears, say, at the (n+1)th stage where rn?1 is divided by rn (a zero remainder occurs sooner or later because the decreasing sequence b > r1 > r2 > ···?0 cannot contain more than b integers). The result is the following system of equations:
a =q1b+ r1, 0 < r1 < b
b =q2 r1 + r2, 0 < r2 < r1
r1 =q3r2 + r3 0 < r3 < r2
. . .
rn?2 =qn rn?1 + rn, 0 < rn < rn?1
rn?1 =qn+1 rn + 0.
With rn, the last nonzero remainder that appears in this manner, is equal to gcd(a,b).
This proof is based on the following lemma:
Lemma 2.1.1. If a =qb+r, then gcd(a,b)=gcd(b,r).
Proof. If d =gcd(a,b), then the relations d|a and d|b together imply that d|(a?qb), or d|r. Thus, d is a common divisor of both b and r. On the other hand, if c is an arbitrary common divisor of b and r, then c|(qb+r), whence c|a. This makes c a common divisor of a and b, so that c ?d. It now follows from the de?nition of gcd(b,r) that d =gcd(b,r).
Using the result of this lemma, we simply work down the displayed system of equations, obtaining
gcd(a,b)=gcd(b, r1)=···=gcd(rn?1, rn)=gcd(rn,0)= rn.