Exercise 3.3.9 (Congruence $x^2 + y^2 \equiv 0 \pmod n$)

Proof. If $n=1$, $x^2+y^2\equiv 0(\mathit{mod}n)$ for all integers $x,y$. We suppose now that $n>1$.

Write $n=2^{a_0}{p}_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$ the decomposition of $n$ in prime factors, where $p_1,p_2,\dots ,,p_k$ are distincts odd primes, and $a_0\ge 0$, $a_i>0$ for every index $i=1,2,\dots ,k$.

Suppose that $x^2+y^2\equiv 0(\mathit{mod}n)$, where $x\wedge n=y\wedge n=1$. Then

If $a_0>1$, then by Problem 8 the congruence $x^2+y^2\equiv 0(\mathit{mod}{2}^{a_0})$ has no solution $(x,y)$ where $x,y$ are odd. Therefore $a_0=0$, or $a_0=1$.

Moreover, Problem 8 shows that $p_i\equiv 1(\mathit{mod}4)$.

Conversely, suppose that $n=2^{a_0}{p}_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$, where $a_0\in \{0,1\}$, $a_i>0$ and $p_i\equiv 1(\mathit{mod}4)$ for $i=1,2,\dots ,k$.

By Problem 8, for each index $i=1,2,\dots ,k$, there are some integers $x_i,y_i$ satisfying $x_i\wedge p_i=y_i\wedge p_i=1$ and

• If $a_0=0$, by the Chinese Remainder Theorem, there are integers $x,y$ such that $x\equiv x_i(\mathit{mod}{p}_i^{a_i})$ and $y\equiv y_i(\mathit{mod}{p}_i^{a_i})$ for $i=1,2,\dots k$. Then

  $$x^2+y^2\equiv x_i^2+y_i^2\equiv 0(\mathit{mod}{p}_i^{a_i}).$$

  Since the $p_i^{a_i}$ are relatively prime by pairs, this implies

  $$x^2+y^2\equiv 0(\mathit{mod}n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}).$$

  Moreover $x\equiv x_i(\mathit{mod}{p}_i^{a_i})$ implies $x\wedge p_i=1$. Similarly $y\wedge p_i=1$. Therefore $x\wedge p=y\wedge p=1$.

• If $a_0=1$, there are integers $x,y$ such that $x\equiv x_i(\mathit{mod}{p}_i^{a_i})$ and also $x\equiv 1(\mathit{mod}2)$, and $y\equiv y_i(\mathit{mod}{p}_i^{a_i})$ for $i=1,2,\dots k$, and $y\equiv 1(\mathit{mod}2)$. Then

  $$x^2+y^2\equiv 0(\mathit{mod}n=2p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}),$$

  where $x\wedge p_i=y\wedge p_i=1$ and $x\wedge 2=y\wedge 2=1$. Therefore $x\wedge n=y\wedge n=1$

If $n>1$, there exist integers $x$ and $y$ with $(x,n)=1,(y,n)=1$, such that $x^2+y^2\equiv 0(\mathit{mod}n)$ if and only if $n=2^{a_0}{p}_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$, where $a_0=0$ or $a_0=1$, $a_i>0$ and the distinct odd primes $p_i$ satisfy $p_i\equiv 1(\mathit{mod}4)$. □