Math Forum / Mathematics / Undergraduate Math / February 2007

Hi all,

I'm having a little bother clearly understanding a proof. Would be grateful
for feedback on my approach and on any tips/suggestions etc from you
knowledgables.

So I'm proving (supposedly) that "a^p ? a (mod p) where p is a prime and a
is an element of the naturals"

So I begin by trying to make things clearer for myself:

"a^p ? a (mod p)"
<==> "a^p - a = pc for some integer c"
<==> "(a^p - a) / p = c"
<==> "p divides a^p - a"
<==> "p divides a*(a^(p-1) - 1)"
Thus, if p divides a then a^p ? a (mod p) is true.

So we need to look at two cases.
Case1: P divides A
Case2: P does not divide A

Case1 -- P divides A:
If p divides a then a / p = c for come integer c.
a = p*c
a - 0 = p*c
a ? 0 (mod p)
Now, I've read that it follows that a^p ? 0 (mod p) but why? Is it just
because we can multiply both sides by mutiple a's?
And then now a^p ? a (mod p) is true? Why? since a = 0 and 0 is an element
of the naturals (let us let 0 be an element of the naturals)?
so then surely 0^p ? 0 mod p follows.
So does this have any particular signifiance? what happens when p divides a?
so in this case a = [0]_p?

Case 2 -- P does not divide A:
Then we have a remainder r, between 0 and p-1 inclusive.
So we have p-2 congruence classes, right? since [0]_p is for when P divides
A
so we have [1]_p, [2]_p, .... , [p-1]_p congruences classes that a can exist
in?
Now, I've seen in other proofs that they go on to multiply these by a and
then somehow they reach the conclusion that:
a.2a.3a.....(p-1)a = 1.2.3.....(p-1) (mod p)
I cannot see this at all.
Can someone please explain. I would be ever so appreciative of some help.
Thanks a lot in advance.