# Roots of a polynomial mod $n$

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.

• It's exactly the CRT. Each root mod $n$ gives a root to each of the other congruences, and, by CRT, any choice of roots of the congruences mod the $n_i$ gives a single root of the congruence mod $n$. Jul 13 '12 at 1:21
• Could you elaborate how that fits into "equal to the product of the number of roots" Jul 13 '12 at 1:28
• That's just the multiplication principle: en.wikipedia.org/wiki/Rule_of_product Jul 13 '12 at 2:46

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$.

• Beat me by 50 seconds. Jul 13 '12 at 1:39

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)).$

• See here for a worked example. Apr 29 '20 at 16:05