# Homework Help: Proof of Fermat's Theorm

1. Jun 21, 2014

### PsychonautQQ

1. The problem statement, all variables and given/known data
In proving Fermats Theorm, I got confused trying to follow one of the steps.

Theorm: 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 eachother is confusing me, help?

2. Relevant equations

3. The attempt at a solution

2. Jun 21, 2014

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

3. Jun 21, 2014

### drake

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.

4. Jun 21, 2014

### thelema418

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.

5. Jun 21, 2014

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

6. Jun 21, 2014

### 1MileCrash

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