Remainder of polynomial product, CRT solution via Bezout

Question

Given: $$f(x) \pmod{x^2 + 4} = 2x + 1$$ $$f(x) \pmod{x^2 + 6} = 6x - 1$$

Define r(x) as: $$f(x) \pmod{(x^2 + 4)(x^2+6)} = r(x)$$

What is $r(4)$?

---

The 3 equations can be restated as quotient · divisor + remainder:

$$f(x) = a(x)(x^2 + 4) + 2x + 1 $$ $$f(x) = b(x)(x^2 + 6) + 6x - 1 $$ $$f(x) = c(x)(x^2 + 4)(x^2 + 6) + r(x) = c(x)(x^4 + 10x^2 + 24) + r(x) $$

---

Note this isn't homework, and there are several different methods that can be used to solve this, one of which produces an f(x) based on the 2 given remainders, two of which produce r(x) without having to determine f(x), and a slight variation that produces r(4). I've looked at other polynomial remainder questions here at SE, but those did not involve all of the methods that I'm aware of that can be used to solve this particular problem, so I thought it might be interesting for others here at SE. Some, but not all of the methods are related to Chinese remainder theorem, so I wasn't sure if should also tag this question with Chinese remainder theorem. I found this problem at another forum site, so I'm not sure of the origins of this particular problem.

Answer 1

