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