Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
The Euclidean algorithm computes in steps, no factoring required, and it's one of the oldest non-trivial algorithms ever recorded — Euclid wrote it down around 300 BC. It matters now because every modern public-key crypto system (RSA, ECDSA, EdDSA, Diffie-Hellman) needs gcds and modular inverses on huge integers, and the only reason that's tractable is this algorithm. The trick is the identity , which collapses the problem into a tail-recursive shrinking sequence. Once you've internalized why that identity is true, you've also internalized the central move of computational number theory: replace integers with their remainders, repeatedly, until the answer is staring at you.
The Euclidean algorithm repeatedly applies the identity , terminating when the second argument becomes 0. At that point is the answer. Why is the identity true? Any common divisor of and also divides , and vice versa, so the set of common divisors of equals the set of common divisors of — and therefore the element of those sets is the same.
gcd_trace output.gcd_trace(2024, 748) and count how many steps it takes. Predict the count for gcd_trace(2 * 2024, 2 * 748) before running — should be the same number of steps, since scaling by 2 doesn't change the algorithm's structure.gcd_trace(89, 55) and observe that every quotient is 1. Lamé's theorem says this is the slowest input shape — the number of steps is bounded by .Use these three in order. Each builds on the one before.
In one paragraph, explain the Euclidean algorithm to someone who has never seen it, using a concrete numerical example (e.g. $\gcd(48, 18)$). Why does each step preserve the gcd?
Walk me step by step through the proof that $\gcd(a, b) = \gcd(b, a \bmod b)$. The key claim is that the *set* of common divisors of $(a, b)$ equals the set of common divisors of $(b, a \bmod b)$ — show both inclusions.
Lamé's theorem says the Euclidean algorithm on $(a, b)$ takes at most $5 \log_{10} \min(a, b)$ steps, with the worst case being consecutive Fibonacci numbers. Sketch why Fibonacci numbers are the worst case, and what that tells us about the time complexity of gcd on $n$-bit integers.
gcd_rec(a, b) = a if b == 0 else gcd_rec(b, a % b) and verify it gives the same answer as the iterative version on 10 random pairs.// main.go
package main
import (
"fmt"
)
func gcd(a, b int) int {
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
for b != 0 {
a, b = b, a%b
}
return a
}
// Trace gcd(1071, 462)
func gcdTrace(a, b int) int {
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
for b != 0 {
q, r := a/b, a%b
fmt.Printf("%d = %d*%d + %d\n", a, b, q, r)
a, b = b, r
}
return a
}
func main() {
fmt.Println("gcd =", gcdTrace(1071, 462))
// 1071 = 462*2 + 147
// 462 = 147*3 + 21
// 147 = 21*7 + 0
// gcd = 21
}
go run main.go