Maths Olympiad Prep

Library / /11 of 27

Number theory Difficulty 5.5 AIME, harder Prove it Croatia

Determine all pairs (p,q)(p, q) of prime numbers for which pq1+qp1p^{q-1} + q^{p-1} is a perfect square.

Solution

Let nn be a positive integer such that
pq1+qp1=n2. p^{q-1} + q^{p-1} = n^2.
We will divide our solution into cases, depending on the parity of numbers pp and qq.

If both are even, the only possibility is that both are equal to 22. This leads to a solution (p,q)=(2,2)(p, q) = (2, 2) for n=2n = 2.

If both pp and qq are odd, we conclude that there are no solutions by looking at the remainder of division by 44. If pp and qq are odd, then p1p-1 and q1q-1 are even, so that pq1p^{q-1} and qp1q^{p-1} are squares of odd numbers. This means that they always give remainder 11 when divided by 44. This shows that the left-hand side gives remainder 22 when divided by 44, whereas n2n^2 must give remainder 11 or 00 when divided by 44.

The only remaining case is when one of the numbers pp and qq is even, while the other is odd. The equation being symmetric, we can, without loss of generality, assume that pp is odd, i.e. p=2k+1p = 2k+1 for some positive integer kk, and that qq equals 22.

Now we have
p+2p1=n2, i.e. p=n222k=(n2k)(n+2k). p + 2^{p-1} = n^2, \quad \text{ i.e. } p = n^2 - 2^{2k} = (n - 2^k)(n + 2^k).
Since pp is prime, the only way in which we can represent it as a product (n2k)(n+2k)(n - 2^k)(n + 2^k) is if one of the factors equals ±1\pm 1, while the other is ±p\pm p. Notice that n+2k>0n + 2^k > 0, and also that n+2k>n2kn + 2^k > n - 2^k, which yields
n2k=1andn+2k=p. n - 2^k = 1 \quad \text{and} \quad n + 2^k = p.
Subtracting these two equalities, we get
2k+1+1=p=2k+1. 2^{k+1} + 1 = p = 2k + 1.
Let us prove that this equation has no solution. We know that 2k+1+12^{k+1} + 1 gives remainder 11 when divided by 44, so the same must hold for 2k+12k + 1. This implies that kk is even, i.e. k=2lk = 2l for some positive integer ll. In that case,
p=2k+1+1=22l+1+1=24l+1 p = 2^{k+1} + 1 = 2^{2l+1} + 1 = 2 \cdot 4^l + 1
is divisible by 33 (because 4l4^l gives remainder 11 when divided by 33). We conclude that pp is divisible by 33, so p=3p = 3. Plugging this into the initial equation, we see that p=3p = 3 and q=2q = 2 is not a solution.

This means that the only solution is (p,q)=(2,2)(p, q) = (2, 2).

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 and solution reproduced as published; topic and difficulty added by this site.