Let with p prime and . Apply the division algorithm to see

for some integers q and 0<r<p. note: r is not 0 as this would mean p does in fact divide a.

clearly pa is 0 mod p, so the order of a is at most p and at least 2 since a is not the identity (p doesn't divide a). Suppose for a moment the order is strictly less than p. That means there is some integer 1<k<p such that p clearly divides pqk, so p divides rk.

Now since p is prime, p divides either r or k. but both r and k are strictly less than p which is impossible. Thus the order must be precisely p as desired. QED