# Math Help - mods with prime powers

1. ## mods with prime powers

Hey guys, cant get my head around this fact .If p is a prime, then $a^{p-1}$ = 1 (mod p) provided a $\not\equiv$ 0 mod p. If someone could explain with an clear example of some sort it would be much appreciated.

2. Originally Posted by jvignacio
Hey guys, cant get my head around this fact .If p is a prime, then $a^{p-1}$ = 1 (mod p) provided a $\not\equiv$ 0 mod p. If someone could explain with an clear example of some sort it would be much appreciated.
This result is called Fermat's Little Theorem. I suppose the reason that it holds is because every number less than p is coprime to p and so there are no zero divisors. So every element has an inverse, but there is not enough space for it not to be of this form.

For an example, try working mod 5 (this is small enough to work with).

$1^4 = 1$
$2^4 = 16 = 15+1 \equiv 1 \text{ mod }5$
$3^4 = 81 = 80+1 \equiv 1 \text{ mod }5$
$4^5 = 16^2 \equiv 1^2 \equiv 1 \text{ mod }5$.

Alternatively, plug the following code into maple,

p:=7;
for n from 1 to (p-1) do
a:=p^{n-1}:
print(a, a mod p):
od:

and change the number p to be any prime.

There actually exists a very beautiful proof of this result, which can be found on wikipedia. (Actually, this page contains many beautiful proofs of the theorem. If you really want to understand the theorem, read through as many of these proofs as you have the knowledge to grasp.)

3. Originally Posted by Swlabr
This result is called Fermat's Little Theorem. I suppose the reason that it holds is because every number less than p is coprime to p and so there are no zero divisors. So every element has an inverse, but there is not enough space for it not to be of this form.

For an example, try working mod 5 (this is small enough to work with).

$1^4 = 1$
$2^4 = 16 = 15+1 \equiv 1 \text{ mod }5$
$3^4 = 81 = 80+1 \equiv 1 \text{ mod }5$
$4^5 = 16^2 \equiv 1^2 \equiv 1 \text{ mod }5$.

Alternatively, plug the following code into maple,

p:=7;
for n from 1 to (p-1) do
a:=p^{n-1}:
print(a, a mod p):
od:

and change the number p to be any prime.

There actually exists a very beautiful proof of this result, which can be found on wikipedia. (Actually, this page contains many beautiful proofs of the theorem. If you really want to understand the theorem, read through as many of these proofs as you have the knowledge to grasp.)
Cheers, makes a lot more sense now!