Polynomial division and remainder

Question

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?

Answer 1

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$

Answer 2

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

Answer 3

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