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?

  • 4
    $\begingroup$ You might also have quadratic term in your remainder, i.e. it'd be $ax^2+bx+c$, not necessarily just $ax+b$. $\endgroup$ – Wojowu Feb 5 '15 at 20:55
  • $\begingroup$ 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 :-( $\endgroup$ – 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$.

  • $\begingroup$ you're very welcome $\endgroup$ – Zach Effman Feb 5 '15 at 21:08
  • 3
    $\begingroup$ 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.) $\endgroup$ – Greg Martin Feb 5 '15 at 21:27
  • 3
    $\begingroup$ 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$ $\endgroup$ – MooS Feb 5 '15 at 21:30
  • $\begingroup$ Thank you for catching it; I'll fix it $\endgroup$ – Zach Effman Feb 6 '15 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.