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

Printable View

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

- Apr 19th 2010, 12:52 AMSwlabr
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).

$\displaystyle 1^4 = 1$

$\displaystyle 2^4 = 16 = 15+1 \equiv 1 \text{ mod }5$

$\displaystyle 3^4 = 81 = 80+1 \equiv 1 \text{ mod }5$

$\displaystyle 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.) - Apr 19th 2010, 01:02 AMjvignacio