GCD Summary

Number Theory · Axiom Academy

SUMMARY GCD and the Euclidean Algorithm Let's review the essential concepts from our exploration of greatest common divisors, the Euclidean algorithm, and their powerful applications. GCD (Greatest Common Divisor): The largest positive integer that divides both numbers with no remainder LCM (Least Common Multiple): The smallest positive integer that both numbers divide evenly into Relatively Prime: Two numbers are relatively prime when gcd(a,b) = 1, meaning they share no common factors except 1 Common Divisor: Any integer that divides both numbers; the GCD is the greatest among all common divisors Prime Factorization Method: Factor both numbers into primes, then take the minimum power of each common prime Euclidean Algorithm: Repeatedly divide and take remainders until reaching zero; the last non-zero remainder is the GCD Efficiency Comparison: Euclidean algorithm is much faster for large numbers and doesn't require finding prime factors Ancient Wisdom: The Euclidean algorithm dates back over 2,300 years and is one of the oldest algorithms still in use today Example: Euclidean Algorithm for gcd(252, 105) Step 1 - First Division: 252 = 105 × 2 + 42, so the remainder is 42 Step 2 - Continue: 105 = 42 × 2 + 21, so the new remainder is 21 Step 3 - Keep Going: 42 = 21 × 2 + 0, the remainder is now zero Step 4 - Conclude: The last non-zero remainder was 21, so gcd(252, 105) = 21. This process is guaranteed to terminate and always gives the correct GCD!

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