Thread: Proving that the additive integer is prime...

I've run into this question and I feel like im on the brim of solving it but i cant come up with final undisputable proof:

"Prove that if p is a prime number and a is an integer such that p does not divide a, then the additive order of a modulo p is equal to p."

I know that it involves proving 2 cases, one where the additive order is greater or equal to p, and one where it is less than or equal to p. Both of these can be done by contradiction.

I have only written simple proofs before and I'm wondering if someone could show me how this problem is done.

Thank you.

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