Exercise 3.18

Proof. Note ${[x]}_n$ the class of $x$ modulo $n$. Let $S$ the set of solutions in $\mathbb{Z}∕\mathit{n\mathbb{Z}}$ of $f(\bar{x})=0$, and $S_i$ the set of solutions in $\mathbb{Z}∕p^{a_i}\mathbb{Z}$ of $f(\bar{x})=0$.

(We designate with the same letter the polynomial $f$ in $\mathbb{Z}[x]$ or its reduction in $\mathbb{Z}∕\mathit{n\mathbb{Z}}[x]$.)

Let

$\text{∙}$ $\phi$ is well defined: if $x\equiv x^{\prime }(\mathit{mod}n)$, then $x\equiv x^{\prime }(\mathit{mod}{p}_i^{a_i}),i=1,2,\cdots ,t$, so $([x{\text{]}}_{p_1^{a_1}},[x{\text{]}}_{p_2^{a_2}},\dots ,[x{\text{]}}_{p_t^{a_t}})=([x^{\prime }{\text{]}}_{p_1^{a_1}},[x^{\prime }{\text{]}}_{p_2^{a_2}},\dots ,[x^{\prime }{\text{]}}_{p_t^{a_t}})$. Moreover, we proved in Ex 3.17 that ${[x]}_n\in S\Rightarrow {[x]}_{p_i^{a_i}}\in S_i$.

$\text{∙}$ $\phi$ is injective: if $([x{\text{]}}_{p_1^{a_1}},[x{\text{]}}_{p_2^{a_2}},\dots ,[x{\text{]}}_{p_t^{a_t}})=([x^{\prime }{\text{]}}_{p_1^{a_1}},[x^{\prime }{\text{]}}_{p_2^{a_2}},\dots ,[x^{\prime }{\text{]}}_{p_t^{a_t}})$, then $p_i^{a_i}\mid x^{\prime }-x,i=1,2,\dots ,t$, thus $n\mid x^{\prime }-x$ and ${[x]}_n={[x^{\prime }]}_n$.

$\text{∙}$ $\phi$ is surjective: if $y=([x_1{\text{]}}_{p_1^{a_1}},[x_2{\text{]}}_{p_2^{a_2}},\dots ,[x_t{\text{]}}_{p_t^{a_t}})$ is any element of $S_1\times S_2\times \cdots \times S_t$, there exists by the Chinese Remainder Theorem $x\in \mathbb{Z}$ such that $x\equiv x_i(\mathit{mod}{p}_i^{a_i})$. Then $\phi ({[x]}_n)=y$ (see Ex. 3.17).

In conclusion, $\phi$ is bijective, therefore $N=|S|=|S_1\times S_2\times \cdots \times S_t|=N_1{N}_2\cdots N_t$. □