The sequence a1, a2, a3, ... of positive integers is strictly monotonic increasing, a2 = 2 and amn = aman for m, n relatively prime. Show that an = n.
The key observation is that if aN = N for N odd, then a2N = 2N, and hence aN+1 = N+1, aN+2 = N+2, ... , a2N-1 = 2N-1 (because an is strictly increasing, so there are only N-1 holes for N-1 pegs. But we can now repeat using 2N-1 (provided 2N-1 > N, or N > 1) and the result is established for all n.
So we just need to get started with a3. Suppose a3 = m. Then a6 = 2m. So m+2 ≤ a5 ≤ 2m-1. Hence a10 ≤ 4m-2 and a9 ≤ 4m-3. So a18 ≤ 8m-6 and hence a15 ≤ 8m-9. But a15 = a3a5 ≥ m2+2m, so m2+2m ≤ 8m-9 or (m-3)2 ≤ 0. Hence m = 3.
24th Putnam 1963
© John Scholes
5 Feb 2002