Mathematical Reflections 2017, Issue 5 - Problem S423

Problem:
Let $p$ and $q$ be prime numbers such that $p^2+pq+q^2$ is a perfect square. Prove that $p^2-pq+q^2$ is prime.

Proposed by Alessandro Ventullo, Milan, Italy

First solution:
Let $p^2+pq+q^2=n^2$. Then, $(p+q)^2=n^2+pq$ where $n \in \mathbb{N}$, which gives $$(p+q-n)(p+q+n)=pq.$$ If $p=q$, then $(2p-n)(2p+n)=p^2$. Since $2p-n<2p+n$, then $2p-n=1$ and $2p+n=p^2$, i.e. $4p=1+p^2$, which gives no integer solution. If $p \neq q$, assuming without loss of generality that $p<q$, then since $p+q-n<p+q+n$, we have
$$\begin{array}{lll} p+q-n &=& 1 \\ p+q+n &=& pq, \end{array} \qquad \begin{array}{lll} p+q-n &=& p \\ p+q+n &=& q. \end{array}$$
The first system gives $2(p+q)=pq+1$, i.e. $(p-2)(q-2)=3$, which gives $p=3, q=5$. The second equation of the second system gives $p+n=0$, contradiction. So, we get $(p,q) \in \{(3,5),(5,3)\}$ and $p^2-pq+q^2=19$, which is prime.

Second solution:Observe that $p^2<p^2+pq+q^2<(p+q)^2$ for all primes $p,q$. Hence, $$p^2+pq+q^2=(p+k)^2,$$ where $k \in \{1,2,\ldots,q-1\}$, i.e. $$pq+q^2=2kp+k^2.$$ We get
$$
p(2k-q)=(q-k)(q+k) \qquad (1)
$$
Since the right-hand side is positive, it follows that $q<2k$. Moreover, since $p$ is prime, then $p \ | \ (q-k)$ or $p \ | \ (q+k)$.

(i) If $p \ | \ (q-k)$, then $q-k=ph$ for some $h \in \mathbb{N}$, so equation (1) becomes $$2k-q=h(k+q).$$ It follows that $(k+q) \ | \ (2k-q)$. Since $2k-q=2(k+q)-3q$, then $(k+q) \ | \ 3q$. If $q=3$, there is no solution. If $q \neq 3$, we have $k+q \in \{1,3,q,3q\}$. But $1<q<k+q<2q<3q$, so it must be $k+q=3$. Since $q$ is prime, this gives $q=2$ and $k=1$, but this would imply that $p \ | \ 1$, contradiction.

(ii) If $p \ | \ (q+k)$, then $q+k=ph$ for some $h \in \mathbb{N}$, so equation (1) becomes $$2k-q=h(q-k).$$ It follows that $(q-k) \ | \ (2k-q)$. Since $2k-q=2(k-q)+q$, then $(q-k) \ | \ q$. But $q-k<q$, so $q-k=1$. Equation \eqref{first-eq} becomes $$p(q-2)=2q-1,$$ which implies $(q-2) \ | \ (2q-1)=[2(q-2)+3]$, i.e. $(q-2) \ | \ 3$. So, $q=3$ or $q=5$, which gives $p=5$ or $p=3$ respectively.

Therefore, $(p,q) \in \{(3,5),(5,3)\}$, which gives $p^2-pq+q^2=19$, which is prime.

Conjecture:
Let $k$ be a positive integer such that if $p^2+kpq+q^2$ is a perfect square, then $p^2-kpq+q^2$ is a prime. Then, $k=1$. Me and Robert Bosch tried to disprove this conjecture with Maple for small $k$, but it seems that $k$ is the only positive integer with this property.