The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm
We give rigorous definitions and properties of gcd and lcm, then prove the correctness and O(log min(a,b)) complexity of the Euclidean algorithm. We establish Bezout's identity, develop the extended Euclidean algorithm, and systematically solve linear congruences ax = b (mod n).
1 Greatest Common Divisor and Least Common Multiple
Definition 1 (Greatest common divisor).
For integers , not both zero, the greatest common divisor of and is the largest positive integer satisfying and . We write . When , we say and are coprime.
Definition 2 (Least common multiple).
For positive integers , the least common multiple is the smallest positive integer satisfying and . We write .
Theorem 3.
For positive integers , we have .
Proof.
Set and write , with . It suffices to show that . Clearly and . Now let be any positive integer with and . Write . Then , so . Since , we obtain , and therefore . Hence . □
2 The Euclidean Algorithm
Theorem 4 (Correctness of the Euclidean algorithm).
For positive integers , write with by the division algorithm. Then .
Proof.
If and , then . Conversely, if and , then . Thus the sets of common divisors of and coincide, and in particular their maxima agree. □
Remark 5.
Applying this theorem repeatedly yields , with the remainders strictly decreasing until we reach . This is the Euclidean algorithm.
Theorem 6 (Complexity).
The Euclidean algorithm terminates in iterations.
Proof.
In the step , we have ; in fact, one can show . If , then . If , then and . Therefore the remainder is at least halved every two iterations, giving total steps. □
3 Bézout's Identity
Theorem 7 (B\'ezout's identity).
For integers , not both zero, there exist integers such that .
Proof.
Consider the set . Since (for instance, belongs to for a suitable combination), the well-ordering principle furnishes a least element . We claim . By the division algorithm, with . Then lies in . Since and is the least element of , we must have , so . Similarly , so is a common divisor. Conversely, if and , then , which forces . □
4 The Extended Euclidean Algorithm
The extended Euclidean algorithm computes, alongside , the Bé satisfying .
Example 8.
Compute : , , , . Hence . Back-substituting: .
5 Solving Linear Congruences
Theorem 9.
The congruence has a solution if and only if . When solutions exist, there are exactly solutions modulo .
Proof.
The congruence is equivalent to the existence of integers with . By Bé, so lies in this set precisely when . When , the reduced congruence has and therefore a unique solution . The solutions of the original congruence are for , giving solutions in all. □
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 followers·105 articles