Proof of the Euclidean Algorithm

Question

How is the euclidean algorithm infallible? An intuitive approach or sketch of the proof would be much appreciated

Answer 1

The proof shows that

• every step of the algorithm preserves the $\gcd$ of the two numbers.

• every step but the last reduces the numbers.

The proof concludes by observing that as the numbers cannot be reduced anymore, you have found the $\gcd$, and this occurs after a finite number of steps.

---

Technically:

• $\gcd(a,b)=\gcd(b,a\bmod b)$ because $a\bmod b$ and $a$ differ by a multiple of $b$.

• $b<a\implies a\bmod b<a$.

If $a=b$, then $\gcd(a,b)=a$.

---

Addendum:

It can be shown that the largest number of steps occurs when the input numbers are two successive Fibonacci numbers, so that the number of steps is bounded by $\log_\phi a$.