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?

As another approach, factor the two quadratics as
$$x^2 + x + 1 = (x-\phi)(x+\psi)$$ $$x^2 - x + 1 = (x + \phi)(x - \psi)$$
Where $\phi$ and $\psi$ are solutions to $\phi\psi=-1$, $\psi - \phi=1$
So problem reduces to solving for $A$ and $B$
$$(x-\phi)^n(x+\psi)^n = P(x)(x+\phi)(x-\psi) + Ax + B$$
Evaluate this for $x=-\phi$ and $x=\psi$ to get
$$(-2\phi)^n(\psi - \phi)^n = -A\phi + B$$
$$(\psi - \phi)^n(2\psi)^n = A\psi + B$$
Remember that $\psi - \phi = 1$ and the rest should be straightforward
