Maths Olympiad Prep

Library / International Mathematical Olympiad /55 of 110

International Mathematical Olympiad

Number theory Difficulty 8.4 Shortlist Prove it IMO

Find all pairs (p,q)(p, q) of prime numbers with p>qp > q for which the number
(p+q)p+q(p−q)p−q−1(p+q)p−q(p−q)p+q−1 \frac{(p+q)^{p+q}(p-q)^{p-q}-1}{(p+q)^{p-q}(p-q)^{p+q}-1}
is an integer.

Solution

Let M=(p+q)p−q(p−q)p+q−1M = (p+q)^{p-q}(p-q)^{p+q} - 1, which is relatively prime with both p+qp+q and p−qp-q. Denote by (p−q)−1(p-q)^{-1} the multiplicative inverse of (p−q)(p-q) modulo MM.
By eliminating the term −1-1 in the numerator,
(p+q)p+q(p−q)p−q−1≡(p+q)p−q(p−q)p+q−1( mod M)(p+q)2q≡(p−q)2q( mod M)((p+q)⋅(p−q)−1)2q≡1( mod M) \begin{align*} (p+q)^{p+q}(p-q)^{p-q}-1 &\equiv (p+q)^{p-q}(p-q)^{p+q}-1 \quad (\bmod M) \\ (p+q)^{2q} &\equiv (p-q)^{2q} \quad (\bmod M) \tag{1}\\ \left((p+q) \cdot (p-q)^{-1}\right)^{2q} &\equiv 1 \quad (\bmod M) \tag{2} \end{align*}

Case 1: q⩾5q \geqslant 5.
Consider an arbitrary prime divisor rr of MM. Notice that MM is odd, so r⩾3r \geqslant 3. By (2), the multiplicative order of ((p+q)⋅(p−q)−1)\left((p+q) \cdot (p-q)^{-1}\right) modulo rr is a divisor of the exponent 2q2q in (2), so it can be 1,2,q1, 2, q or 2q2q.
By Fermat's theorem, the order divides r−1r-1. So, if the order is qq or 2q2q then r≡1( mod q)r \equiv 1 (\bmod q). If the order is 11 or 22 then r∣(p+q)2−(p−q)2=4pqr \mid (p+q)^2 - (p-q)^2 = 4pq, so r=pr = p or r=qr = q. The case r=pr = p is not possible, because, by applying Fermat's theorem,
M=(p+q)p−q(p−q)p+q−1≡qp−q(−q)p+q−1=(q2)p−1≡q2−1=(q+1)(q−1)(modp) M = (p+q)^{p-q}(p-q)^{p+q} - 1 \equiv q^{p-q}(-q)^{p+q} - 1 = \left(q^2\right)^p - 1 \equiv q^2 - 1 = (q+1)(q-1) \pmod{p}
and the last factors q−1q-1 and q+1q+1 are less than pp and thus p∤Mp \nmid M. Hence, all prime divisors of MM are either qq or of the form kq+1kq+1; it follows that all positive divisors of MM are congruent to 00 or 11 modulo qq.
Now notice that
M=((p+q)p−q2(p−q)p+q2−1)((p+q)p−q2(p−q)p+q2+1) M = \left((p+q)^{\frac{p-q}{2}}(p-q)^{\frac{p+q}{2}} - 1\right)\left((p+q)^{\frac{p-q}{2}}(p-q)^{\frac{p+q}{2}} + 1\right)
is the product of two consecutive positive odd numbers; both should be congruent to 00 or 11 modulo qq. But this is impossible by the assumption q⩾5q \geqslant 5. So, there is no solution in Case 1.

Case 2: q=2q = 2.
By (1), we have M∣(p+q)2q−(p−q)2q=(p+2)4−(p−2)4M \mid (p+q)^{2q} - (p-q)^{2q} = (p+2)^4 - (p-2)^4, so
(p+2)p−2(p−2)p+2−1=M⩽(p+2)4−(p−2)4⩽(p+2)4−1,(p+2)p−6(p−2)p+2⩽1. \begin{gathered} (p+2)^{p-2}(p-2)^{p+2} - 1 = M \leqslant (p+2)^4 - (p-2)^4 \leqslant (p+2)^4 - 1, \\ (p+2)^{p-6}(p-2)^{p+2} \leqslant 1. \end{gathered}
If p⩾7p \geqslant 7 then the left-hand side is obviously greater than 11. For p=5p = 5 we have (p+2)p−6(p−2)p+2=7−1⋅37(p+2)^{p-6}(p-2)^{p+2} = 7^{-1} \cdot 3^7 which is also too large.
There remains only one candidate, p=3p = 3, which provides a solution:
(p+q)p+q(p−q)p−q−1(p+q)p−q(p−q)p+q−1=55⋅11−151⋅15−1=31244=781. \frac{(p+q)^{p+q}(p-q)^{p-q}-1}{(p+q)^{p-q}(p-q)^{p+q}-1} = \frac{5^5 \cdot 1^1 - 1}{5^1 \cdot 1^5 - 1} = \frac{3124}{4} = 781.
So in Case 2 the only solution is (p,q)=(3,2)(p, q) = (3, 2).

Case 3: q=3q = 3.
Similarly to Case 2, we have
M∣ (p+q)2q−(p−q)2q=64⋅((p+32)6−(p−32)6). M \left\lvert\, (p+q)^{2q} - (p-q)^{2q} = 64 \cdot \left(\left(\frac{p+3}{2}\right)^6 - \left(\frac{p-3}{2}\right)^6\right) .\right.
Since MM is odd, we conclude that
M∣ (p+32)6−(p−32)6 M \left\lvert\, \left(\frac{p+3}{2}\right)^6 - \left(\frac{p-3}{2}\right)^6\right.
and
(p+3)p−3(p−3)p+3−1=M⩽(p+32)6−(p−32)6⩽(p+32)6−1,64(p+3)p−9(p−3)p+3⩽1. \begin{gathered} (p+3)^{p-3}(p-3)^{p+3} - 1 = M \leqslant \left(\frac{p+3}{2}\right)^6 - \left(\frac{p-3}{2}\right)^6 \leqslant \left(\frac{p+3}{2}\right)^6 - 1, \\ 64(p+3)^{p-9}(p-3)^{p+3} \leqslant 1. \end{gathered}
If p⩾11p \geqslant 11 then the left-hand side is obviously greater than 11. If p=7p = 7 then the left-hand side is 64⋅10−2⋅410>164 \cdot 10^{-2} \cdot 4^{10} > 1. If p=5p = 5 then the left-hand side is 64⋅8−4⋅28=22>164 \cdot 8^{-4} \cdot 2^8 = 2^2 > 1. Therefore, there is no solution in Case 3.

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

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