## Tuesday, November 28, 2006

### 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$?