## Sunday, December 17, 2006

### Toast To Euclid. Topic: Number Theory. Level: AMC/AIME.

Introduction: (Euclid's Algorithm) Given two positive integers $a, b$, we can determine $\gcd(a,b)$ through the following algorithm. Let $a = bq+r$, where $q, r$ are positive integers such that $0 \le r < b$. If $r = 0$, then $\gcd(a, b) = b$. Otherwise, let $a = b$, $b = r$, and repeat. For example, if we wanted to find $\gcd(140, 98)$, we would do

$140 = 98 \cdot 1+42$

$98 = 42 \cdot 2+14$

$42 = 14 \cdot 3+0$

so $\gcd(140,98) = 14$. A proof of this result is left to the reader.

--------------------

Problem: (Stanford Putnam Practice) Prove that consecutive Fibonacci numbers are always relatively prime.

Solution: Well, since we had a handy introduction to Euclid's Algorithm up there, let's try to use it. We want to calculate $\gcd(F_{n+1}, F_n)$. Executing the algorithm, we get

$F_{n+1} = F_n \cdot 1+F_{n-1}$

$F_n = F_{n-1} \cdot 1+F_{n-2}$

$F_{n-1} = F_{n-2} \cdot 1+F_{n-3}$.

Hmm, is there a pattern? I think so! We eventually get

$F_3 = F_2 \cdot 1+F_1$

$F_2 = F_1 \cdot 2+0$.

So $\gcd(F_{n+1}, F_n) = F_1 = 1$, as desired. QED.

--------------------

Comment: Euclid's Algorithm is an extremely powerful tool for computing greatest common divisors. It even comes in handy in computer science, where we can write a very simple recursive method to compute $\gcd(a,b)$. For example

int gcd(int a, int b)
{
if(b > a) swap(a,b);
if(b == 0) return a;
a %= b;
return gcd(b, a);
}