Determine all pairs $(p, q)$ of prime numbers such that $p^p + q^q + 1$ is divisible by $pq.$
Problem
Source:
Tags: number theory, prime numbers
11.11.2015 21:18
If $(p,q)$ is a solution, so is $(q,p)$. Without loss of generality, assume that $p<q$ since $p=q$ implies $p|1$. Now, $pq|p^p+q^q+1$ gives us two things: $p|q^q+1$ and $q|p^p+1$.. Consider $p=2$, then $q|p^p+1=5$, so $q=5$. Now, $p$ is odd and so $q>p+1$. We can alternatively write them as $q^{2q}\equiv1\pmod p$ and $p^{2p}\equiv1\pmod q$. From Fermat's theorem, we also have $q^{p-1}\equiv1\pmod p$ and $p^{q-1}\equiv1\pmod q$. Thus, $q^{\gcd(2q,p-1)}\equiv1\pmod p$ and $p^{\gcd(2p,q-1)}\equiv1\pmod q$. Since $q$ is odd and greater than $p-1$, $\gcd(q,p-1)=1$. We have $q^2\equiv1\pmod p$ or $p$ divides $(q+1)(q-1)$. If $p$ divides $q-1$, then $p$ also divides $q^q-1$. But that would force the contradiction $p|q^q+1-(q^q-1)=2$. So, $p$ must divide $q+1$. On the other hand, since $p$ can't divide $q-1$, we get $\gcd(2p,q-1)=2$. This gives $p^2\equiv1\pmod q$ or $q|(p+1)(p-1)$. This is impossible since $q$ divides none of $p\pm1$. So no other solutions.