Maths Olympiad Prep

Library / /191 of 462

Number theory Difficulty 5.6 AIME, harder Prove it Ireland

Find all prime numbers pp such that 2p+12^p + 1 is a perfect square.

Solution

Solution 1. The only such prime is p=3p=3, when 23+1=322^3 + 1 = 3^2. We consider the remainder of 2k+12^k + 1 on division by 99, for arbitrary integers kk and first note that 26=641(mod9)2^6 = 64 \equiv 1 \pmod{9} and so
2k+6+1262k+12k+1(mod9). 2^{k+6} + 1 \equiv 2^6 2^k + 1 \equiv 2^k + 1 \pmod{9}.
The statement of the question clearly does not hold when p=2p=2 so we must consider only odd primes. In that case, we can determine the following table of 2k+1(mod9)2^k + 1 \pmod{9} given k(mod6)k \pmod{6}:

k(mod6)k \pmod{6}2k+1(mod9)2^k + 1 \pmod{9}
13
30
56

If 33 divides a perfect square, then so must 99 and thus perfect squares can arise only when k3(mod6)k \equiv 3 \pmod{6} and in particular kk is a multiple of 33. The only prime that is also a multiple of 33, is 33 itself.

Solution 2. We first note that 2p+1=n22^p + 1 = n^2 implies that nn needs to be odd. The given equation can be written as 2p=(n1)(n+1)2^p = (n-1)(n+1) with both factors on the right hand side even, hence gcd(n+1,n1)=gcd(n+1,2)=2\text{gcd}(n+1, n-1) = \text{gcd}(n+1, 2) = 2. As n1n-1 and n+1n+1 must both be powers of 22, it follows that the smaller of them, n1n-1, must be equal to 22. This shows that n=3n=3 which leads to the unique solution p=3p=3. The assumption that pp is prime was not needed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.