TITLE: Order of matrix and monic irreducible polynomial over finite field
QUESTION [6 upvotes]: I want to verify (and prove - in case it is true) the following proposition.
Suppose $\mathbb{F}_p$ is a finite field and $m(x)$ is a monic irreducible polynomial over $\mathbb{F}_p$ with $\mathrm{deg}(m(x))=n$.
If $\mathbf{A}$ is an $n \times n$ matrix over $\mathbb{F}_p$ whose characteristic polynomial is $m(x)$, then $\mathrm{ord}(\mathbf{A})=p^n-1$, where $\mathrm{ord}(\mathbf{A})$ denotes the least positive integer $k$ such that $\mathbf{A}^k = \mathbf{I}$, where $\mathbf{I}$ is the identity matrix.
For example, in $\mathbb{F}_2$, $m(x)=x^3+x^2+1$ is a monic irreducible polynomial. The characteristic polynomial of matrix $\mathbf{A}=$
\begin{bmatrix}0&0&1\\1&0&0\\0&1&1\end{bmatrix}
is equal to $m(x)$ and $\mathbf{A}$ satisfies $\mathrm{ord}(\mathbf{A})=7$. Note that $2^3-1=7$.
I have already checked using SAGE mathematical software that the companion matrices of a monic irreducible polynomial have order $q^n-1$ for $q=2$ and $2\leq n \leq 21$.
My question is, is the above proposition true in general?
My attempt to prove the theorem is by using group isomorphism between $\mathbb{F}^{*}_p = (\mathbb{F}_p[x]/m(x))^{*}$, i.e. the non zero elements of the finite field, and the matrix group $S = \{\mathbf{A}^k | k \in \mathbb{Z}\}$. But a problem occurs, how to construct an isomorphism from $\mathbb{F}^{*}_p$ to $S$ ? I have tried the function $\theta: \alpha \mapsto \mathbf{A}$ where $\alpha$ is the primitive element in $\mathbb{F}^{*}_p$, but I can not complete the detail.
I have read several references, this book, p. 65 by R. Ridl and H. Niedereitter and this article by W. P. Wardlaw. The proposition seems true, but I have not found any formal proof about it.
ADDENDUM:
Apparently, the proposition is not true in general. There is a counterexample in W. P. Wardlaw article for $m(x)=x^2+1$ in $\mathbb{F}_3$. (Credit to WimC). However the condition is true for $m(x)=x^2+x+2$.
So what is there any additional requirement for $m(x)$ in order to make the proposition true?

REPLY [1 votes]: No this is not true in general. The polynomial $m(X)=X^2+1$ is irreducible over $\mathbb{F}_3$ but the order of $X$ in $(\mathbb{F}_3[X]/m(X))^{\ast}$ is $4$. In other words, not all non-zero elements in the multiplicative group of a finite field with $p^n$ elements need to have the maximal order $p^n-1$.
{"set_name": "stack_exchange", "score": 6, "question_id": 1595761}