Okay, so this is a similar way that seems to work for me:
Suppose F_{p^n}=F_p(a), where a is a root of some irreducible polynomial over F_p of degree n.
Then,
a^(p^n-1), ..., a^{p^2}, a^p, a (= a^{p^n}) is a basis of the F_p-vector space F_p(a)
Then we notice that \phi(a^{p^i}) = a^{p^i+1}...