Euclidean Algorithm

The Euclidean Algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers. It is much faster than prime factorization.

The Algorithm

To find $\gcd (a,b)$ where $a>b$:

1. Divide $a$ by $b$ to get remainder $r$: $a=bq+r$.
2. Replace $(a,b)$ with $(b,r)$.
3. Repeat until the remainder is 0.
4. The last non-zero remainder is the GCD.

Geometric Interpretation

The algorithm is equivalent to tiling a rectangle of size $a\times b$ with the largest possible squares.

1. Fill with $b\times b$ squares.
2. Remaining strip is $b\times r$.
3. Fill with $r\times r$ squares...
4. The side length of the smallest square is the GCD.

Complexity

Lamé's Theorem states that the number of steps is at most 5 times the number of digits in the smaller number (related to Fibonacci numbers).

Practice Problems