Find all pairs of prime numbers (p,q), such that (2p2−1)q+1p+q and (2q2−1)p+1p+q are both integers.
Problem
Source: Turkey EGMO TST 2017 P6
Tags: Turkey, EGMO, TST, number theory, contest problem, order of an element
claserken
02.06.2017 01:50
Here we go for the standard order solution.
Assume p,q are distinct odd primes.
(2p^2-1)^q\equiv -1\pmod{p+q}
(2q^2-1)^p\equiv (2(-p)^2-1)^p\equiv (2p^2-1)^p\equiv -1\pmod{p+q}
Hence,
(2p^2-1)^{2q}\equiv 1\pmod{p+q}
(2p^2-1)^{2p}\equiv 1\pmod{p+q}
Thus, \text{ord}_{p+q}{(2p^2-1)}\mid 2p and \text{ord}_{p+q}{(2p^2-1)}\mid 2q. Hence, \text{ord}_{p+q}{(2p^2-1)}\mid \gcd(2p,2q)=2\gcd(p,q)=2. Thus, \text{ord}_{p+q}(2p^2-1)=2. Now, (2p^2-1)^q\equiv 2p^2-1\equiv -1\pmod{p+q}, since q is odd. This means that p+q\mid 2p^2, since p,q are odd primes p+q is even, so \frac{p+q}{2}\mid p^2. Obviously, \frac{p+q}{2}\neq 1. If \frac{p+q}{2}=p, then p=q, impossible since they're distinct. If \frac{p+q}{2}=p^2, then q=2p^2-p, so p\mid q, since they're primes, p=q, impossible again.
Assume that p=q. It is easy to check that (p,q)=(2,2) doesn't satisfy this, so p and q are odd. We have (2p^2-1)^p\equiv (2p^2-1)\equiv -1\pmod{2p}, since \gcd(2p^2-1,2p)=\gcd(-1,2p)=1. We have 2p^2\equiv 0\pmod{2p}, which is obvious. Thus (p,p) is a solution for any odd prime p.
WLOG p=2. We have q+2\mid (2q^2-1)^2+1 or q+2\mid (2\cdot (-2)^2-1)^2+1 or q+2\mid 50. It is easy to find that either q=3 or q=23. We also know q+2\mid 7^q+1. It is easy to see that q=3 fails. As for q=23, 7^{23}+1\equiv 0\pmod{25} means that 7^{23}+1\equiv 0\pmod{5}, or 2^3+1\equiv 0\pmod{5}, which is false.
In conclusion, the only solution is (p,p) where p is any odd prime.