# Chinese remainder theorem for polynomial evaluation

Let $R$ be a euclidean domain, $m_0,\ldots ,m_{k-1}\in R$ be pairwise coprime and $m:=m_0\cdots m_{k-1}$. The Chinese remainder theorem states: $$\varphi:R\to R/(m_0)\times\cdots \times R/(m_{k-1})\;,\;\;\;\alpha\mapsto \left(\kappa_0(\alpha),\ldots,\kappa_{k-1}(\alpha)\right)$$ is a surjective ring homomorphism, where $$\kappa_i:R\to R/(m_i)\;,\;\;\;\alpha\mapsto \alpha\text{ mod }m_i$$ is the canonical isomorphism, and thereby induces an ring isomorphism $$R/(m)\to R/(m_0)\times\cdots \times R/(m_{k-1})$$

This result can be transferred to the special case $R=\mathbb{K}[X]$, where $\mathbb{K}$ is a field. Therefore, let $\xi_0,\ldots, \xi_{k-1}\in\mathbb{K}$ be pairwise distinct and $m_i:=X-\xi_i$ (thus, $m_0,\ldots,m_{k-1}$ are pairwise coprime).

How exactly does the existence of a ring isomorphism $$\chi:\mathbb{K}[X]/(m)\to\mathbb{K}^n\;,\;\;\;f\text{ mod }m\mapsto \left(f(\xi_0),\ldots,f(\xi_{k-1})\right)$$ follow from the Chinese remainder theorem? I can't see it. Please explain it by using the notion in the statement of the Chinese remainder theorem above.

• @user26857 Sorry, what I meant was "distinct". – 0xbadf00d Aug 25 '14 at 11:12

## 1 Answer

If $\xi_1\ldots,\xi_k$ are pairwise distinct, then the ideals $(x-\xi_1),\ldots,(x-\xi_k)$ are pairwise coprime, and by the theorem we have an isomorphism$$\chi:\mathbb{K}[x]/\Pi (x-\xi_i)\to\prod\mathbb{K}/(x-\xi_i)\simeq\mathbb{K}^k.$$ The only thing left to be said is that for any polynomial $f\in\mathbb{K}[x]$ and for any $\xi\in\mathbb{K}$ we have $f-f(\xi)\in(x-\xi)$ (see explanation below), or in other words, when dividing $f$ by $(x-\xi)$ the remainder is equal to $f(\xi)$. Thus the canonical map $\mathbb{K}[x]\to\mathbb{K}[x]/(x-\xi)\simeq\mathbb{K}$ is given by $f\mapsto f(\xi)$.

We explain why $f-f(\xi)\in(x-\xi)$. Denote $g=f-f(\xi)$, and immediately get $g(\xi)=0$. Since $\mathbb{K}[x]$ is Euclidean, we can write $g=p(x-\xi)+r$, where $r$ has degree smaller than that of $(x-\xi)$. As the latter is linear, $r$ is a constant. As $g(\xi)=0,$ the previous equation implies $r=0$, thus $$f-f(\xi)=g=p(x-\xi)\in(x-\xi).$$

• For any $f\in\mathbb{K}[X]$ and for any $\xi\in\mathbb{K}$ we have $$f-f(\xi)\in (X-\xi)$$ That's the whole point. I don't understand why this holds. – 0xbadf00d Aug 25 '14 at 10:01
• I added an explanation to the answer, check it out. – Amitai Yuval Aug 25 '14 at 10:18
• That was easy. Thanks a lot. – 0xbadf00d Aug 25 '14 at 10:22