<s>[INST] 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:
"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."
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?
 [/INST] Hint: every term but the last is divisible by $a$, so your remainder is congruent to $(2x)^n$. But that's not quite enough either, because that's still too 'large' if $n\gt 1$. You need to figure out how to divide $(2x)^n$ by $x^2-x+1$. The easiest way (IMHO) to do that is this: modulo $x^2-x+1$, we can just say that $x^2\equiv x-1$. This means that every polynomial is equivalent to one of the form $ax+b$; if you have $(2x)^n\equiv a_nx+b_n$, then you can multiply the RHS by $2x$ and use the equivalence to find $a_{n+1}$ and $b_{n+1}$ in terms of $a_n$ and $b_n$.
</s>