# Remainder Theorem Technique

Determine the remainder when $$(x^4-1)(x^2-1)$$ is divided by $$1 + x + x^2$$ (HMMT 2000, Guts Round)

A. Write the division in the form: $$(x^4-1)(x^2-1)= (1 + x + x^2)Q(x) + R(x)$$

B. Multiply both sides by $$x-1$$: $$(x-1)(x^4-1)(x^2-1)= (x^3-1)Q(x) + R(x)(x-1)$$

C. Substitute $$x^3=1,x\neq1$$, and reduce the resulting equation:

$$(x-1)(x-1)(x^2-1)= R(x)(x-1)$$

D. Divide both sides by $$x-1$$: $$R(x)=(x-1)(x^2-1)=x^3 -x - x^2 + 1=-(x^2+x+1)+3=3$$

For someone who knows the method, is it valid to skip Steps B and D, directly substitute $$x^3=1,x\neq1$$ and use the fact that $$x$$ is a cube root of unity to get $$x^2+x+1=0$$.

• Yeah, you don’t need steps B and D. $x^4-x$ is divisible by $x^3-1$ which is divisible by $x^2+x+1.$ Commented Aug 31, 2021 at 4:01
• @ThomasAndrews What about x^2+x+1=0. Can you do that directly? Commented Aug 31, 2021 at 4:02
• Sure, you can do that. Commented Aug 31, 2021 at 4:09

Yes, you can skip those steps.

The verbose equivalent is that \begin{align}(x^4-1)(x^2-1)&=(x^4-x)(x^2-1)+(x-1)(x^2-1)\\ &=(x^2+x+1)x(x-1)(x^2-1)+(x-1)(x^2-1) \end{align}

So $$(x-1)(x^2-1)$$ has the same remainder as $$(x^4-1)(x^2-1)$$ when dividing by $$x^2+x+1.$$

Answering the question in comments, yes, you can replace $$x^2+x+1$$ with zero.

Here, you can write:

$$(x-1)(x^2-1)=(x-1)(x^2+x+1)-(x-1)(x+2)$$

So you get the same remainder for $$-(x-1)(x+2)$$ as $$(x-1)(x^2-1).$$

• How does $(x^4-x)(x^2-1)+(x^2+x+1)x(x-1)$ Commented Aug 31, 2021 at 4:24
• @LalitTolani Forgot the $(x^2-1)$ term. Thanks! Commented Aug 31, 2021 at 4:26
• Thanks for the valuable and kind criticism, I was able to fix my answer in the end now. Commented Aug 31, 2021 at 5:09

Alternate method:

In the spirit of my answer to your linked question, we recognize that $$P (x) = x^2 + x + 1$$ can be "simplified" with $$Q(x) = x-1$$ to give us $$P(x) Q(x) = x^3 -1$$, and hence

\begin{align} & ( x^4 - 1 ) (x^2 -1 ) \\ = & (x^3 -1 ) A(x) + (x-1)(x^2 - 1) & (1)\\ = & (x^3 -1 ) B(x) + (-x^2 - x + 2 ) & (2) \\ = & (x^2 + x + 1 ) C(x) + 3. \\ \end{align}

Notes:

• In step (1), this uses that $$x^4 - x = (x^3 -1)D(x)$$
• In step (2), this uses $$(x-1)(x^2 -1) = x^3 - x^2 - x + 1 = (x^3-1) E(x) - x^2 -x + 2$$.
• Why does it change from $A(x)$ to $B(x)$ from Step 1 to Step 2? Also, $(x-1)(x^2-1)$ will give you an x^3 term. How do you handle that in your method? Commented Sep 1, 2021 at 16:55
• @Starlight Why not? Note that I didn't require these unknown polynomials to be distinct. Also, they are actually different, and in particular $A(x) + 1 = B(x)$. Commented Sep 1, 2021 at 16:59
• @Starlight FYI I don't think my answer should be accepted because it doesn't (directly) answer your question of "is it valid to skip Steps B and D" as I'm not using your approach as written. Thomas's answer to this particular question is much better than mine. I'm just showcasing what I consider to be the underlying idea to approach this question without too much machinery. Commented Sep 1, 2021 at 17:05

Alternate method:

$$(x^4 - 1)(x^2 -1)$$ has a degree of six, we can write:

$$(x^4 -1)(x^2-1)=Q(x) \left[ 1+x +x^2 \right] + R(x)$$

Evaluate (1) at $$\{ \omega, \omega^2 \}$$:

\begin{align} R( \omega) &= ( \omega-1)(\omega^2 - 1)= ( \omega -1)( \frac{1}{\omega}-1) \\ R( \omega^2) &= (\omega^2 -1)(\omega-1) = ( \omega -1)( \frac{1}{\omega}-1) \end{align}

This means that, $$xR(x) -(x-1)(1-x) = (x - \omega)(x- \omega^2)$$

Rearrange for the answer which is $$R(x)=3$$.

Note: $$(x^4 -1)(x^2-1)$$ when divided by $$1+x+x^2$$ must give a polynomial less than degree two. This follows via the remainder. See Wiki.

• I don’t see how you get $R(1).$ You get $$0=3Q(0)+R(0),$$ which doesn’t let you conclude $R(0)=0.$ Also, your final line is wrong - $R(x)$ is supposed to be a remainder, so it should have degree less than $2.$ Commented Aug 31, 2021 at 4:15
• I've edited the answer but remainder degree less than two is a bit confusing Commented Aug 31, 2021 at 4:36
• How do you got expression of $R(x)$ Commented Aug 31, 2021 at 4:38
• I have fixedd it now @LalitTolani, could you please tell me if it makes complete sense? Commented Aug 31, 2021 at 5:08
• I didn't understand how you got the equation after This means that Commented Aug 31, 2021 at 5:13