Euclidean Algorithm Examples

Number Theory · Axiom Academy

EXAMPLE Euclidean Algorithm Examples Master the step-by-step process of finding GCDs efficiently Excellent work! You've completed this example. Here's what we learned: Euclidean Algorithm Efficiency: The algorithm finds the GCD through repeated division, terminating when the remainder is zero. The last non-zero remainder is the GCD. Step Counting: The number of division steps varies based on the input. Consecutive Fibonacci numbers require the most steps (worst case), while numbers with large quotients terminate quickly. Verification with Prime Factorization: We can always verify our result using prime factorization - the GCD is the product of common prime factors with minimum exponents. General Pattern: At each step, we replace the pair (a, b) with (b, r) where r is the remainder when dividing a by b. This process always decreases the size of the numbers. Multiple Examples: We explored gcd(252, 105) = 21 in 4 steps, gcd(1071, 462) = 21 in 5 steps, and gcd(987, 610) (Fibonacci) in 8 steps, demonstrating different algorithm behaviors. The Euclidean Algorithm is one of the oldest and most efficient algorithms in mathematics. Practice with different pairs of numbers to develop intuition for when the algorithm terminates quickly!

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