Find all pairs of prime numbers $(p,q)$, such that $\frac{(2p^2-1)^q+1}{p+q}$ and $\frac{(2q^2-1)^p+1}{p+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.