Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $n=n_1n_2\ldots n_k$ where $n_i$ are pairwise relatively prime. Prove for any polynomial $f$ the number of roots of the equation $f(x)\equiv 0\pmod n$ is equal to the product of the number of roots of each of the equations $f(x)\equiv 0\pmod{n_1}$, $f(x)\equiv 0\pmod{n_2}$, $\ldots$, $f(x)\equiv 0\pmod{n_k}$.
I encountered this problem while reading a chapter on RSA encryption. It has something to do with the Chinese remainder theorem but I can't see precisely how to use it.
The Chinese Remainder Theorem says that if $n_1,\ldots,n_k$ are pairwise coprime, and $a_1,\ldots,a_k$ are any integers, then there is a solution to the system of congruences $$\begin{align*} x &\equiv a_1\pmod{n_1}\\ x&\equiv a_2\pmod{n_2}\\ &\cdots\\ x&\equiv a_k\pmod{n_k}, \end{align*}$$ and moreover, the solution is unique modulo $n=n_1\cdots n_k$.
We show that there is a bijection between the set of integers $$A=\{a\in\mathbb{Z}\mid 0\leq a\lt n, f(a)\equiv 0\pmod{n}\}$$ and the set $$B=\{(a_1,\ldots,a_k)\in\mathbb{Z}^k\mid 0\leq a_i\lt n_i, f(a_i)\equiv 0\pmod{n_i},\text{ for }i=1,\ldots,k\}.$$
Suppose first that $a$ is a solution to $f(x)\equiv 0\pmod{n}$. Since $n_i|n$ for each $i$, then $f(a)\equiv 0\pmod{n}$ implies $f(a)\equiv 0\pmod{n_i}$. Hence, $(a\bmod n_1,a\bmod n_2,\ldots,a\bmod n_k)$ is a $k$-tuple of integers whose $i$th entry is a solution to $f(x)\equiv 0\pmod{n_i}$, and satisfies $0\leq a_i\lt n_i$.
Conversely, suppose that $(a_1,\ldots,a_k)$ is a tuple such that $f(a_i)\equiv 0\pmod{n_i}$ for each $i$. Then, by the Chinese Remainder Theorem, there is a unique $a$, $0\leq a\lt n$, such that $a\equiv a_i\pmod{n_i}$ for each $i$. Therefore, $f(a)\equiv f(a_i)\equiv 0\pmod{n_i}$ for $i=1,\ldots,n$. Since the $n_i$ are pairwise coprime and $n_i|f(a)$ for all $i$, then $n=n_1\cdots n_k|f(a)$, so $f(a)\equiv 0\pmod{n}$. That is, each element of $A$ yields an element of $B$.
It is now easy to verify that the maps we have defined $A\to B$ and $B\to A$ are inverses of each other (by the uniqueness clause of the Chinese Reainder Theorem), yielding the desired bijection: $|A|=|B|$.
Note that $A$ is the set of all solutions to $f(x)\equiv0\pmod{n}$, whereas $B$ is the cartesian product of the sets of solutions of $f(x)\equiv 0\pmod{n_i}$; so $|A|$, the number of solutions to $f(x)\equiv 0\pmod{n}$, is the same as the product of the number of solutions of $f(x)\equiv 0\pmod{n_i}$ for $i=1,\ldots,k$.
Each choice of roots mod the $n_i$ corresponds to a solution of the equation mod $n$. The CRT says that, for each choice of the $n_i$ there is just one solution mod $n$. Since they must all be distinct, that gives exactly one root of the equation for each distinct choice of roots to the $n_i$. But these are independent so the number is just the product of the number of roots mod each $n_i$.
Hint $\ $ By CRT, $\rm\:(n_1,n_2)= 1\:\Rightarrow\ \exists$ isomorphism $\rm\,h: \Bbb Z/n_1n_2 \to \Bbb Z/n_1 \times \Bbb Z/n_2\:$ via $\rm\:h(a) = (a_1,a_2).$
So for $\rm\,f\in \Bbb Z[x],\:$ we have: $\rm\: 0 = f(a)\iff (0,0) = h(f(a)) = f(h(a)) = f((a_1,a_2)) = (f(a_1),f(a_2)).$
