Divides Both! Topic: NT/S&S. Level: AIME.

Problem: (Stanford Putnam Practice) Let $ a_0 = 1 $ and $ a_{n+1} = a_n^2+1 $ for $ n \ge 0 $. Find $ \gcd(a_{2004},a_{999}) $.

Solution: Re-label starting with $ a_0 = 0 $, $ a_1 = 1 $ instead. We will prove a much stronger statement, that, $ \gcd(a_m, a_k) = a_{gcd(m,k)} $ for $ m, k \neq 0 $.

First, we will show a lemma that if $ q | a_r $ for positive integers $ r, q $ then $ a_{r+s} \equiv a_s \pmod{q} $ for $ s \ge 0 $. This is trivial by induction, since $ a_r \equiv a_0 \pmod{q} $, $ a_{r+s+1} \equiv a_{r+s}^2+1 \pmod{q} $, and $ a_{s+1} \equiv a_s^2+1 \pmod{q} $.

We will prove the final result by induction as well, on $ \max(m,k) $. When this is $ 1 $, we clearly have $ (a_1, a_1) = 1 = a_{\gcd(1,1)} $.

Assume the property is true for $ \max(m,k) \le p $. Now suppose $ \beta $ divides $ \gcd(a_m,a_{p+1}) $ with $ m < p+1 $. We must have $ a_m \equiv a_{p+1} \equiv 0 \pmod{\beta} $. But then by the lemma above we have $ \beta | a_m \Rightarrow a_{p+1} \equiv a_{p+1-m} \equiv 0 \pmod{\beta} $. So then

$ \gcd(a_m,a_{p+1}) = \gcd(a_m,a_{p+1-m}) $

with $ p+1-m \le p $. But by our inductive hypothesis, we know that

$ \gcd(a_m,a_{p+1-m}) = a_{\gcd(m,p+1-m)} = a_{\gcd(m,p+1)} = \gcd(a_m,a_{p+1}) $, as desired. Shifting the indices in the problem statement, we have

$ \gcd(a_{2005}, a_{1000}) = a_{\gcd(2005,1000)} = a_5 = 677 $. QED.

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

Comment: Pretty classic as far as GCD of terms in a sequence go. It follows a similar property that the Fibonnacci sequence also has. Instead of using induction on the last step, another option was to invoke Euclid's Algorithm to arrive at $ \gcd(m,p+1) $ but that didn't seem quite as fulfilling.

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

Practice Problem: (Stanford Putnam Practice) Define a sequence $ \{a_i\} $ by $ a_1 = 3 $ and $ a_{i+1} = 3^{a_i} $ for $ i \ge 1 $. Which integers between $ 00 $ and $ 99 $ occur as the last two digits of infinitely many $ a_i $?