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?

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