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?

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$.
