Proof of the Order Divisibility Property

[squire636]

The Order Divisibility Property states that if aⁿ = 1 (mod p), then the order e_p(a) of a (mod p) divides n.

How can I go about proving this?

Additionally, if a is relatively prime to p, when does the congruence a^m = aⁿ (mod p) hold? Is there a proof for this as well?

Thanks!

 

[morphism]

Hint for 1: The division algorithm says we can write $n=qe_p(a)+r$. What can you say about r?

Hint for 2: If a is relatively prime to p, what is $e_p(a)$?

 

[squire636]

For the first one, r must equal zero, but I'm not sure how to show that it is true.

For the second, would the order e_p(a) = p-1 ?

 

[dodo]

For the second, would the order e_p(a) = p-1 ?

Not really; other integer less than p-1 could do the trick. Anyway, I believe morphism was simply trying to make you think about the very definition of 'order'. And what would you need to do to this definition in order to transform it into something like the premises that you are given.

 

[morphism]

As for the first problem, the division algorithm tells us that $0 \leq r < e_p(a)$. What can you do with this, squire636?