Resto cuando se divide $x^{1000000}$ $x^3 + x +1$ $\mathbb{Z}_2[x]$

Question

He probado el algoritmo tradicional de la división de largo con la esperanza de encontrar un patrón, pero no pude.

Luego probé utilizando la raíz de $x^3 + x + 1$ $\left(x \sim -0.7\right)$ en la ecuación:

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

Tengo un resultado numérico horriblemente desordenado pero me gustaría solucionar esto limpio. ¿Cómo puedo plantear esto?

Answer 1

Basta con mirar los poderes bajo de $x$. Finalmente hará un ciclo.

$x^0 = 1$

$x, x^2$ no puede ser simplificada, pero

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

Así que los poderes de $x$ ciclo con período $7$. Basta con considerar el exponente de $x$ modulo $7$, entonces y $x^{1000000} = x^{142857*7+1} = x^1 = x$.