# Chinese Remainder Theorem and polynomial roots

Suppose $$f$$ is a polynomial with integer coefficients and that $$f(3) \equiv 0 \mod 7$$ and $$f(5)\equiv 0\mod 11$$. Use the Chinese Remainder Theorem to show that there exists $$x \in \mathbb{Z}$$ such that $$f(x)\equiv 0 \mod 77$$.

This is a CRT problem where we are given two equivalences with relatively prime moduli.

All I can see is that the CRT gives us some unique $$K \mod 77$$ $$\\$$ such that $$K\equiv f(3)\equiv 0 \mod 7 \quad \operatorname{and} \mod 11$$, but I have no idea why there must be an $$x$$, such that $$f(x)\equiv K\equiv 0 \mod 77$$

More generally,

Assume f(x) is a polynomial with integer coefficients. Assume the polynomial has a root modulo m and a root modulo n, and assume gcd(m, n)=1. Prove that the polynomial has a root modulo mn.

• The missing ingredient is the fact that since the coefficients of $f$ are in $\Bbb Z$, if $a\equiv b\pmod p$, then $f(a)\equiv f(b)\pmod p$. Commented Mar 21, 2019 at 3:45

## 2 Answers

By the CRT, $$\exists x\in\mathbb{Z}$$ such that

$$x\equiv 3 \mod 7 \\ x\equiv 5 \mod 11$$.

Since $$7 |f(x)$$ and $$11|f(x)$$ and 7 and 11 are coprime, $$\quad 77|f(x)$$

If $$K \equiv 0 \mod 7$$ and $$K \equiv 0 \mod 11$$ then (since $$7$$ and $$11$$ are co-prime... indeed each is prime) $$K \equiv 0 \mod 77$$.

• Why should $K$ be the value of the function? Commented Mar 21, 2019 at 3:23