Hint $ $ We can read off a CRT solution from the Bezout equation for the gcd of the moduli, viz. $$\bbox[5px,border:1px solid #c00]{\text{$\color{#90f}{\text{scale}}$ the Bezout equation by the residue difference - then ${\rm \color{#c00}{re}\color{#0a0}{arrange}}$}}$$ $$\begin{align} {\rm if}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\begin{array}{rr} &f\equiv\, f_g\pmod{\!g}\\ &f\equiv\, f_h\pmod{\! h} \end{array}\ \ {\rm and}\ \ \gcd(g,h) = 1\\[.4em] {\rm then}\ \ \ f_g - f_h\, &=:\ \delta\qquad\qquad\ \ \rm residue\ difference \\[.2em] \times\qquad\quad\ \ \ 1\ &=\ \ a g\, +\, b h\quad\ \rm Bezout\ equation\ for \ \gcd(g,h) \\[.5em]\hline \Longrightarrow\ \,f_g\, \color{#c00}{-\, f_h}\, &= \color{#0a0}{\delta ag} + \delta bh\quad\ \rm product\ of \ above\ (= {\color{#90f}{scaled}}\ Bezout)\\[.2em] \Longrightarrow \underbrace{f_g \color{#0a0}{- \delta ag}}_{\!\!\!\large \equiv\ f_{\large g}\! \pmod{\!g}}\! &= \underbrace{\color{#c00}{f_h} + \delta bh}_{\large\!\! \equiv\ f_{\large h}\! \pmod{\!h}}\ \ \ \underset{\large {\rm has\ sought\ residues}\phantom{1^{1^{1^{1^1}}}}\!\!\!}{\rm \color{#c00}{re}\color{#0a0}{arranged}\ product}\rm\! = {\small CRT}\ solution\end{align} $$

More generally: $ $ if the gcd $\,d\neq 1\,$ then it is solvable $\iff d\mid f_g-f_h\,$ and we can use the same method we used below for $\,d=\color{#c00}2\!:\,$ scale the Bezout equation by $\,(f_g-f_h)/d = \delta/d.\,$ Since $\,\color{#c00}2\,$ is invertible in the OP, we could have scaled the Bezout equation by $\,1/2\,$ to change $\,\color{#c00}2\,$ to $\,1,\,$ but not doing so avoids (unneeded) fractions so simplifies the arithmetic.

In our specific problem we have the major simplification that the Bezout equation is obvious being simply the moduli difference $ =\color{#c00}2$
hence $\ \ \smash[t]{\overbrace{\color{0a0}{6x\!-\!1}-\color{#90f}{(2x\!+\!1)}}^{\rm residue\ difference}} = \overbrace{(2x\!-\!1)}^{\!\text{scale LHS}}\,\overbrace{\color{#c00}2 = (\color{0a0}{x^2\!+\!6}-\color{#0a0}{(x^2\!+\!4)}}^{{\overbrace{\textstyle\color{#c00}2\, =\, x^2\!+\!6-(x^2\!+\!4)_{\phantom{|_{|_i}}}\!\!\!\!}^{\Large \text{Bezout equation}}}})\overbrace{(\color{#0a0}{2x\!-\!1})}^{\text{scale RHS}},\ $ which rearranged

yields $\ \ \underbrace{\color{}{6x\!-\!1 - (\color{#0a0}{2x\!-\!1})(x^2\!+\!6)}}_{\large \equiv\ \ 6x\ -\ 1\ \pmod{x^2\ +\ 6}\!\!\!}\, =\, \underbrace{\color{#90f}{2x\!+\!1} -\color{#0a0}{(2x\!-\!1)(x^2\!+\!4)}}_{\large \equiv\ \ 2x\ +\ 1\ \pmod{x^2\ +\ 4}\!\!\!} =\,r(x) =\, $ CRT solution.

---

Remark $ $ If ideals and cosets are familiar then the above can be expressed more succinctly as

$$ \bbox[12px,border:2px solid #c00]{f_g\! +\! (g)\,\cap\, f_h\! +\! (h) \neq \phi \iff f_g-f_h \in (g)+(h)}\qquad$$

Answer 2

Hint

Observe that $\gcd(x^2+4, x^2+6)=1$ and $$\frac{1}{2}(x^2+6)-\frac{1}{2}(x^2+4)=1.$$ Now apply Chinese remainder theorem to the system \begin{align*} f(x) & \equiv 2x+1 \pmod{x^2+4}\\ f(x) & \equiv 6x-1 \pmod{x^2+6} \end{align*} To get something like: $$f(x) \equiv \underbrace{(2x+1)(\ldots) + (6x-1)(\ldots)}_{r(x)} \pmod{(x^2+4)(x^2+6)}.$$

Answer 3

I'm posting an "answer" for alternative methods. The third method below is the most straight forward, exploiting the fact that $(x^2+6)-(x^2+4) = 2$. The answer to the question, r(4) = -131.

Using a "reverse" long division process to produce a common f(x) based on the first two given equations will work, but, although this solves the problem, I doubt that is the intended solution, since it involves a reasoned trial and error search for f(x) (sort of an optimized brute force search), and it is my impression that a proper answer should be able to solve for r(x) or specifically for r(4) without having to determine f(x).

Below is what the process looks like. f(x) (the dividend) and the quotients a(x), b(x) are unknown. The divisors and remainders are given in the first two equations of the question. You start at the bottom of these two long hand divisions in parallel, working upwards to produce a common f(x).

As mentioned, this is a reasoned trial an error process. For example, my first attempt at the x^2 term of f(x) was 13x^2, which failed later, the second attempt was 25x^2, which worked (at least it produces a common f(x) that satisfies the first two equations). For the rest of the terms, the first attempts at terms for a common f(x) (and the corresponding quotient terms of a(x) and b(x)) worked.

Consider the very first step, f(x) / (x^2+4) has remainder ...+1, f(x) / (x^2+6) has remainder ...-1. This suggests that the last term of f(x) is 5 and the last terms of both quotients are 1, since 5-4 = +1 and 5-6 = -1. The x terms in the remainder show that after subtraction from the third step from the bottom, x terms are 2x for division by (x^2+4) and 6x for division by (x^2+6), and setting the x term of f(x) to 18 works as 18 - (4·4) = 2 and 18 - (2·6) = 6. The process is continued upwards, looking for common f(x) terms that satisfy both long hand divisions. This is the final result. Again note that this process is started at the bottom and worked upwards to produce a common f(x) (dividend) for both divisors:

              1  1  6  4  1                   1  1  4  2  1
      ---------------------           ---------------------
1 0 4 | 1  1 10  8 25 18  5     1 0 6 | 1  1 10  8 25 18  5
        1  0  4                         1  0  6
           1  6  8                         1  4  8
           1  0  4                         1  0  6       
              6  4 25                         4  2 25
              6  0 24                         4  0 24
                 4  1 18                         2  1 18                  
                 4  0 16                         2  0 12   
                    1  2  5                         1  6  5
                    1  0  4                         1  0  6
                       2  1                            6 -1

Once any f(x) is determined that satisfies the first two given equations, then the rest just requires normal division.

$$f(x) = x^6 + x^5 + 10 x^4 + 8 x^3 + 25 x^2 + 18 x + 5$$

Expressing f(x) as quotient · divisor + remainder for the different divisors:

$$f(x) = (x^4 + x^3 + 6x^2 + 4x + 1)(x^2 + 4) + 2x + 1 $$ $$f(x)= (x^4 + x^3 + 4x^2 + 2x + 1)(x^2 + 6) + 6x - 1 $$ $$f(x) = (x^2 + x)(x^4 + 10x^2 + 24) -2 x^3 + x^2 - 6 x + 5 $$

---

Using typical remainder theorem approach f(x) evaluated at the 4 roots of (x^2+4)(x^2+6): $$f(x) = c(x))(x^2+4)(x^2+6)) = r(x)$$ $$f(x) = (c(x) · 0) + r(x) = r(x)$$ f(x) evaluated at the 2 roots of (x^2+4): $$f(x) = (a(x) · 0) + 2x + 1) = 2x + 1$$ f(x) evaluated at the 2 roots of (x^2+6): $$f(x) = (b(x) · 0) + 6x - 1) = 6x - 1$$ This leads to 4 data points for r(x): $${-(2)i,-(4)i+1}$$ $${+(2)i,+(4)i+1}$$ $${-\sqrt{6}i,-(6)\sqrt{6}i-1}$$ $${-\sqrt{6}i,-(6)\sqrt{6}i-1}$$

Using Lagrange interpolation to solve for r(x) is complicated due to the complex numbers:

r(x) = ((x-x1)(x-x2)(x-x3)(y0))/((x0-x1)(x0-x2)(x0-x3)) +
       ((x-x0)(x-x2)(x-x3)(y1))/((x1-x0)(x1-x2)(x1-x3)) +
       ((x-x0)(x-x1)(x-x3)(y2))/((x2-x0)(x2-x1)(x2-x3)) +
       ((x-x0)(x-x1)(x-x2)(y3))/((x3-x0)(x3-x1)(x3-x2)) +

grinding the 4 terms leads to:

r(x) = (1/2 + i/8) (x^3 - 2 i x^2 + 6 x - 12 i) +
       (1/2 - i/8) (x^3 + 2 i x^2 + 6 x + 12 i) +
       1/24 (( i sqrt(6) - 36) x + 36 i sqrt(6) + 6) (x^2 + 4) +
       1/24 ((-i sqrt(6) - 36) x - 36 i sqrt(6) + 6) (x^2 + 4)
r(x) =    x^3 + 1/2 x^2 +  6 x + 3 +
       -3 x^3 + 1/2 x^2 - 12 x + 2
r(x) = -2 x^3 +     x^2 -  6 x + 5

---

Exploiting the fact that $(x^2+6) - (x^2+4) = 2$ :

$$f(x) = a(x)(x^2+4)+(2x+1)$$ $$f(x) = b(x)(x^2+6)+(6x-1)$$ multiply 1st equation by $(x^2+6)$ and 2nd equation by $(x^2+4)$ $$f(x)(x^2+6) = a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)$$ $$f(x)(x^2+4) = b(x)(x^2+4)(x^2+6)+(6x-1)(x^2+4)$$ subtracting 4th equation from 3rd: $$2f(x) = a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)-b(x)(x^2+4)(x^2+6)-(6x-1)(x^2+4)$$ $$f(x) = (1/2)(a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)-b(x)(x^2+4)(x^2+6)-(6x-1)(x^2+4))$$ $$f(x) mod((x^2+4)(x^2+6)) = r(x) = (1/2)((2x+1)(x^2+6) - (6x-1)(x^2+4))$$ $$r(x) = -2x^3 + x^2 - 6x + 5$$