1
$\begingroup$

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.

$\endgroup$
1
  • 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
    Commented Mar 21, 2019 at 3:45

2 Answers 2

3
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .