# For an odd prime $p$, prove that the congruence $2x^2 +1 \equiv 0\pmod p$ has a solution if and only if $p ≡ 1 \text{ or } 3\pmod 8$

I have to prove that the congruence $2x^2 +1 ≡ 0\pmod p$ has a solution if and only if $p ≡ 1 \text{ or } 3\pmod 8$, for any odd prime.

Thanks.

-
Similar question: math.stackexchange.com/questions/333587/… –  Inceptio Mar 18 '13 at 13:23

You want $-2$ to be a square modulo $p$. In fact a solution $x$ exists if and only if $x^{2} \equiv (-2)/4$ is a square modulo $p$, and thus if and only if $-2$ is a square modulo $p$.

This is because the following congruences modulo $p$ are equivalent: (reworked avoiding inverses at a suggestion of Math Gems in the comments)

• $2 x^2 + 1 \equiv 0$
• $2 x^{2} \equiv -1$
• $(2 x)^{2} \equiv - 2$

Now $$\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac{2}{p}\right)$$ is $1$ if and only if $p \equiv 1, 3 \pmod{8}$.

-
The first part is what I wanted to know how is 2x^2+1=0(mod p) same as x^2 = -2 (mod p) –  noddy Mar 18 '13 at 13:18
@noddy, is it clear now? $2 x^2 + 1 \equiv 0$ is the same as $2 x^{2} \equiv -1$ which is the same as $x^{2} \equiv - 2^{-1} \equiv (-2) (2^{-1})^{2}$, where $2^{-1}$ denotes the inverse of $2$ modulo the odd prime $p$. –  Andreas Caranti Mar 18 '13 at 13:20
yah..had initially missed the inverse part..Thanks –  noddy Mar 18 '13 at 13:22
@noddy, you're welcome. –  Andreas Caranti Mar 18 '13 at 13:24
@noddy $\rm\ mod\ p\!:\ -1 \equiv kx^2\:\Rightarrow -k\equiv k^2 x^2 \equiv (kx)^2.\:$ Note that one does not need to use inverses to make that inference. It is squareness, not invertibility, that plays the key role. –  Math Gems Mar 18 '13 at 13:45