Proving GCD Properties

Intro to Proofs · Axiom Academy

EXAMPLE Proving GCD Properties Understanding the key insight behind the Euclidean Algorithm Prove that for integers a and b with b > 0 , the greatest common divisor satisfies . This single fact is the engine of the Euclidean algorithm. Excellent work! You've completed a fundamental proof in number theory. Here's what we learned: Two-Way Proof Strategy: To show two sets are equal, we proved that every element of one set is in the other, and vice versa. Division Algorithm Foundation: The relationship is the starting point for understanding how remainders relate to the GCD. Divisibility is Preserved: If divides both a and b , then d divides any linear combination of a and b , including the remainder r . Same Divisors → Same GCD: Since (a,b) and (b,r) have exactly the same set of common divisors, their greatest common divisors must be equal. Euclidean Algorithm Foundation: This theorem justifies the Euclidean algorithm: we can repeatedly replace (a,b) with without changing the GCD, until we reach (d,0) where the answer is obvious. This elegant result shows that finding the GCD of large numbers reduces to finding the GCD of progressively smaller numbers, making computation feasible even for very large integers. It's one of the oldest and most efficient algorithms still in use today!

This is the written version of the interactive lesson above. See the full Intro to Proofs course.