Stage 37 · Beyond (Optional)

37.3.3 Greatest Common Divisor and the Euclidean Algorithm

37.3 First Steps in Number Theory: Divisibility, Congruence, and Primes

Point 3 of 5

37.3.3 Greatest Common Divisor and the Euclidean Algorithm

Core idea

Keep dividing the larger number by the smaller and taking the remainder until it hits zero, and you've found gcd(a, b).

Module goal. Starting from divisibility and remainders among the integers, meet the prime numbers as building blocks and congruence as a clock arithmetic, and feel the beauty of pure structure.

eastmath.com · 37.3 First Steps in Number Theory: Divisibility, Congruence, and Primes · 37.3.3 Greatest Common Divisor and the Euclidean Algorithm