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?
 A: 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$
A: 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).$$
A: 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$.
