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)?
On
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$).
From the fact that $\alpha$ is not contained within any proper subfield, we know it is not fixed by any power of Frobenius, so that the elements $\alpha, \alpha^p, \alpha^{p^2},...,\alpha^{p^{n-1}}$ are all distinct, i.e. there exist $n$ distinct powers of $\alpha$ not equal to the identity, so $\alpha$ must have order greater than $n$.