Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Similar question: math.stackexchange.com/questions/333587/… –  Inceptio Mar 18 '13 at 13:23

1 Answer 1

up vote 3 down vote accepted

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}$.

share|improve this answer
    
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
3  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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