What is the significance of p being prime in proving Fermat's Theorem?

[PsychonautQQ]

Homework Statement

In proving Fermats theorem, I got confused trying to follow one of the steps.

theorem: If p is prime, then:
a^p~a (mod p).


part of proof:
multiply all the nonzero elements in Z_p by a to obtain
[a][1],[a][2],...,[a][p-1].
These are all distinct elements and none equal [0], so they must be the set of all nonzero elements [1],[2],...,[p-1] in some order. In particular, the products are the same and we obtain
([a]^(p-1))([1],[2],...,[p-1]) = ([1],[2],...,[p-1])

That fact that those last parts equal each other is confusing me, help?

Homework Equations

The Attempt at a Solution

 

[1MileCrash]

Don't you mean ([a]^(p-1))([1][2]...[p-1]) = ([1][2]...[p-1])?

And if that is what you mean, does your question still stand?

 

[drake]

Homework Statement

In proving Fermats theorem, I got confused trying to follow one of the steps.

theorem: If p is prime, then:
a^p~a (mod p).


part of proof:
multiply all the nonzero elements in Z_p by a to obtain
[a][1],[a][2],...,[a][p-1].
These are all distinct elements and none equal [0], so they must be the set of all nonzero elements [1],[2],...,[p-1] in some order. In particular, the products are the same and we obtain
([a]^(p-1))([1],[2],...,[p-1]) = ([1],[2],...,[p-1])

That fact that those last parts equal each other is confusing me, help?

Firstly, you can consider Euler's theorem too.
So we know that the set Q = { a*a_1 , a*a_2, .., a*a_p-1 } includes all elements in the set B = {a_1, a_2, .., a_p-1 } in mod p.
We know that from the property that
" if (a,p) = 1, we can get rid of the a in the equation :
a*a_i = a*a_j (mod p) ⇔ a_i = a_j (mod p) "

Which means that all elements in Q are distinct. And they are equal to one and only one of the elements in B.

So we get

(a*a_1) * (a*a_2) * .. * (a*a_p-1 ) = a_1 * a_2 *..* a_p-1 (mod p)
=>
a^(p-1) * A = A (mod p)
=>
a^(p-1) = 1 (mod p).

end of the proof.

 

[thelema418]

Don't you mean ([a]^(p-1))([1][2]...[p-1]) = ([1][2]...[p-1])?

And if that is what you mean, does your question still stand?

In addition to what is said above, you will need to state this restriction on the part you are doing: $p$ does not divide $a$, or $p \nmid a$.

The case of p divides a, $p \mid a$, will need to be discussed separately.

 

[drake]

As I told above;
" if (a,p) = 1, we can get rid of the a in the equation :
a*a_i = a*a_j (mod p) ⇔ a_i = a_j (mod p) "
you can't get rid of a if you don't have (a,p) = 1 property. And that prop. is given in the theorem.

 

[1MileCrash]

In addition to what is said above, you will need to state this restriction on the part you are doing: $p$ does not divide $a$, or $p \nmid a$.

The case of p divides a, $p \mid a$, will need to be discussed separately.

This is true, it may be given in the assignment since this case is trivial.

OP, the key here is that if p is prime, and a and b are both not multiples of p, then ab is not a multiple of p. Do you see why this makes the left product one of p-1 distinct classes none of which are [0]?