So since $p$ is prime, the order of is either or some power of , say . If , then we're done, so assume that . So an element has order if is the smallest positive integer with the property that .

Now generates a cyclic subgroup of that consists of elements, each of which is a power of .

So let be an element in where is a positive integer and . Now generates a subgroup of , and the order of must divide . Now since , is there some value of such that ?

Check out the section on cyclic subgroups in Artin's Algebra. There is a proposition that talks about the GCD of the order of a group and the order of an element in the group. makes the rest of the proof a snap.