Exercise 3.1.24* (Number of solutions of the congruence $x^2 \equiv a \pmod m$)

Proof. The decomposition of the odd integer $m$ into prime factors is $m=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}$, where $a_i>0$ and $p_i$ is an odd prime number for every index $i$. Then $x^2\equiv a(\mathit{mod}m)$ is equivalent to the $l$ conditions

For every positive integer $n$, and every integer $x$, write ${[x]}_n$ the class of $x$ in $\mathbb{Z}∕\mathit{n\mathbb{Z}}$. Let $S_n$ denote the roots of $x^2-{[a]}_n$ in $\mathbb{Z}∕\mathit{n\mathbb{Z}}$:

Consider the map

• $\phi$ is well defined: If $y={[x]}_n={[x^{\prime }]}_n\in S_n$, where $x,x^{\prime }$ are integers, then $x\equiv x^{\prime }(\mathit{mod}m)$, thus $x\equiv x^{\prime }(\mathit{mod}{p}_i^{a_i})$, therefore $[x{\text{]}}_{p_i^{a_i}}=[x^{\prime }{\text{]}}_{p_i^{a_i}}$ for every index $i$.
• $\phi$ is injective: If $\phi ({[x]}_m)=\phi {[x^{\prime }]}_m)$, then $x\equiv x^{\prime }(\mathit{mod}{p}_i^{a_i})$ for every $i$, therefore $x\equiv x^{\prime }(\mathit{mod}m)$, so ${[x]}_m={[x^{\prime }]}_m$.

• $\phi$ is surjective: Let $([x_1{\text{]}}_{p_1^{a_1}},[x_2{\text{]}}_{p_2^{a_2}},\dots ,[x_l{\text{]}}_{p_l^{a_l}})$ be any element of $S_{{p_1}^{a_1}}\times S_{{p_2}^{a_2}}\times \cdots \times S_{{p_l}^{a_l}}$. By the Chinese remainder Theorem, there is some integer $x$ such that $x\equiv x_i(\mathit{mod}{p}_i^{a_i})$ for every index $i$. Then

  $$\phi ({[x]}_m)=([x{\text{]}}_{p_1^{a_1}},[x{\text{]}}_{p_2^{a_2}},\dots ,[x{\text{]}}_{p_l^{a_l}})=([x_1{\text{]}}_{p_1^{a_1}},[x_2{\text{]}}_{p_2^{a_2}},\dots ,[x_l{\text{]}}_{p_l^{a_l}})$$

This shows that $\phi$ is a bijection, hence

Since $a\wedge m=1$, $a\wedge p_i$ for every index $i$. By Problem 23,

Therefore

If $a\wedge m=1$, the number of solutions of the congruence $x^2\equiv a(\mathit{mod}m)$ is

□