What is the remainder of this polynomial division?

Question

Find the remainder when $\ (x^2 + x + 1)^{n}$ is divided by$\ x^{2} - x + 1 $, knowing that$\ n$ is a positive integer.

Answer 1

Pattern: $$\begin{align}\frac{(x^2+x+1)^0}{x^2-x+1}&=0+\frac{2^0}{x^2-x+1}\end{align}$$ $$\begin{align}\frac{(x^2+x+1)^1}{x^2-x+1}&=A+\frac{2^1x}{x^2-x+1}\end{align}$$ $$\begin{align}\frac{(x^2+x+1)^2}{x^2-x+1}&=B+\frac{2^2(x-1)}{x^2-x+1}\end{align}$$ $$\begin{align}\frac{(x^2+x+1)^3}{x^2-x+1}&=C-\frac{2^3}{x^2-x+1}\end{align}$$ $$\begin{align}\frac{(x^2+x+1)^4}{x^2-x+1}&=D-\frac{2^4x}{x^2-x+1}\end{align}$$ $$\begin{align}\frac{(x^2+x+1)^5}{x^2-x+1}&=E-\frac{2^5(x-1)}{x^2-x+1}\end{align}$$

Conjecture: $$\begin{align}(x^2+x+1)^n\equiv \left\{\begin{matrix} (-1)^{n/3}2^n&\pmod{x^2-x+1}\quad\text{if}\,3\mid n\\ (-1)^{(n-1)/3}2^nx&\pmod{x^2-x+1}\quad\text{if}\,3\mid (n-1)\\ (-1)^{(n-2)/3}2^n(x-1)&\pmod{x^2-x+1}\quad\text{if}\,3\mid (n-2)\\ \end{matrix}\right.\end{align}$$

Answer 2

Note that if $\omega, \omega^2$ are the non-real cube roots of unity (i.e. $\omega^2 + \omega+1=0$), we have $-\omega, -\omega^2$ as roots of $x^2-x+1$. Now as the remainder sought, say $r(x)$, has degree less than $2$, we just need it evaluated at two points.

$r(-\omega) = (\omega^2-\omega+1)^n = (-2\omega)^n$ and $r(-\omega^2) = (-2\omega^2)^n$. So by the two point form, $$\frac{r(x)-r(-\omega) }{r(-\omega^2)-r(-\omega)}= \frac{x - (-\omega)}{(-\omega^2) - (-\omega)}$$

$$\implies r(x) = \frac{(-2\omega^2)^n-(-2\omega)^n}{\omega-\omega^2}(x+\omega) + (-2\omega)^n$$

To simplify any further, you could consider cases $n \pmod 3$, or use it as is to evaluate for any given $n$. For illustration, $n=1, 2, 3, 4, 5$ yields $r(x) = 2x, 4(x-1), -8, -16x, -32(x-1)$ respectively.