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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: