Primitive polynomials I am revising for a discrete mathematics exam and as quite stuck on this question.
Show that the polynomial $f = x^2 + 2 x + 3 \in \mathbb{Z}_5[x]$ is primitive. How many monic primitive quadratic polynomials are there in $\mathbb{Z}_5[x]$?
Any help would be greatly appreciated.
 A: A polynomial is called primitive (in the context of finite fields), iff its zero is a generator of the multiplicative group of the field it generates. In this case the polynomial is quadratic, so a root $\alpha$ will generate the field $L=\mathbb{F}_{25}$.
The multiplicative group of $L$ is cyclic of order 24. By the well known facts about cyclic groups, the group $L^{\times}$ has $\phi(24)=\phi(2^3\cdot3)=2^2(3-1)=8$ generators. Another way of seeing this is to observe that if $g$ is a primitive root of unity of order $24$, all of them are in the list $g$, $g^5$, $g^7$, $g^{11}$, $g^{13}$, $g^{17}$, $g^{19}$ and $g^{23}$. Anyway, between them, these eight elements have four distinct minimal polynomials (the conjugate of a primitive element is also primitive, and the conjugates come in pairs in a quadratic extension).
The answer is thus that there are exactly $4$ quadratic primitive polynomials.

Looking at the specific polynomial $p(x)=x^2+2x+3$. Its discriminant is non-square, so it is irreducible (alternatively one may check that it has no zeros in $\mathbb{F}_5$). Let $g$ be one of its roots in the extension field
$\mathbb{F}_{25}$. We want to prove that it is of order $24$. We know that the order is a factor of $24$, so it suffices to rule out factors of $12$ and $8$
as orders.
The other zero of $p(x)$ is the Frobenius conjugate $g^5$ (basic Galois theory).
The product of the zeros of a monic quadratic is its constant term, so we know that
$$
g^6=g\cdot g^5=3.
$$
Therefore $g^{12}=3^2=4=-1$, and we can conclude that the order of $g$ is not a factor of $12$. We still have to rule out the possibility that $g$ could be of order $8$. If $g$ were of order $8$, then $g^2$ is of order four. But all the fourth roots of unity are in the prime field $\mathbb{F}_5$. OTOH from the minimal polynomial we read that $g^2=-(2g+3)=3g+2$ is not $\in \mathbb{F}_5$. 
The claim follows from this.
A: Hint: if you actually meant "irreducible polynomial"  then
$$x^2+2x+3\in\Bbb Z_5[x]\implies \Delta=b^2-4ac=4-12=-8=2\pmod 5$$
Is there $\,a\in\Bbb Z_5\;\;s.t.\,\,a^2=2\,$ ?
A: About monic irreducibles, the reducible ones are those which can be factored in $\mathbb{Z}_5$, i.e., can be written $(x - a) (x - b)$. This means selecting 2 out of 5 as roots if different, and 5 if equal, for a total of:
$$
\binom{5}{2} + 5 = 10 + 5 = 15
$$
The total number of monic polynomials $x^2 + c_1 x + c_2$ is just $5 \cdot 5 = 25$ (can select $c_1$, $c_2$ at will), so there are $25 - 15 = 10$ irreducible ones.
A: I came to this idea thanks to Jyrki Lahtonen:
$
x^1 = x\\
x^2 = -2x - 3 = 3x + 2\\
x^4 = (4x + 2)(4x + 2) = 4x + 2\\
x^8 = x^4 \cdot x^4 = 4x + 1\\
x^{12} = x^8 \cdot x^4 = 4\\
x^{24} = x^{12} \cdot x^{12} = 16 = 1\\
$
It answers the first part of the question only but completely.
A: A polynomial with integer coefficients is primitive if its content (the GCD of its coefficients) is 1.
You can simply enumerate the primitive monic quadratic polynomials (depicted as ordered triples of coefficients in descending order of order):
(1, 0, 1), (1, 1, 1), (1, 0, 2), (1, 1, 2), (1, 2, 1), (1, 0, 3), (1, 1, 3), (1, 3, 1), (1, 2, 3), (1, 3, 2), (1, 1, 4), (1, 4, 1), (1, 3, 4), (1, 4, 3)
Where (1, 1, 1), for example, is $x^2 + x + 1$ in $\mathbb{Z_5}$.
