# Polynomial division and remainder

Find the remainder when $$x^{100}+x^{101}$$ is divided by $$x^2+x+1$$. I don't know how to proceed with this. Can you give a hint on how to start?

Hints:

$$x^2+x+1 | x^{101}+x^{100}+x^{99}$$ so $$x^{101}+x^{100}\equiv-x^{99}\pmod {x^2+x+1}$$.

$$x^{99}\equiv (x^3)^{33}\equiv1\pmod {x^3-1}$$.

$$x^2+x+1 | x^3-1$$

• Thank you for helping me with this problem! Using your hints I was able to come up with a result of -1! By realizing the mod x^3-1 of x^99 is 1, and using this information to find the remainder of the missing -x^99 from the original expression (x^100+x^101). – Lisa Levi Jun 23 at 5:29
• You're welcome! – J. W. Tanner Jun 23 at 18:30

The hint: $$x^{101}+x^{100}=\left(x^{101}+x^{100}+1\right)-1=$$ $$=\left(x^{101}-x^2\right)+\left(x^{100}-x\right)+(x^2+x+1)-1$$ and use $$x^3-1=(x-1)(x^2+x+1).$$

If you have studied complex numbers, this is one way to proceed:

$$P(x) = Q(x)(x-\alpha)(x-\beta) + ax+b$$

where $$\alpha, \beta$$ are the (complex) roots of the divisor quadratic and $$ax+b$$ is the linear remainder.

Here, note that the roots of $$x^2+x+1$$ are the complex cube roots of unity (one), which are often represented $$\omega, \omega^2$$. They have the property that their third power is simply $$1$$, and therefore any power that is a multiple of three just returns them to $$1$$. This is very useful.

The two roots $$\omega, \omega^2$$ are complex conjugates of each other. It doesn't matter which of the two values we choose to represent as $$\omega$$, as one squared equals the other, and vice versa.

So here we can write:

$$P(\omega) = Q(x)(\omega-\omega)(\omega-\omega^2) + a\omega+b$$

which reduces to:

$$P(\omega) = a\omega +b\ \$$ (equation 1)

and $$P(\omega^2) = Q(x)(\omega^2-\omega)(\omega^2-\omega^2) + a\omega^2+b$$

which reduces to:

$$P(\omega^2) = a\omega^2 +b\ \$$ (equation 2)

Note that $$P(\omega) = \omega^{100} + \omega^{101} = \omega^{99}\cdot \omega + \omega^{99} \cdot \omega^2 = \omega + \omega^2 = -1$$

(since $$\omega^2 + \omega + 1 = 0$$)

Similarly,

$$P(\omega^2) = \omega^{200} + \omega^{202} = \omega^{198}\cdot \omega^2 + \omega^{201} \cdot \omega = \omega^2 + \omega = -1$$

which gives us the pair of linear simultaneous equations:

$$a\omega + b = -1 \ \$$ (equation 1)

$$a\omega^2 + b = -1 \ \$$ (equation 2)

subtract the first from the second to get: $$a(\omega^2 - \omega) = 0$$, which implies $$a=0$$ since $$\omega^2 - \omega \neq 0$$, and $$b=-1$$.

So the remainder is simply $$-1$$.