Maths Olympiad Prep

Library / /3 of 21

Number theory Difficulty 5.7 AIME, harder Prove it South Korea

Find all pair (p,q)(p, q) of primes such that pp+qq+1p^p + q^q + 1 is divisible by pqpq.

Solution

Clearly, pqp \ne q. So we may assume that p<qp < q without loss of generality. Assume that p=2p = 2. Then since
qq+550(modq), q^q + 5 \equiv 5 \equiv 0 \pmod{q},
the only possible prime for qq is 55. Furthermore, (p,q)=(2,5)(p, q) = (2, 5) satisfies the above condition. Now we assume that both pp and qq are odd primes. Since pp+10(modq)p^p + 1 \equiv 0 \pmod{q}, pp1pp2+p+1p^{p-1} - p^{p-2} + \dots - p + 1 is divisible by qq and p2p1(modq)p^{2p} \equiv 1 \pmod{q}. On the other hand, Fermat's Little Theorem says
pq11(modq). p^{q-1} \equiv 1 \pmod{q}.
If gcd(2p,q1)=2\gcd(2p, q-1) = 2, then p21(modq)p^2 \equiv 1 \pmod{q}. Hence p1(modq)p \equiv 1 \pmod{q} or p1(modq)p \equiv -1 \pmod{q}. Therefore
0pp1pp2+p+11(modq), 0 \equiv p^{p-1} - p^{p-2} + \dots - p + 1 \equiv 1 \pmod{q},
which is a contradiction. Assume that gcd(2p,q1)=2p\gcd(2p, q - 1) = 2p, that is, q1(modp)q \equiv 1 \pmod p. In this case we have
0pp+qq+1pp+1+12(modp), 0 \equiv p^p + q^q + 1 \equiv p^p + 1 + 1 \equiv 2 \pmod{p},
which is again a contradiction.
Therefore (p,q)=(2,5)(p, q) = (2, 5) or (5,2)(5, 2) is the only pair of primes satisfying the above condition. \square

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.