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.
