Exercise 3.3.7 (Congruence $x^2 + y^2 \equiv 0 \pmod p$)

Question

For which primes $p$ do there exist integers $x$ and $y$ with $(x,p) = 1,\ (y,p) = 1$, such that $x^2 + y^2 \equiv 0 \pmod p$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
Suppose that $x^2+ y^2 \equiv 0 \pmod p$, where $x\wedge p = 1$ (then $y \wedge p = 1$). Let $\overline{x} \in \Z$ be an inverse of $x$ modulo $p$, so that $x \overline{x} \equiv 1 \pmod p$. Then $$1 + (y \overline{x})^2 \equiv 0 \pmod p,$$ thus $-1$ is a quadratic residue modulo $p$, therefore $p = 2$, or $p$ is odd and $\legendre{-1}{p} = 1.$ This gives $(-1)^{(p-1)/2} = 1$, thus $(p-1)/2$ is even. This shows that
$$p = 2 	ext{ or } p\equiv 1 \pmod 4.$$

Conversely, if $p = 2$ then $1^2 + 1^2 \equiv 0 \pmod p$, and if $p \equiv 1 \pmod 4$, then $\legendre{-1}{p} = (-1)^{(p-1)/2} = 1$, therefore there is some integer $a$ such that  $a^2 + 1 \equiv 0 \pmod p$. Put $x = a,\ y = 1$. Then $x^2 + y^2 \equiv 1$, where $p
mid y = 1$, and $p 
mid x$, otherwise $p \mid 1$.

To conclude, if $p$ is a prime number,
\begin{align*}
\exists x \in \Z, \exists y \in \Z,& \ x\wedge p = 1 	ext{ and } y \wedge p = 1 	ext{ and } x^2 + y^2 \equiv 0 \pmod p\
&\iff p = 2 	ext { or } p\equiv 1 \pmod 4.
\end{align*}
\end{proof}

Exercise 3.3.7 (Congruence $x^2 + y^2 \equiv 0 \pmod p$)

Answers

Comments

Exercise 3.3.7 (Congruence $x^2 + y^2 \equiv 0 \pmod p$)

Answers

Comments

Add answer