Determine all prime numbers $p,q$ such that $$p^2+pq+q^2$$ is a perfect square.
Proposed by Alessandro Ventullo, Milan, Italy
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 (1) 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)\}$.
Note:
A variant of this problem can be the following:
Let $p,q$ be prime numbers such that $$p^2+pq+q^2$$ is a perfect square. Prove that $$p^2-pq+q^2$$ is prime.
\newline\newline
Indeed, $p$ and $q$ can be found as before and we get $p^2-pq+q^2=19$.
