The Euclidean Algorithm

Number Theory · Axiom Academy

LESSON The Euclidean Algorithm An efficient method for computing the greatest common divisor of two integers The foundation of the Euclidean Algorithm is a simple but powerful observation about how the gcd behaves under the division algorithm. For any integers a and b with b > 0: In other words, the gcd of a and b equals the gcd of b and the remainder when a is divided by b. This lemma tells us that we can replace a larger problem with a smaller one without changing the answer. Let's prove why gcd(a,b) = gcd(b, a mod b). We'll use the division algorithm and properties of divisibility. Step 1: By the division algorithm, we can write: Step 2: Let d = gcd(a,b). Then d divides both a and b, so d divides any linear combination of a and b. In particular: Step 3: So d divides both b and r, which means d divides gcd(b,r). Step 4: Conversely, let e = gcd(b,r). Then e divides both b and r, so: Conclusion: Since d divides e and e divides d, we have d = e, so gcd(a,b) = gcd(b,r). Now we can describe the algorithm itself. The key lemma tells us we can repeatedly reduce the problem size. Input: Two positive integers a and b Otherwise, compute r = a mod b Why does it terminate? Each iteration replaces b with r = a mod b. By the division algorithm, 0 r < b, so the second value strictly decreases at each step. Eventually, we must reach r = 0. Why is it correct? By the key lemma, each replacement preserves the gcd. When we reach (d, 0), we have gcd(d, 0) = d, giving us the answer.

This is the written version of the interactive lesson above. See the full Number Theory course.