## Solving simultaneous polynomial congruences

Let $\{f_i(x)\}_{i=1}^k$ be polynomials in $\mathbb{Z}[x]$, all of degree $d$. Let $\{n_i\}_{i=1}^k$ be pairwise relatively prime integers. Use the Chinese Remainder Theorem to prove that there exists a polynomial $f(x) \in \mathbb{Z}[x]$ of degree $d$ such that $f(x) \equiv f_i(x) \mod n_i$ for each $i$ – that is, the coefficients of $f(x)$ and $f_i(x)$ agree mod $n_i$. Show also that if the $f_i(x)$ are all monic, then $f(x)$ may be chosen monic.

We begin with some lemmas.

Lemma 1: Let $R$ be a ring, and let $I,J \subseteq R$ be ideals. Then $(I+J)[x] = I[x] + J[x]$. Proof: $(\supseteq)$ is clear, since $I[x], J[x] \subseteq (I+J)[x]$. $(\subseteq)$ Let $\alpha = \sum (a_i+b_i)x^i \in (I+J)[x]$. Then $\alpha = \sum a_ix^i + b_ix^i$ $= (\sum a_ix^i) + (\sum b_ix^i)$ $\in I[x] + J[x]$. $\square$

Lemma 2: Let $R$ be a ring, and let $I,J \subseteq R$ be ideals. Then $(I \cap J)[x] = I[x] \cap J[x]$. Proof: Certainly $I[x] \cap J[x] \subseteq (I \cap J)[x]$. Now if $\alpha = \sum a_ix^i \in (I \cap J)[x]$, then $\alpha \in I[x]$ and $\alpha \in J[x]$, so that $\alpha \in I[x] \cap J[x]$. $\square$

Note that the ideals $(n_i)$ are pairwise comaximal. By Lemma 1, the ideals $(n_i)[x]$ are pairwise comaximal in $\mathbb{Z}[x]$. By the Chinese Remainder Theorem, the map $\varphi : \mathbb{Z}[x] \rightarrow \prod \mathbb{Z}[x]/(n_i)[x] \cong \prod (\mathbb{Z}/(n_i))[x]$ given by $\varphi(f(x)) = (\overline{f}(x))$ is a surjective ring homomorphism. Thus, given $(f_i(x)) \in \prod (\mathbb{Z}/(n_i))[x]$, there exists $f(x) \in \mathbb{Z}[x]$ such that $\varphi(f(x)) = (f_i(x))$.

Suppose that each of the $f_i(x)$ are monic- that is, the leading coefficient of $f_i(x)$ is congruent to 1 mod $n_i$. By the previous exercise, there is an integer $a \in \mathbb{Z}$ which is congruent to 1 mod $n_i$ for all $i$. The solution $f(x)$ above is unique only modulo $(n)[x]$, and thus we can choose the leading coefficient of $f(x)$ to be 1.