# Find the remainder when $f(x)$ divided by $(x^2 + x + 1)(x+1)$.

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.

• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Sep 24 '17 at 14:51
• 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. – Arthur Sep 24 '17 at 14:51

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.

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

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

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}

• @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. – Bill Dubuque Sep 25 '17 at 14:34

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

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}