# Remainder when $x^{1000000}$ is divided by $x^3 + x +1$ in $\mathbb{Z}_2[x]$

I tried the traditional algorithm of long division hoping to find a pattern, but I was not able to.

I then tried using the root of $x^3 + x + 1$ $\left(x \sim -0.7\right)$ in the equation:

$$x^{1000000} = \left(x^3 + x + 1\right) q\left(x\right) + ax + b.$$

I have a horribly messy numerical result but I would like to solve this cleanly. How can I approach this?

• You might also have quadratic term in your remainder, i.e. it'd be $ax^2+bx+c$, not necessarily just $ax+b$. – Wojowu Feb 5 '15 at 20:55
• This has nothing whatsoever to do with division algebras. This should be plain to anyone who bothered to look at the tag excerpt (the text that shows when you mouseover a tag). Tsk. Tsk :-( – Jyrki Lahtonen Feb 17 '15 at 22:35

Just look at the low powers of $x$. Eventually they will cycle.

$x^0 = 1$

$x, x^2$ cannot be simplified, but

$x^3 = 0 - (x+1) = -x-1 = x+1$

$x^4 = x(x+1) = x^2+x$

$x^5 = x(x^2+x) = x^3+x^2 = x+1+x^2 = x^2+x+1$

$x^6 = x(x^2+x+1) = x^3+x^2+x = x+1+x^2+x = x^2+1$

$x^7 = x(x^2+1) = x^3+x = x+1+x = 1$.

So the powers of $x$ cycle with period $7$. You only need to consider the exponent of $x$ modulo $7$, then, and $x^{1000000} = x^{142857*7+1} = x^1 = x$.

• you're very welcome – Zach Effman Feb 5 '15 at 21:08
• There is a theoretical reason for this cycling as well: if $p(x)$ is an irreducible polynomial of degree $d$ over any field $F$, then $F[x]/\langle p(x)\rangle$ is a field extension of $F$ of degree $d$. In this case, $\Bbb Z_2[x]/\langle x^3+x+1\rangle$ is a degree-$3$ field extension of $\Bbb Z_2$. But there is only one such extension, and its multiplicative group is cyclic of order $2^3-1=7$. Therefore $x^7=1$ in this extension, which is the phenomenon seen above. (It's also true, for the same reason, that $x^3+x+1$ divides $x^7-1$ over $\Bbb Z_2$ - another way of seeing this calculation.) – Greg Martin Feb 5 '15 at 21:27
• By the way, there is an error in the calculation at $x^7$. $x^7=x(x^2+1)=x^3+x=1$ (which was clear anyway since the unit group of $\mathbb F_2[x]/(x^3+x+1)$ is cyclic of order $7$). So we get $x^{1000000}=x^{7 \cdot n+1} = x$ – MooS Feb 5 '15 at 21:30
• Thank you for catching it; I'll fix it – Zach Effman Feb 6 '15 at 23:35