# On a characterization of primitive polynomials over a finite field

Let $K$ be a finite field. Let us define a primitive polynomial as an $f \in K[X]$ s.t. the multiplicative order of $X$ in $K[X]/(f)$ is equal to $|K|^{\deg f} - 1$. I want to show that $f \in K[X]$ is primitive if and only if $f$ is irreducible and $X$ generates the multiplicative group $(K[X]/(f))^\times$.

I would like to ask how to show this. I already showed that if $f$ is primitive and irreducible the latter half of the condition holds, but I cannot figure out the rest. I would also like to know if it is customary to talk about the multiplicative order of an element of a ring whose multiplicative part is not necessarily a group.

-
I think you mean "multiplicative order of $X$." Also, the multiplicative group has $|K|^{\deg f}-1$ elements at most, so $X$ can never have the order you give in your problem. –  Thomas Andrews Mar 10 '13 at 4:10

## 1 Answer

I assume that the definition of primitive includes that $X$ is relatively prime to $f$ (since if not, $X$ has no well-defined multiplicative order in $K[X]/(f)$.)

If $f$ has a nontrivial divisor $g$, there are at least two elements of $K[X]/(f)$, $0$ and $g$, which do not have multiplicative inverses, so $K[X]/(f)$ has at most $|K|^{\deg f}-2$ invertible elements. However, if $f$ is primitive, then, by definition, $K[X]/(f)$ contains $|K|^{\deg f}-1$ powers of $X$, all of which are invertible. Therefore, if $f$ is primitive, then it is also irreducible. This reduces the problem to showing that if $f$ is irreducible, then $f$ generates the multiplicative group of $K[X]/(f)$ if and only if $f$ has order $|K|^{\deg f}-1$. But this is obvious because the group has order $|K|^{\deg f}-1$.

-