Show $p(x)$ is a primitive polynomial

Question

First the definition:

Polynomial $q(x) \in \mathbb{Z}_p[x]$ of degree $n$ is called primitive, iff:

1. $q(x) \mid x^{p^n-1}-1$
2. $\forall k : 1 \leq k \leq p^{n}-1$ : $q(x) \nmid x^k - 1$

Now the polynomial from my exam, where I should show that it is primitive:

$p(x)=x^6+x^5+x^2+x+1, \quad p(x) \in \mathbb{Z}_2$

So in this case $n=6$ and $p=2$, hence I need to check $1+(2^6-1)=64$ cases. How is this feasible to do on the exam, where I have just few minutes for each task without access to computer? Am I missing some "trick" to show that $p(x)$ is primitive?

Answer 1

First we show that $p$ is irreducible. If it were not, it would have a root in $F_2$, $F_4$ or $F_8$.

If $a$ were a root in $F_4$, we'd have $a^3 = 1$, hence $0 = a^6 + a^5 + a^2 + a + 1 = a$, which is impossible.

If $a$ were a root in $F_8$, we'd have $a^7 = 1$, hence $0 = a^8 + a^7 + a^4 + a^3 + a^2 = a^4 + a^3 + a^2 + a + 1$. Multiplying by $a - 1$, we find $a^5 = 1$. Combining this with $a^7 = 1$, it follows that $a = 1$, which is absurd.

Since $p$ is irreducible, its roots are distinct and of degree $6$ over $F_2$. They therefore belong to $F_{64}^{*},$ so they satisfy $x^{63} = 1$ by Lagrange's theorem. This proves that $p(x)$ divides $x^{63} - 1$. Moreover, since the roots are conjugate, they all have the same order.

Because the roots have order dividing $63$, the only thing to do now is to check that they do not satisfy $x^9 = 1$ or $x^{21} = 1$. The first part results from the fact that $p(x)$ is irreducible and $x^9 - 1 = (x^3 - 1)(x^6 + x^3 + 1)$. For the second part, we have the factorization $x^{21} - 1 = (x-1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)(x^{14} + x^7 + 1)$. At this point, I don't see anything better to do than to divide $x^{14} + x^7 + 1$ by $p(x)$ by hand.

Answer 2

Assuming $p$ is irreducible it suffices to show that the order of a root $\alpha$ is at least $22$ (since the order divides $63$). This is easy to check with the linear recursion (in $\mathbb{F}_2$) $$a_n=a_{n-1}+a_{n-4}+a_{n-5}+a_{n-6}$$ which has period equal to the order of $\alpha$. Starting from $00000\,1$ this sequence continues as $$00000\,11110\,01001\,01010\,01\ldots$$ and so its period is more than $21$.