How to prove that equation $x^2 + y^2 + 1 = 0$ (mod $p$) has roots?
Hints are acceptable.
Asked
Active
Viewed 1,012 times
3
-
Hint: If you take $y=0$, then all $p$ with $(\frac{-1}{p})=1$ are solved. – vadim123 Oct 31 '14 at 17:01
-
You can show that for $p\equiv 3 \pmod 4$, $y=0, x=\pm\sqrt{-1}$ is a solution where $\sqrt{-1}$ exists because of the requirement $p\equiv 3\pmod 4$... – AlexR Oct 31 '14 at 17:01
-
Hint: Every element of the ring $\mathbb{Z}/p\mathbb{Z}$ is a sum of two squares in that ring. – Geoff Robinson Oct 31 '14 at 17:03
-
You can directly write the solution of the equation: $x^2+y^2=pz-1$ It's easier. – individ Oct 31 '14 at 17:04
-
@vadim123 okay, but if $(\frac{-1}{p}) = -1$ then what? – Jihad Oct 31 '14 at 17:06
-
@GeoffRobinson it seems pretty equal to the whole statement. – Jihad Oct 31 '14 at 17:07
-
@Jihad: It is essentially equivalent, I agree, but it is not so hard to prove directly. – Geoff Robinson Oct 31 '14 at 17:12
1 Answers
8
Hint: Let $p$ be an odd prime. Note that $x^2$ takes on $\frac{p+1}{2}$ distinct values modulo $p$, and so does $-(y^2+1)$. Now use the Pigeonhole Principle.
André Nicolas
- 507,029