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]