## Tuesday, December 19, 2006

### I Am The Greatest (Common Divisor)! Topic: Number Theory. Level: Olympiad.

Problem: (Stanford Putnam Practice) Suppose $(a_i)_{i \ge 1}$ is a sequence of positive integers satisfying $\gcd(a_i, a_j) = \gcd(i, j)$ for $i \neq j$. Show that $a_i = i$ for each $i$.

Solution: Let $n$ be an arbitrary positive integer. If we can show that $a_n = n$ we will be done. We have

$\gcd(a_n, a_{2n}) = \gcd(n, 2n) = n$

so $n|a_n$. Then $a_n = kn$ for some positive integer $k$. Similarly, we know $kn|a_{kn}$ so $a_{kn} = ckn$ for some positive integer $c$. Then, however,

$\gcd(a_n, a_{kn}) = (kn, ckn) = kn$ and $\gcd(n, kn) = n$

so we must have $kn = n \Rightarrow k = 1$. Thus $a_n = n$. QED.

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

Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since $a_1 = 1, a_2 = 2, \ldots, a_k = k$ puts very few restrictions on $a_{k+1}$. So then you look to a better option, trying to find the strongest use of $\gcd(i, j)$. It turns out that this happens when $j$ is a multiple of $i$, which is exactly how the above proof starts.

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

Practice Problem: (Stanford Putnam Practice) Let $p > 5$ be a prime number. Show that $p$ divides infinitely many of the numbers

$1, 11, 111, 1111, \ldots$.

[Reworded]