# Quadratic Residue Problem: $2x^2+1\equiv 0\mod p$

When I am learning Number Theory, I saw this question:
"If $p$ is a prime number, then $$2x^2+1\equiv 0\mod p$$ has solution iff $p\equiv 1 \pmod8$ or $p\equiv 3\pmod8$."

Where should I start?

---After first edit---

I have considered when $p=5,7,11,13,17,19,23$ and found out the equation actually have solutions when $p=11,17,19$ which fulfill the condition.

I simplified the equation to $$x^2\equiv \frac{p-1}{2} \pmod p,$$ I am familiar with equation like $x^2\equiv \text{constant}\pmod p$ but this time the remainder will change at the time $p$ change.

I have started finding the Legendre symbol $(\frac{p-1}{2}/p)$ but do not know how to continue.

---After second edit---

I have tried letting $p=8k+1$ which satisfy $p\equiv 1\pmod8$ then substitute in Legendre symbol $$(\frac{p-1}{2}/p)=(4k/8k+1)=(4/8k+1)(k/8k+1)=(k/8k+1)$$ After that I still haven't got any further calculation...

• Okay, sorry for that, I edit a little bit, please guide me if I am on wrong road. – kelvin hong 方 Apr 14 '18 at 10:07
• You could also explain what $x$ is. – José Carlos Santos Apr 14 '18 at 10:09
• $x$ is the variable needed to solve, isn't it? – kelvin hong 方 Apr 14 '18 at 10:11
• +1 for the improved question. Also, you can get rid of $p = 2$ individually, so that you only have to deal with odd numbers. – астон вілла олоф мэллбэрг Apr 14 '18 at 10:12
• @kelvinhong方 It's much better now. – José Carlos Santos Apr 14 '18 at 10:14

We want $\big(\frac{-1 \cdot 2^{-1}}{p}\big) = \big(\frac{-1 \cdot 2}{p}\big) = 1$ which is the case iff $\big(\frac{-1}{p}\big) = \big(\frac{2}{p}\big)$ since the Legendre symbol is multiplicative. Now use the First and Second Nebensatz.
• Wow, I'm surprised that using fraction $\frac{1}{2}$ inside Legendre symbol! Thanks for intuitive solution! – kelvin hong 方 Apr 14 '18 at 10:22