2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

$$(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

$\endgroup$
  • $\begingroup$ Note that $1$ isn't a prime. $\endgroup$ – Shaun May 13 '17 at 20:55
  • $\begingroup$ @Shaun Good point, so no worry about that one too. $\endgroup$ – Yujie Zha May 13 '17 at 20:56
  • $\begingroup$ Nope. 2*q*^2 has to be even, but any integer multiplied by two is even, so that doesn't eliminate any potential q. $\endgroup$ – Luís Henrique May 14 '17 at 21:53
  • $\begingroup$ @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 $\endgroup$ – Yujie Zha May 14 '17 at 21:56
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.