Show that $x^7 + x^6 + x^5 + x^4 + x^2 + x + 1$ is a primitive polynomial over $Z_2$.

Question

I am new to polynomial rings and have to solve the following question:

Show that $x^7 + x^6 + x^5 + x^4 + x^2 + x + 1$ is a primitive polynomial over $Z_2$.

I was trying to use this theorem to solve the problem:

A polynomial of degree $n$ over the finite field $GF(2)$ (i.e., with coefficients either $0$ or $1$) is primitive if it has polynomial order $2^n-1$.

But I am still stuck, Any help would be appreciated.

Answer 1

It suffices to show that the polynomial $f = x^7+x^6+x^5+x^4+x^2+x+1$ does not have any (non-constant) factor of degree $\leq 3$.

This can be achieved by proving two statements:

1. show that $f$ has no root in $\Bbb F_{2^2}$;
2. show that $f$ has no root in $\Bbb F_{2^3}$.

The first can be shown by verifying that $\gcd(f, x^{2^2} - x) = 1$, and similarly the second with $\gcd(f, x^{2^3} - x) = 1$.

Computations of the $\gcd$'s are carried out with the usual Euclid algorithm.

---

One may also compress the two computations into one, by showing that $f$ has no root in $\Bbb F_{2^6}$, hence it suffices to compute $\gcd(f, x^{2^6} - x)$.

This is not necessarily simpler, as the exponent gets bigger.