4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please give some context, in particular, tell us what you've tried so far, including anything you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks. $\endgroup$ – John Omielan Apr 4 at 4:56
  • $\begingroup$ @JohnOmielan - this problem is already solved, but depending on the method used to solve it, there are some difficulties that can be overcome by altering the approach, which I thought might be interesting to others here at SE. $\endgroup$ – rcgldr Apr 4 at 7:16
  • $\begingroup$ Thanks for your response & question text update. Please initially include any such context in your future questions. $\endgroup$ – John Omielan Apr 4 at 7:33
  • $\begingroup$ @JohnOmielan - brain fade on my part, I was in the process of composing the context when I got called away and forgot to go back and copy / paste the context into my question. I'll pay more attention next time. $\endgroup$ – rcgldr Apr 4 at 8:10
  • $\begingroup$ Please give details on the other methods you mention. $\endgroup$ – Bill Dubuque Apr 4 at 18:24
3
$\begingroup$

Hint $ $ We can read off a CRT solution from the Bezout equation for the gcd of the moduli, viz. scale the Bezout equation by the residue difference - then rearrange. Here the Bezout equation is obvious

$$ \color{#c00}2\, =\, x^2\!+\!6-(x^2\!+\!4)\quad\, $$

Hence $\ \smash[t]{\overbrace{\color{#0a0}{6x\!-\!1}-(2x\!+\!1)}^{\rm residue\ difference}} = (2x\!-\!1)\,\color{#c00}2 = (\color{#0a0}{2x\!-\!1})(\color{#0a0}{x^2\!+\!6}-(x^2\!+\!4)),\ $ which rearranged

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

Remark $ $ For completeness below is the method in general

$${\rm if}\ \ \begin{align} &f\equiv\, f_g\!\!\pmod{g}\\ &f\equiv\, f_h\!\!\pmod h\end{align}\ \ {\rm and}\ \ \gcd(g,h) = 1\ \ \rm then\qquad\qquad\qquad $$

$$\begin {align} f_g - f_h\, &=:\ \delta\qquad\qquad\ \ \rm residue\ difference \\[.2em] \times\qquad\quad\ \ \ 1\ &=\ \ a g\, +\, b h\quad\ \rm Bezout\ equation \\[.5em]\hline \Rightarrow\ \,f_g\, \color{#c00}{-\, f_h}\, &= \color{#0a0}{\delta ag} + \delta bh\quad\ \rm product\ of \ above\ (scaled\ Bezout)\\[.2em] \Rightarrow \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 CRT\ solution}\ f\phantom{1^{1^{1^{1^1}}}}}{\rm \color{#c00}{re}\color{#0a0}{arranged}\ product}\end{align}\quad $$

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 above 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 avoiding fractions simplified the arithmetic.

If you are familiar with ideals and cosets then the above can be expressed more succinctly as

$$ f_g\! +\! (g)\,\cap\, f_h\! +\! (h) \neq \phi \iff f_g-f_h \in (g)+(h)\qquad\qquad $$

$\endgroup$
  • $\begingroup$ So simple it can all be all be done purely mentally in a minute once you grasp the key idea that scaling the Bezout equation by the residue difference - then rearranging - yields the CRT solution. $\endgroup$ – Bill Dubuque Apr 6 at 19:38
  • $\begingroup$ Good answer. You might want to enclose 2x-1, 2x+2, 6x-1 and x^2+6 in parenthesis for consistency. $\endgroup$ – rcgldr Apr 6 at 21:43
  • $\begingroup$ @rcgldr The paren's are used only when needed (standard algebraic syntax / operator precedence), I don't distribute the negative sign into $\,{-}(2x+1)\,$ etc because this makes the rearranging clearer - just negate the single sign factor when moving it to the opposite side of the equation. Also it preserves the form of the moduli and residues - making it clearer how the method works in general. $\endgroup$ – Bill Dubuque Apr 6 at 22:04
  • $\begingroup$ Since the original question only asks about r(4), there should be a path or insight to conclude r(x) = (d(x))(x^2+4)+(2x+1) = (d(x))(x^2+6)+(6x-1). Then 11 · (1st equation) - 10 · (2nd equation) = (d(x))(x^2-16) + 11(2x+1) - 10(6x-1), and for x = 4, r(4) = (d(4)·0) + 11(2·4+1) - 10(6·4-1) = -131, without having to determine d(x). I was planning on adding this as a fourth method on my answer. $\endgroup$ – rcgldr Apr 7 at 23:57
  • $\begingroup$ @rcgldr Evaluating $\, r = f_g- \delta ag = 2x\!+\!1 - (2x\!-\!1)(x^2\!+\!4)\,$ at $\,x=4\,$ is already extremely simple. I doubt you'll find anything much simpler than that (assuming the Bezout equation is known). $\endgroup$ – Bill Dubuque Apr 8 at 1:10
2
$\begingroup$

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)}.$$

$\endgroup$
  • $\begingroup$ The question has been updated with context I initially forgot to include, that the problem is already solved using several methods. So assuming that r(x) = (2x+1)(a(x)) + (6x-1)(b(x)), how would you determine a(x) and b(x)? $\endgroup$ – rcgldr Apr 4 at 15:26
  • $\begingroup$ There is a method that starts with 1/2(x^+6) - 1/2(x^2+4) = 1 to end up with r(x) = (2x+1)(...) + (6x-1)(...), but I'm wondering if the approach you are considering is the same. $\endgroup$ – rcgldr Apr 6 at 8:34
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ The last method essentially rederives one form of CRT, namely if $\,\gcd(g,h)=1\,$ then $$\large \begin{align} &f\equiv f_g\!\!\pmod{g}\\ &f\equiv f_h\!\!\pmod{h}\end{align} \iff f \equiv \dfrac{ f_g\, h - f_h\,g}{\color{#c00}{\ h\,-\,g}}\!\!\pmod{\!gh}$$ This is particularly simple here because $\,\color{#c00}{h - g} = x^2+6-(x^2+4) = \color{#c00}2\,$ is trivially invertible. $\ \ $ $\endgroup$ – Bill Dubuque Apr 8 at 2:31
  • $\begingroup$ @BillDubuque - true, but I was unaware of CRT when I first did the last method. I was just looking for some way to remove a(x), b(x), and c(x) from the equations. $\endgroup$ – rcgldr Apr 8 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.