# Proof of the Order Divisibility Property

1. Mar 12, 2012

### squire636

The Order Divisibility Property states that if an = 1 (mod p), then the order ep(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 am = an (mod p) hold? Is there a proof for this as well?

Thanks!!

2. Mar 12, 2012

### 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)$?

3. Mar 13, 2012

### 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 ep(a) = p-1 ?

4. Mar 13, 2012

### dodo

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.

5. Mar 13, 2012

### 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?