# Adapting the Chinese Remainder Theorem (CRT) for integers to polynomials

I did a few examples using the CRT to solve congruences where everything was in terms of integers. I'm trying to use the same technique for polynomials over $$\mathbb{Q}$$, but I'm getting stuck.

Here's an example with integers:

$$\begin{cases}x \equiv 1 \, (\mathrm{mod} \, 5) \\ x \equiv 2 \, (\mathrm{mod} \, 7) \\ x \equiv 3 \, (\mathrm{mod} \, 9) \\ x \equiv 4 \, (\mathrm{mod} \, 11). \end{cases}$$

Since all the moduli are pairwise relatively prime, we can use the CRT. Here's some notation I'm using:

$$\bullet \, M$$ denotes the product of the moduli (in this case, $$M = 5 \cdot7 \cdot 9 \cdot 11$$)

$$\bullet \, m_i$$ denotes the modulus in the $$i^{\mathrm{th}}$$ congruence

$$\bullet \, M_i$$ denotes $$\dfrac{M}{m_i}$$

$$\bullet \, y_i$$ denotes the inverse of $$M_i$$ (mod $$m_i$$), i.e. $$y_i$$ satisfies $$y_i M_i \equiv 1$$ (mod $$m_i$$).

Then $$x = \displaystyle \sum_{i = 1}^n a_iM_iy_i$$, and this solution is unique (mod $$M$$).

Now I want to apply the same technique to the following:

$$\begin{cases} f(x) \equiv 1 \, (\mathrm{ mod } \, x^2 + 1) \\ f(x) \equiv x \, (\mathrm{mod} \, x^4), \end{cases}$$

where $$f(x) \in \mathbb{Q}(x)$$. Having checked that the moduli are relatively prime, we should be able to use the CRT. Using the notation above, I have the following:

$$M = (x^4)(x^2 + 1)$$

$$M_1 = x^4$$

$$M_2 = x^2 + 1$$

Here's where I run into a problem. I need to find $$y_1, y_2$$ such that

$$\begin{cases} y_1 (x^4) \equiv 1 \, (\mathrm{mod} \, x^2 + 1) \\ y_2 (x^2+1) \equiv 1 \, (\mathrm{mod} \, x^4). \end{cases}$$

But how does one find $$y_1, y_2$$?

• "Having checked that the moduli are relatively prime..." but that means precisely that there exist $p_1(x)$ and $p_2(x)$ such that $p_1(x)x^4 + p_2(x)(x^2+1)=1$. – kccu Apr 21 at 19:23
• Are you saying that I can find $p_1(x)$ and $p_2(x)$ in general by using the extended Euclidean algorithm, and that $p_1(x)$ and $p_2(x)$ are precisely my $y_1$ and $y_2$? – Junglemath Apr 21 at 19:56

To find $$y_1$$ and $$y_2$$ consider solving the problem $$y_1x^4+y_2(x^2+1)=1.$$ This is not always easy to solve, but in this case a solution comes to mind. Note that by difference of squares $$(x^2-1)(x^2+1)=x^4-1,$$ hence $$x^4+[(-1)(x^2-1)](x^2+1)=1.$$ This tells us that we can choose $$y_1=1,$$ $$y_2=(1-x^2).$$

• Is there an algorithmic way of solving these, rather than relying on intuition? – Junglemath Apr 21 at 19:59
• @Junglemath By Euclidean algorithm you can find two polynomials $p(x), q(x) \in \mathbb{Q}[x]$ such that $p(x) x^4 + q(x) (x^2 + 1) = 1$. – Paolo Apr 21 at 20:09
• @Junglemath The polynomials over a field form a Euclidean Domain, so yes, there is. If the gcd of $f_1,f_2\in\mathbb{Q}[x]$ is a unit, then you can perform the Euclidean Algorithm to find their gcd. Now, you can reverse the algorithm to write them as a linear combination of their gcd the same way you would for integers. I said not easy, because the process can be time consuming and very tedious. – Melody Apr 21 at 20:10
• @Junglemath I didn't really convert it. I knew in advanced the single equation had a solution. This is because $x^4$ and $x^2+1$ have no common roots, hence no common irreducible factors. This means they are relatively prime, in which case we can write $1$ as a linear combination. Knowing that, I knew solving the single equation would give rise to a solution to the congruence equations. This is completely analogous to how you can solve everything over the integers. – Melody Apr 21 at 20:22
• @Junglemath I describe here at length this method of scaling the Bezout equation into a CRT solution. – Bill Dubuque Apr 21 at 21:28

Bu applying $$\ ab\bmod ac\, =\, a(b\bmod c)\$$ [Mod Distributive Law]  it is a bit simpler:

$$f-x\,\bmod\, {x^{\large 4}(x^{\large 2}\!+\!1)}\, =\, x^{\large 4}\underbrace{{\left[\dfrac{\color{#c00}f-x}{\color{#0a0}{x^{\large 4}}}\bmod {x^{\large 2}\!+\!1}\right]}}_{\large \color{#0a0}{x^{\Large 4}} \ \equiv\ 1\ \ \ {\rm by}\ \ \ x^{\Large 2}\ \equiv\ \ -1 } =\, x^{\large 4}[1-x],\$$ by $$\,\color{#c00}f\equiv 1\pmod{\!x^{\large 2}\!+\!1}$$

Remark  Here are further examples done using MDL (an operational form of CRT).

You can find further details here on transforming the Bezout equation into a CRT solution (the method sketched in Melody's answer).