Remainder of Polynomial Division of $(x^2 + x +1)^n$ by $x^2 - x +1$ I am trying to solve the following problem:
Given $n \in \mathbb{N}$, find the remainder upon division of $(x^2 + x +1)^n$ by $x^2 - x +1$
the given hint to the problem is:
&quot;Compute $(x^2 + x +1)^n$ by writing $x^2 + x +1 = (x^2 - x +1) + 2x$. Then, use the uniqueness part of the division algorithm.&quot;
If I take $a = x^2 - x +1$ I have
$$(x^2 + x +1)^n = (a + 2x)^n = a^n + \binom{n}{1}a^{n-1} 2x+ \binom{n}{2}a^{n-2} (2x)^2 + \dots + (2x)^n$$
but how do I proceed further?
Since every term but the last is divisible by $a$, so we only need to deal with $(2x)^n \bmod \left(x^2-x+1\right)$. Let's start from small ones, and try to find patterns:
$$
\begin{aligned}
((2 x)^1 &amp;\bmod \left(x^2-x+1\right))=\color{gray}{2x} \\
((2 x)^2&amp;\bmod \left(x^2-x+1\right)) =\color{red}{-4+4 x} \\
((2 x)^3 &amp;\bmod \left(x^2-x+1\right)) = \color{blue}{-8}\\
((2 x)^4 &amp;\bmod \left(x^2-x+1\right)) = \color{green}{-16x}\\
((2 x)^5 &amp;\bmod \left(x^2-x+1\right)) = 32-32x\\
((2 x)^6 &amp;\bmod \left(x^2-x+1\right)) = 64\\
((2 x)^7 &amp;\bmod \left(x^2-x+1\right)) =\color{gray}{128x}\\
((2 x)^8 &amp;\bmod \left(x^2-x+1\right)) = \color{red}{-256+256x}\\
((2 x)^9 &amp;\bmod \left(x^2-x+1\right)) = \color{blue}{-512} \\
((2 x)^{10} &amp;\bmod \left(x^2-x+1\right)) =\color{green}{-1024 x}
\end{aligned}
$$
What do you find? Hint: Divide into groups by $n \bmod 6$. Prove by induction separately.
Great job so far! Notice that all terms of the form $\binom{n}{i}a^{n-i}$ are divisible by $a$ if and only if $i&lt;n$. This means that the remainder is simply $(2x)^n$.