$\newcommand{\FF}{\mathbb{F}} $ $\newcommand{\bs}{\mathbf{s}}$ Given linear recurrence $$ x_n = a_{1}x_{n-1} + a_{2}x_{n-2} + \cdots + a_kx_{n-k}\pmod p, $$ for $x_0, x_1, \ldots$ we define its state vector $\bs_{m}=(x_{m+k-1}, \ldots, x_m)\in \FF_p^k$. The sequence is determined by choosing $\bs_0$. We define its characteristic polynomial to be $\phi(x) = x^k - a_1x^{k-1} - \cdots - a_k$. We say a recurrence is maximal if it has period $p^k-1$ for any nonzero choice of initial state $\bs_0$. Clearly this is maximal because no nontrivial sequence can pass through the zero state.
I am trying to prove the following (The Art of Computer Programming Vol 2, sec 3.2.2)
The recurrence is maximal iff $\phi$, considered as an element of $\FF_{p^k}[x]$, has a primitive element of $\FF_{p^k}$ as a root.
I am unsure how to attempt either direction.