Some examples:
Let's use p=7
 $2^{\small{71}}1=2^61=641=63,$ a multiple of 7
 $3^{\small{71}}1=3^61=7291=728,$ a multiple of 7
 $4^{\small{71}}1=4^61=40961=4095,$ a multiple of 7
Let's use p=5
 $2^{\small{51}}1=2^41=161=15,$ a multiple of 5
 $3^{\small{51}}1=3^41=811=80,$ a multiple of 5
 $4^{\small{51}}1=4^41=2561=255,$ a multiple of 5


Fermat's little theorem (not to be confused with Fermat's last theorem)
states that if p is a prime number, then for any integer a, $a^pa$ will
be evenly divisible by p. This can be expressed in the notation of modulo arithmetic as follows:
$a^p\equiv{a}$ (mod p)
A variant of this theorem is stated in the following form:
Fermat's little theorem is the basis for the Fermat primality test.
Euler's extension of Fermat's little theorem is the basis of the RSA publickey cryptosystem.
 If n is a positive integer
 and $\phi(n)$ is how many numbers that are
 less than n and have no factors in common with n,
 then if a is one of those numbers,
 then $a^{\small\phi(n)}1$ is a multiple of n.
Let p be a prime. What we're going to do is write down one product, and then evaluate it
in two different ways. One way will give some number $F,$ the other will give $a^{p1}F,$
and so these are equal.
Everything is being done modulo p.
So, let's start by looking at the product $(p1)!$ which is $F=1\text{x}{2}\text{x}\ldots\text{x}(p1).$
This is some number which, because we are working modulo a prime, has a multiplicative inverse, $F^{1}.$
Now let's look at the product
 $P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p1)a).$
This is the magic formula that we'll evaluate in two different ways.
If $ma{\equiv}na,$ multiplying by $a^{1}$ shows that $m=n.$
That means that each of the terms a, 2a, 3a, ... (p1)a must be different. 

Firstly, each of the elements here are different. The element a has a multiplicative
inverse, so multiplying all the number from 1 up to p1 can be undone. That means we
can't get the same answer twice, so they're all different. That means that the product
is just the same elements multiplied in a different order, and so the product is again F.
But let's rearrange it to bring all the a's to the front. Then
 $P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p1)a)\quad\quad$ (equation 1)
is the same as
 $P{\equiv}a^{p1}(1)\text{x}(2)\text{x}(3)\text{x}\ldots\text{x}(p1)\quad\quad$ (equation 2)
Equation (1) shows that $P{\equiv}F$ (because it's the same product in a different order)
Equation (2) shows that $P{\equiv}a^{p1}F$
So $F{\equiv}a^{p1}F$
Now we can multiply by $F^{1}$ and we can see that $1{\equiv}a^{p1}$
which is the result we wanted!
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Search /
Change password /
Logout