I am currently studying toward understanding the Berlekamp–Zassenhaus algorithm for factorizing polynomials, using 'Algorithms of Informatics' (AnTonCom, Budapest, 2011).
While studying some algebraic preliminaries in chapter 5, I stumbled upon the following lemma (see p. 235):
Lemma 5.32 Let be a prime. In a finite field $\mathbb{F}_q$ there exists an element which is not an $r$-th power if and only if $q \equiv 1 \pmod r$. If $b \in \mathbb{F}_q$ is such an element, then the polynomial $x^r - b$ is irreducible in $\mathbb{F}_q[x]$, and so $\mathbb{F}_q[x]/(x^r-b)$ is a field with $q^r$ elements.
The proof of the implication
$q \equiv 1\pmod r$ $\implies$ There is an element which is not an $r$-th power
assumes $r \mid q - 1$, giving the $r$-th powers explicitly as $$ 0,\, 1,\, a^r,\, \left(a^r\right)^2, \dots ,\, \left(a^r\right)^{(q - 1)/r - 1} $$ where $a$ is a generator of the cyclic group $\mathbb{F}_q\setminus \left\{0\right\}$ and then picks $s$ maximal such that $r^s \mid q-1$.
I understood all this, however I'm at a loss at how to prove the next statement the author makes:
Then the order of an element $b \in \mathbb{F}_q\setminus\{0\}$ is divisible by $r^s$ if and only if $b$ is not an $r$-th power.
From the explicit listing given, one can read off that all nonzero $r$-th powers constitute a cyclic group generated by $a^r$ of order $(q-1)/r$. By initial assumption, this implies $r^s \nmid \mathop{ord}(a^r) = (q - 1)/r\,$, by maximality of $s$. But then, $r^s \nmid \mathop{ord}\left(\left(a^r\right)^j\right)$ for all $j$, since $$ \mathop{ord}\left(\left(a^r\right)^j\right) \mid \mathop{ord}\left(\left(a^r\right)\right) $$ by LaGrange's theorem. This shows that no nonzero $r$-th power is of order divisible by $r^s$.
Now, assume that $b \neq 0$ is not an $r$-th power. This means that $b = a^l$ with $r \nmid l$. Since $$ 1 = b^{\mathop{ord}\left(b\right)} = a ^ {l \cdot \mathop{ord}\left(b\right)} $$ we have $r^s \mid q - 1 \mid l \cdot \mathop{ord}\left(a\right)$, so that $r^s \mid l \cdot \mathop{ord}\left(a\right)$ which proves $r^s \mid ord\left(b\right)$, because $r$ is prime and $r \nmid l$ (use the unique-prime-factorization-theorem).