Polynomial Divisibilty Test

Question

I recently came across a question in a book and I was wondering how to go about solving this. I just need a hint about how I could approach it.

I have to show that $x^{6n+2} - x^{6n+1} + 1$ is always divisible by $x^2 - x + 1$ where $n = \{1,2,3,4,\cdots\}$

Answer 1

Let $\alpha,\beta$ be two (complex) roots of $x^2-x+1$. Then $x^2-x+1=(x-\alpha)(x-\beta)$. Note that $x^2-x+1$ divides $x^3+1=(x+1)(x^2-x+1)$, and hence also $x^6-1=(x^3-1)(x^3+1)$. So both $\alpha,\beta$ satisfy $x^6=1$. Thus we have $\alpha^{6n+2}-\alpha^{6n+1}+1=(\alpha^6)^n\cdot\alpha^2-(\alpha^6)^n\cdot\alpha+1=\alpha^2-\alpha+1=0$, and same for $\beta$. So both $\alpha,\beta$ are roots of $x^{6n+2}-x^{6n+1}+1$. So $x-\alpha,x-\beta$ divide $x^{6n+2}-x^{6n+1}+1$, so also $(x-\alpha)(x-\beta)=x^2-x+1$ divides $x^{6n+2}-x^{6n+1}+1$.

Answer 2

Hint. For $x = 4$, this gives that $4^{6n+2} - 4^{6n+1} + 1\equiv 0 \bmod 13$. How would you prove this? Then try to extend your method to polynomials.

Answer 3

Take $n=1$. Then $x^2-x+1|x^8-x^7+1$ and the quotient is $x^6-x^4-x^3+x+1$.

Now assume that the $x^2-x+1|x^{6n+2}-x^{6n+1}+1$ and the quotient be $q(x)$.

Performing long division,

$x^{6n+8}-x^{6n+7}+1=(x^2-x+1)(x^{6n+6}-x^{6n+4}-x^{6n+3}+x^{6n+1}+q(x))$.

Hence by induction the result follows.