an irreducible polynomial over GF(2) is primitive over GF(2)

Question

let $P \in F_{2} [X]$ of degree $7$, how to prove this:

P is irreducible $\Leftrightarrow$ P is primitive

i tried to use the mersenne prime !

Answer 1

One direction is trivial. Assume P(x) is a primitive. Then clearly P(x) is irreducible over Z_2 (Since P(x) is the minimal monic polynomial where P(a) = 0 and (a) = GF^*(2^7).

Conversely, assume that P(x) is irreducible. Let a be a root of P(x). We know Z_2(a) is ring-isomorphic to Z_2[x]/(P(x)). Thus Z_2(a) = GF(2^7). Note that GF*(2^7) is a group under multiplication and |GF*(2^7)| = 127 = 2^7 - 1. Note that 127 is a prime number. Hence |a| = 2^7 - 1 = 127 (Note that the order of each element must divide the order of the group by Lagrange). Thus a is a primitive root (other name a is (2^7 -1)-root of unity). Let m = 2^7-1. Since (a) = {1, a, a^2, ..., a^{m-1} }, P(x) is primitive.

Answer 2

first a primitive polynomial is irreducible by definition.

For the other direction, if P is an irreducible polynomial of degree $7$, it generates a field extension of $2^7 = 128$ elements over Z2.

The polynomial is primitive if the powers of one of its roots generate the multiplicative group of the field. If the polynomial is not primitive, the powers of its root only generate a proper subgroup of that group.

However, the multiplicative subgroup of the fields consists of the non-zero elements, which means that this group has order 127. As 127 is prime, the group does not contain any proper non-trivial subgroup, by Lagranges's theorem.

Answer 3

A more general statement can be shown. All irreducible polynomials of degree $n$ in $GF(2)[x]$ are primitive if and only if $2^{n}-1$ is a (Mersenne) prime. Note that this means $n$ must also be a prime. It now suffices to compare the number of irreducible polynomials from Gauss formula $\frac{\sum_{d \mid n} \mu(d) 2^{\frac{n}{d}}}{n}$ and the number of primitive polynomials $\frac{\phi(2^n-1)}{n}$ where $\mu$ and $\phi$ are, respectively, the Moebius and Euler phi function. The numerator in the first formula is $2^n-2$ while in the second one it is $2^n-2$ if and only if $2^n-1$ is a prime.