Solving an equation for two primes

Question

This is from contest preparation:

Find all pairs of primes $(p, q)$ that satisfy

$$p^q - q^p = p q^2 - 19$$.

It looks simple, but I spent hours trying to solve it... and no luck so far.

NOTE: There are similar MSE Q&Ąs here and here. Perhaps someone could apply some ideas from there.

Answer 1

We have a diophantine equation involving prime numbers. Therefore it makes sense to try to solve the problem with the help of techniques and theorems from this particular field of mathematics. I refer to the answer posted by Hagen von Eitzen.

However, we can also see the problem as a fairly simple math puzzle, and solve it with common sense and elementary mathematical considerations.

The right hand side of the equation has a cubic term and a constant. The left hand side has two terms with (in general) much higher powers. So if we plug in some random values, e.g. $p=7$ and $q=11$, then the absolute value of the LHS will be many orders of magnitude larger than the RHS. Even when the difference between $p$ and $q$ is minimal, the LHS increases much more rapidly than the RHS. Thus there is a strict limit on the maximum value for the smallest of the pair $(p, q)$.

It turns out that $3$ is the critical value. However if we try $(p,q) = (3,5)$, then the LHS is already too large. This effect only increases for larger $q$. From this we conclude that there can be only be solutions if the smallest value equals $2$. [In fact there is also a solution $p=1$ and $q=4$, but these are not prime numbers.]

Case 1. $p=2$. This leads to the equation $f = 2^q - 3q^2 + 19 = 0$. We can easily verify that the function has (roughly) a parabolic shape, and thus there are at maximum two solutions. These are indeed found for $q=3$ and $q=7$.

Case 2. $q=2$. This leads to the equation $g = 2^p -p^2 + 4p -19 = 0$. This function appears to be monotonically increasing. So there is at most one solution. We can verify that $g$ has indeed a zero for a real value of $p$ larger than $4$, smaller than $5$. It follows that there are no solutions where $p$ is a natural number (prime).

Answer 2

Certainly $p\ne q$ (as we cannot have $pq^2-19=0$).

Consider the equation modulo $p$ and $q$, using Fermat's little theorem: $$ -q\equiv -19\pmod p$$ $$ p\equiv -19\pmod q$$ Hence $$-19\equiv p-q\pmod{pq}.$$ Let $p-q=kpq-19$ with $k\in\mathbb Z$. With $p=2$ we arrive at $(2k+1)q=21$, so $q=3$ or $q=7$. This gives us two candidate solutions $(p,q)=\color{red}{(2,3)}$ and $(p,q)=\color{red}{(2,7)}$. Assume from now on that $p\ge 3$. Especially, $(kp+1)q=p+19$ is a positive even number, hence $kp+1$ must be positive even, i.e., $k$ is positive odd.

• The case $k=1$ is only possible with $$ p-2\ge p-q=pq-19\ge 2p-19,$$ i.e., $p\le 17$. For each of $p=3,5,7,11,13,17$, check if $q=\frac{p+19}{p+1} $ is prime. This leads to $(p,q)=\color{red}{(17,2)}$.
• The case $k=3$ is only possible with $$ p-2\ge p-q=3pq-19\ge 6p-19,$$ i.e., $5p\le 17$ and finally $p=3$. However, then $q=\frac{p+19}{3p+1}$ fails to be prime.
• If $k\ge 5$, we find $$ p-2\ge p-q=kpq-19\ge 10p-19,$$ i.e., $9p\le 17$, which is impossible.

Check the original equation with the solution candidates found.