Find all pairs of primes $(p, q)$ such that $p^2 + 6pq + q$ is a perfect square Find all pairs of primes $(p, q)$ such that $p^2 + 6pq + q$ is a perfect square.
This is a problem I encountered a month ago. I remember having had multiple attempts, but they didn't seem to lead anywhere useful; I can't remember what they were now.
If my memory serves me right, a few of my attempts involved quadratic residues (quadratic reciprocity-ish), and desperately trying to work on cases.
How can one approach this problem?
1: A picture of the test paper the problem is from. The language is Vietnamese.
 A: The problem is difficult (barring some typo). I cannot solve it, but I share my thoughts and very modest findings. Nothing much here, I'm afraid.
The equation
$$
a^2=p^2+6pq+q
$$
implies that $a^2\equiv p^2\pmod q$. Taking into account that $q$ is a prime, this implies that $a\equiv\pm p\pmod q$. Because we can replace $a$ with $-a$ without affecting anything, we can assume that we have the plus sign, and hence $a=p+kq$ for some integer $k$. Plugging that into the original equation leads to the equation
$$k^2q-1=(6-2k)p.\qquad(*)$$
Here the left hand side is always positive, so $k<3$. The right hand side is always even, implying that $k$ is odd (and $q>2$). Also $k$ cannot be a multiple of $3$ because then so is the r.h.s. but the l.h.s. is not. But, there seem to be solutions for many values of $k$ (if not all $k$ subject to the above constraints):

*

*If $k=1$ then $(*)$ implies $q=4p+1$. Many primes work here (see the comments).

*If $k=-1$ then similarly $(*)$ implies $q=8p+1$. The same applies.

*If $k=-5$ we get the equation $25q-1=16p$. Modulo $16$ we get $q\equiv 9$, so $q=16r+9$ and $p=25r+14$ for some integer $r$. Here $r=5$ and $r=17$ lead to solutions (the only ones with $r<40$).

*If $k=-7$ we similarly arrive first at $49q-1=20p$ and then $q=20r+9$, $p=49r+22$ for some integer $r$. Here $r=1,3,19$ work (the only solutions with $r<60$).

I don't see any chance of classifying the solutions this way. I'm not a number theorist but IIRC even the simplest similar question:  Are there infinitely many integers $r$ such that $r$ and $2r+1$ are both primes (i.e. infinitude of Sophie Germain primes) is open? I have the impression that many people think there are infinitely many Sophie Germain prime pairs. If only because there is even a conjecture that there are arbitrarily long chains of Sophie Germain pairs: $(r,2r+1)$, $(2r+1,4r+3)$, $\ldots$. Look up Cunningham chains for more information.
Of course, it is natural to think that the lists of prime pairs relevant to this problem: $(4r+1,r)$, $(8r+1,r)$, $(16r+9,25r+14)$, $(20r+9,49r+22)$, $\ldots$, are all sparser than the lists of Sophie Germain pairs. If only because the numbers grow a bit faster here. Anyway, these observations suggest to me that it is extremely difficult to decide whether there are infinitely many prime pair solutions $(p,q)$.
:-(
A: $p^2+6pq+q=a^2$  -----(1)
Eqn. (1) has parametric solution:
$p=w$
$q=4w+1$
$a=5w+1$
We take $(4w+1)$ a prime for prime 'w'. And we get:
$(p,q,a)=(1,5,6)=(3,13,16)=(13,53,66)=(37,149,186)$
A: Not sure if this is all of them.
We want triples $p$, $q$, and $m$ so that
$p^2+6pq+q=m^2$ where p and q are prime and m is some integer.
Alternatively, $(p+3q)^2+q=m^2+9q^2$ by completing the square.
First consider whether p or q is an even prime, i.e. 2. We clearly have no $m$ if $p$ and $q$ are both 2. If $q$ is 2 and $p$ is an odd prime, the left side of the equation is congruent to 3 modulo 4, and the right is a perfect square, an impossibility.
Now suppose $p$=2 and $q$ is an odd prime. Then the equation becomes $4+13q=m^2$. Or, $13q=(m-2)(m+2)$. $13q$ can only be expressed as a product two ways, $13q=1\cdot 13q$ or $13q=13\cdot q $. The first factorization implies $m=3$ and $13q=5$, not possible. We don't know which is the greater of $13$ and $q$ so try two cases. If $m-2=13$ then $m+2=17=q$. So we have our first $(p,q,m)$ triplet, (2,17,15). Assuming $m+2=13$ implies $q=9$, not prime so it is not a solution.
This process can be iterated for the next several primes 3,5,7,11...

*

*Pick a prime $p$

*$(6p+1)q=(m-p)(m+p)$.

*Each permitted factorization implies a value for m which in turn implies a value for q, i.e. If $(m-p)=(6p+1)$ then $m=7p+1$ and $q=8p+1$. Discard if q is composite.

*Step 3 effectively yields the triple $(p,8p+1,7p+1)$ or $(p,4p+1,5p+1)$ depending on if the implied $q$ is prime. So we have (3,13,16), (5,41,36), (7,29,36), (11,89,78), (13,53,66).

Regardless if that is all of them, some properties hold in general. For odd $p$ and $q$, the equation implies $m$ is even. The alternative form implies $q$ must be congruent to 1 modulo 4, consistent with solutions above. Any prime other than 3 is congruent to 1 or -1 modulo 3, so its square is 1. Applying this to the alternative form of the equation tells us that $q$ is congruent to 2 modulo 3, otherwise $m^2$ would be congruent to 2 modulo 3, not possible. It follows that $m$ is divisible by 3. It's already been established at $m$ is even, so the preceding implies $m$ is divisible by 6 if p is not 3.
If we have $q=2 (mod \ 3)$ and $q=1 (mod \ 4)$, the Chinese remainder theorem tells us $q=5 (mod \ 12)$, further narrowing the possibilities.
