# Find, with proof, all prime numbers $p$ and $q$ such that $p^2-2q^2=1$

Find, with proof, all prime numbers $p$ and $q$ such that $p^2-2q^2=1$.

I've got a crappy guess-and-check solution, which states that only $p=3$ and $q=2$ works, which is obvious. The equation also doesn't seem to be factorable.

How do I prove that I didn't miss anything?

$$(p-1)(p+1)=2q^2$$

Notice $p= 2$ is not a solution, and thus the left side are two even numbers, thus $q$ has to be even, not a prime if it is larger than 2

• Note that $1$ isn't a prime. – Shaun May 13 '17 at 20:55
• @Shaun Good point, so no worry about that one too. – Yujie Zha May 13 '17 at 20:56
• Nope. 2*q*^2 has to be even, but any integer multiplied by two is even, so that doesn't eliminate any potential q. – Luís Henrique May 14 '17 at 21:53
• @LuísHenrique Hey, notice on the left side of the equation, you get two even numbers multiplying together, which has a factor of $4$, but on the right hand side, we only have $2$ if $q$ is not even - hope this explains your doubt – Yujie Zha May 14 '17 at 21:56

Consider the equation modulo 3. You can check that any number squared mod 3 is either 0 or 1, and in particular if $n$ is a prime not equal to 3, then $n^2$ is 1. Say $(p, q)$ solves the equation, where $p$ and $q$ are prime. If $q$ is not equal to $3$, then $2q^2+1 = 0$ (mod 3), so $p$ must be 3. So, either $p$ or $q$ is $3$, and you can check $q=3$ doesn't work clearly, so $(3,2)$ is the only solution.

• Why would $q$ have to be 3? Couldn't it be a multiple of 3? – Gerard L. May 13 '17 at 20:43
• Not if $q$ is a prime! – B. Mehta May 13 '17 at 20:44
• My bad. I forgot about that condition. – Gerard L. May 13 '17 at 20:46