I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field.

Consider the equation:

$$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$

For which primes $p$ is it possible for this equation to have solutions in $a$ and $b$?

I wrote a quick brute force number crunching program to find that for primes 3, 5, 11, 13, and 19 there are no solutions in $a$ and $b$.

However, for primes 7 and 17, there exist solutions.

Is there a discernible condition on $p$ such that this congruence has solutions?


Yes—indeed this is a classical motivating problem of number theory, addressed by Euler and Gauss among others.

First of all, note that $a\equiv b\equiv0\pmod p$ is a solution for any $p$; I assume you mean to exclude these trivial solutions. That means we can assume that neither $a$ nor $b$ is $0\pmod p$ (since if one is, the other is too).

In particular, $b$ is invertible modulo $p$, and so the congruence is equivalent to $(ab^{-1})^2 \equiv 2\pmod p$. Therefore if the congruence has nontrivial solutions, so does the congruence $x^2\equiv2\pmod p$. Conversely, if $x^2\equiv2\pmod p$ has solutions, then take $a=x$ and $b=1$.

So we've reduced the problem to deciding which primes $p$ have "square roots of $2$"; in other words, we want to know for which primes $2$ is a quadratic residue. And this is a classical theorem: they are exactly the primes congruent to either $1$ or $7$ modulo $8$.

  • $\begingroup$ Thank you very much! The terminology really helps when researching this! $\endgroup$
    – cemulate
    Nov 24 '14 at 8:14

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.