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?
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 &\bmod \left(x^2-x+1\right))=\color{gray}{2x} \\ ((2 x)^2&\bmod \left(x^2-x+1\right)) =\color{red}{-4+4 x} \\ ((2 x)^3 &\bmod \left(x^2-x+1\right)) = \color{blue}{-8}\\ ((2 x)^4 &\bmod \left(x^2-x+1\right)) = \color{green}{-16x}\\ ((2 x)^5 &\bmod \left(x^2-x+1\right)) = 32-32x\\ ((2 x)^6 &\bmod \left(x^2-x+1\right)) = 64\\ ((2 x)^7 &\bmod \left(x^2-x+1\right)) =\color{gray}{128x}\\ ((2 x)^8 &\bmod \left(x^2-x+1\right)) = \color{red}{-256+256x}\\ ((2 x)^9 &\bmod \left(x^2-x+1\right)) = \color{blue}{-512} \\ ((2 x)^{10} &\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.
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$.
You're trying to divide by $a$ with remainder. You almost have it, since in your expression for $(a+2x)^n$ all terms but the final $(2x)^n$ are multiples of $a$ so can be dropped in getting the remainder. You now can focus just on $(2x)^n.$
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
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<n$. This means that the remainder is simply $(2x)^n$.
