IMO 1995 SL N1

Origin: ROM | Category: Number Theory

Problem

Let k be a positive integer. Prove that there are infinitely many perfect squares of the form n2k −7, where n is a positive integer.

Solution

We show by induction on k that there exists a positive integer ak for which a2 k \equiv−7 (mod 2k). The statement of the problem follows, since every ak + r2k (r = 0, 1, . . . ) also satisfies this condition. Note that for k = 1, 2, 3 one can take ak = 1. Now suppose that a2 k \equiv−7 (mod 2k) for some k > 3. Then either a2 k \equiv−7 (mod 2k+1) or a2 k \equiv2k −7 (mod 2k+1). In the former case, take ak+1 = ak. In the latter case, set ak+1 = ak + 2k−1. Then a2 k+1 = a2 k + 2kak + 22k−2 \equiva2 k + 2k \equiv−7 (mod 2k+1) because ak is odd.