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.

  • 2
    $\begingroup$ 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$. $\endgroup$ – Lubin Mar 21 at 3:45

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

  • $\begingroup$ Why should $K$ be the value of the function? $\endgroup$ – Jungleshrimp Mar 21 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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