How do I show that the polynomial $f(x) = x^2 + x + 3$ $∈$ $Z_7[x]$ is a primitive polynomial?

Question

I understand that a primitive polynomial is a polynomial that generates all elements of an extension field from a base field. However I am not sure how to apply this definition to answer my question. Can someone explain to me how I need to start please?

Answer 1

If you are happy to be vulgar, you can simply evaluate the expression at all 7 integer values, and show none of them is $0(7)$

Alternatively, $(x+4)^2 + 1\equiv x^2 + x + 3(7)$ and $-1$ is not a quadratic residue of $7$

Answer 2

The polyomial is irreducible for the reasons given in Will Brooks' answer. $F_{49}^{*}$ is cyclic of order 48. You want to check that a root $\alpha$ of the polynomial must have order 48. Since every element of $F_{49}^{*}$ has order dividing $48$, it's enough to check that $\alpha^{16} \ne 1$ and $\alpha^{24} \ne 1$. So it's enough to check that your given polynomial doesn't divide $X^{24} - 1$ or $X^{16} - 1$. You can do that by computing powers of $X$ modulo $f(X)$. (Successively compute $X^2$, $X^4$, $X^8$, $X^{16}$ and $X^{24}$ modulo $f(X)$.)

Answer 3

A primitive polynomial root is also the minimal polynomial of a primitive root of unity in $\mathbf F_7$. Let $\xi$ be a root of $f$. The field $\mathbf F_7(\xi)$ is the field $\mathbf F_{49}$ and its nonzero elements form a group of order $48$. It suffices to show $xi$ has order $48$. Anyway its order can only be a divisor of $48$, i.e. $1,2,4,8,16, 3,6,12,24,48$.

Let's compute the powers of $\xi$ from its minimal polynomial. I give the details only for one of them: from $\xi^2=-\xi-3$, we deduce $$\xi^4 =(\xi+3)^2=\xi^2+6\xi+2=5\xi-1$$. Similarly \begin{alignat*}{4} \xi^8&=3,&\qquad&\xi^{16}=2, &\qquad&\xi^{24}=-1,&\qquad&\xi^{48}=1. \end{alignat*} The order cannot be $3, 6$ or $12$, since otherwise we would have $\xi^{24}=1$.

Thus $\xi$ is a primitive root of unity in $\mathbf F_{49}$, which proves $f$ is a primitive polynomial in $\mathbf F_7[x]$.