Order of element in field extension Given a field extension $\mathbb{F}_{p^n}$ and some element $\alpha \in \mathbb{F}_{p^n}$ which is not contained within any proper subfield of $\mathbb{F}_{p^n}$, is there a lower bound on the order of $\alpha$?
I understand that the nonzero elements of a finite field form a cyclic group generated by some primitive element $\beta \in \mathbb{F}_{p^n}$. However, if we don't know whether $\alpha$ is primitive, what can we say about its order (without actually computing anything)?

Well, for any $m\mid n$, the subfield $\mathbb{F}_{p^m}$ consists of all elements of order dividing $p^m-1$.  So the possible orders of elements of $\mathbb{F}_{p^n}$ which are not in any proper subfield are all the factors of $p^n-1$ that are not factors of $p^m-1$ for any proper divisor $m$ of $n$.
This gives a simple way to compute the possibilities in any individual case if you're willing to do some integer factoring.  I don't see any simple way to get a general explicit lower bound from this, though.  Using the Frobenius automorphism, as in Quinn Greicius's answer, you can find a lower bound of $n+1$.  This is tight in some cases: for instance, if $p=3$ and $n=4$, then the possibilities are factors of $3^4-1=80$ which are not factors of $3^2-1=8$, and the smallest such factor is $5=n+1$.   But it is often not tight: for instance, it never can be if $n+1$ is divisible by $p$, since $p^n-1$ has no factors which are divisible by $p$.  Or in the case that $n+1$ is prime, it will be tight iff $p$ is a primitive root mod $n+1$ (since that means exactly that $p^n-1$ is divisible by $n+1$ but $p^m-1$ is not for all smaller $m$).
