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);
}