IMO shortlist 1995/N1 solution

36th IMO 1995 shortlist

Problem N1

k is a positive integer. Show that there are infinitely many squares of the form 2^kn - 7.

Solution

We show first that there is at least one such square. We use induction on k. For k = 1 we have 4.2¹ - 7 = 1². For k = 2 we have 2.2² - 7 = 1². For k = 3 we have 1.2³ - 7 = 1². So it is true for k = 1, 2, 3. Suppose it is true for k, so that 2^kn = m² + 7 or m² = -7 mod 2^k. Then either m² = -7 mod 2^k+1 or m² = 2^k - 7 mod 2^k+1. In the first case, we are home. In the second case, we have (m + 2^k-1)² = m² + 2^km + 2^2k-2 = (2^k - 7) + 2^km mod 2^k+1 (since k ≥ 3 implies 2k-2 ≥ k+1) = -7 mod 2^k+1 since m must be odd. So the result holds for all k.

So for each k we have a_k such that a_k² = -7 mod 2^k. But a_k² ≥ 2^k - 7, which is unbounded, so { a_k} is unbounded. Hence there are infinitely many distinct a_k. But if h > k, then a_h² = -7 mod 2^h and hence a_h² = -7 mod 2^k. So there are infinitely many squares for any given k.

36th IMO shortlist 1995