Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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$. –  Gerry Myerson Jul 13 '12 at 1:21
    
Could you elaborate how that fits into "equal to the product of the number of roots" –  user782220 Jul 13 '12 at 1:28
    
That's just the multiplication principle: en.wikipedia.org/wiki/Rule_of_product –  Micah Jul 13 '12 at 2:46
add comment

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
Beat me by 50 seconds. –  Charles Jul 13 '12 at 1:39
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.