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?



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

  • $\begingroup$ 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). $\endgroup$ – Lisa Levi Jun 23 at 5:29
  • $\begingroup$ You're welcome! $\endgroup$ – 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$)


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.