1
$\begingroup$

When a polynomial $f(x)$ is divided by $x^2 + x + 1$ and $(x+1)^2$, the remainder are $x+5$ and $x-1$ respectively. Find the remainder when $f(x)$ is divided by $(x^2 + x + 1)(x+1)$.

First, I let the remainder be $Ax^2 + Bx +C$, then I try to find the values of $A$, $B$ and $C$. There is $3$ unknowns so we need three equations but I can only get two equations.

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Sep 24 '17 at 14:51
  • 1
    $\begingroup$ Which equations did you get, and how did you get them? Also note that an equation like $5x + 3 = Ax+B$ is actually two-in-one, since what we have is an equality of functions, so each coefficient must be equal. I assume that will give you the third one you're looking for. $\endgroup$ – Arthur Sep 24 '17 at 14:51
1
$\begingroup$

Hint $\ f = x\!+\!5 + \color{#c00}c\,(\overbrace{x^2\!+\!x\!+\!1}^{\large g})\ $ and $\ {-}2 = \color{#0a0}{f\bmod x\!+\!1} = f(-1) = 4\!+\!c\iff \color{#c00}{c = -6}$


Remark $\,\ $ Or use $\,\ fg\bmod hg\, =\, (f\bmod h)g\,= $ mod Distributive Law $ $ algorithmically

$$\,\ \ \begin{align} f-(x\!+\!5)\ \bmod\ (x\!+\!1)g\, =\ &\left[\dfrac{f-(x\!+\!5)}{g}\bmod\, x\!+\!1\right]g\ \ \ {\rm by}\ \ \ f\equiv x\!+\!5\!\!\!\pmod{\!g}\\[.3em] =\ &\left[\dfrac{f(-1)-4}{1}\right]g\ \ \ \,{\rm by}\ \ \ g\bmod x\!+\!1 = g(-1) = 1\\[.3em] =\ &[\color{#c00}{\,-6}\,]\,g\ \ \ {\rm by}\ \ f(-1)=\color{#0a0}{f\bmod x\!+\!1} = x\!-\!1\bmod x\!+\!1 = -2 \end{align}$$

Note that we did not need to solve any equations - only evaluate polynomials at $\,x=-1$
The same method works generally:

Lemma $\,\ f\bmod (x\!-\!a)g\, =\, f_g + \left[\dfrac{f(a)- f_g(a)}{g(a)}\right]g\ \ $ if $\ g(a)\neq 0,\,$ for $\,f_g = f\bmod g$

$\begin{align}{\bf Proof}\ \ f-f_g\ \bmod\ (x\!-\!a)g\, =\ &\left[\dfrac{f-f_g}{g}\bmod\, x\!-\!a\right]g\\[.3em] =\ &\left[\dfrac{f(a)-f_g(a)}{g(a)}\right]g \end{align}$

The formula does not require solving equations, only evaluating a few polynomials at $\,x=a$

Note $ $ The $\!\bmod\!$ Distributive Law can be viewed as an equivalent "shifty" operational reformulation of CRT = Chinese Remainder Theorem, as I explain in the end of my Remark here. It is often more convenient to apply in practice because of its operational nature, e.g. here are many examples.

$\endgroup$
0
$\begingroup$

$$p(x)\equiv (x-1)\pmod{(x+1)^2} $$ implies $p(x)\equiv (x-1) \equiv -2 \pmod{(x+1)}$. We know that $p(x)\equiv(x+5)\pmod{x^2+x+1}$, or $$ p(x) = (x+5) + (x^2+x+1) r(x) $$ hence $$ p(x) \equiv 4 + r(x)\pmod{(x+1)}$$ and $r(x)\equiv -6\pmod{(x+1)}$. It follows that $$ p(x) = (x+5)+(x^2+x+1)(-6+(x+1)s(x)) $$ and $$ p(x)\equiv \color{red}{(x+5)-6(x^2+x+1)} \pmod{(x+1)(x^2+x+1)}.$$

$\endgroup$
0
$\begingroup$

We know that $$f(x)=Q_1(x)(x^2 + x + 1)+x+5=Q_2(x)(x+1)^2+x-1$$ for some polynomials $Q_1$ and $Q_2$. Moreover, for some polynomial $Q_3$, $$f(x)=Q_3(x)(x^2 + x + 1)(x+1)+Ax^2+Bx+C.$$ Hence $$f(-1)=-1-1=A(-1)^2+B(-1)+C.$$ Now consider the complex zeros $w_1$ and $w_2$ of $x^2 + x + 1$. Then $$f(w_1)=w_1+5=Aw_1^2+Bw_1+C\quad,\quad f(w_2)=w_2+5=Aw_2^2+Bw_2+C.$$ By solving the linear system of the three equations we find that $A = -6$, $B = -5$, $C = -1$.

$\endgroup$
0
$\begingroup$

Using the Generalized Euclidean Algorithm, we get $$ (x+2)\left(x^2+x+1\right)-(x+1)(x+1)^2=1\tag1 $$ Therefore, we have $$ \begin{align} (x+2)\left(x^2+x+1\right)&\equiv1&&\pmod{(x+1)^2}\\ (x+2)\left(x^2+x+1\right)&\equiv0&&\pmod{x^2+x+1} \end{align}\tag2 $$ and $$ \begin{align} -(x+1)(x+1)^2&\equiv0&&\pmod{(x+1)^2}\\ -(x+1)(x+1)^2&\equiv1&&\pmod{x^2+x+1} \end{align}\tag3 $$ Thus, to get $$ \begin{align} f(x)&\equiv x-1&&\pmod{(x+1)^2}\\ f(x)&\equiv x+5&&\pmod{x^2+x+1} \end{align}\tag4 $$ we can use $x-1$ times $(2)$ plus $x+5$ times $(3)$ to get $\bmod{(x+1)^2\left(x^2+2x+1\right)}$ $$ \begin{align} f(x) &\equiv(x-1)(x+2)\left(x^2+x+1\right)-(x+5)(x+1)(x+1)^2\\ &=-6x^3-18x^2-17x-7\\ &\equiv-6x^2-5x-1\pmod{(x+1)\left(x^2+2x+1\right)}\tag5 \end{align} $$

$\endgroup$
  • $\begingroup$ @Readers No doubt we can mechanically solve any congruence system using one of the many formulations of CRT (e.g. the above Bezout-based method). But computing it mechanically typically inhibits optimizations that exploit any innate special structure that the problem may possess - structure which may yield significant simplifications. For example. here one of the moduli is linear, which greatly simplifies matters - reducing the computation to a single line, e.g. see my answer. $\endgroup$ – Bill Dubuque Sep 25 '17 at 14:34
0
$\begingroup$

The remainder when dividing by $(x+1)^2$ was $x-1$, so the remainder when dividing by just $x+1$ must be $-2$.

We know that $f(x)$ is of the form $$ f(x) = q(x)(x^2 + x + 1)(x+1) + Ax^2 + Bx + C $$ where $q(x)$ is a polynomial and $Ax^2 + Bx + C$ has the same remainders as $f$ does when divided by $x+1$ and by $x^2 + x + 1$. Now we just calculate: $$ \frac{Ax^2 + Bx + C}{x+1} = Ax + B-A+\frac{C-B+A}{x+1} $$ so we must have $C-B+A = -2$. That's one equation down. Now we deal with $x^2 + x + 1$: $$ \frac{Ax^2 + Bx + C}{x^2 + x + 1} = Ax + \frac{(B-A)x + C-A}{x^2 + x + 1} $$ so we know that $(B-A)x + C-A = x+5$. As I alluded to in the comments to the question above, this is actually two equations in one, as this is an equality of functions. The slopes must be equal, and the constant terms must be equal. This gives you the remaining two equations $B-A = 1$ and $C-A = 5$.

$\endgroup$
0
$\begingroup$

Write $$ f(x)=k(x)(x^2+x+1)+x+5$$

and $$ f(x)=q(x)(x+1)^2+x-1 \Longrightarrow f(-1) = -2$$

So $$-2 = f(-1) = k(-1)\cdot 1 +4 \Longrightarrow k(-1) = -6$$

thus

$$ k(x) = p(x)(x+1)-6 $$ and finally \begin{eqnarray} f(x) &= &(p(x)(x+1)-6)(x^2+x+1)+x+5 \\ &=& p(x)(x+1)(x^2+x+1)-6x^2-5x-1 \end{eqnarray}

$\endgroup$

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.