# Congruence proof

1. Sep 23, 2010

### kathrynag

1. The problem statement, all variables and given/known data
prove that if p is a prime number and a is any integer p|/a(p does not divide a), then the additive order of a modulo p is equal to p.

2. Relevant equations

3. The attempt at a solution
I know p|/ a says a$$\neq$$pn for an integer n.
The additive order of a modulo n is the smallest positive solution to ax$$\equiv$$0 mod n.
Let p be a prime number and p|/ a.
Then we can say (p, a)=1. That is p and a are relatively prime.
That's as far as I got.

2. Sep 23, 2010

### Office_Shredder

Staff Emeritus
ax=0 mod p means that p|ax. If p does not divide a, what can you infer?

3. Sep 23, 2010

### kathrynag

the additive order is p?

4. Sep 23, 2010

### Office_Shredder

Staff Emeritus
Why?

5. Sep 23, 2010

### kathrynag

Since p does not divide a, there are no multiples of a that equal p. Thus, p must be the smallest additive order.

6. Sep 23, 2010

### Office_Shredder

Staff Emeritus
p not dividing a means no multiple of p equals a, not that no multiple of a equals p. And I don't see what that has to do with additive order anyway... 4 does not divide six, there are no multiples of 4 or 6 that give the other one, but the additive order of 4 mod 6 is three, not six.

If p|ax and p does not divide a, and p is a prime, what must p divide? This is the defining property of prime numbers

7. Sep 23, 2010

### kathrynag

p divides x or p divides 1

8. Sep 23, 2010

### Office_Shredder

Staff Emeritus
p can't divide 1...

You should be able to finish the proof now

9. Sep 23, 2010

### kathrynag

Ok I think this makes a bit more sense for em now. Thanks!