Edit made on December 05, 2008 by ColinWright at 13:22:13
Deleted text in red /
Inserted text in green
WW
HEADERS_END
[[[>50
!!! Some examples:
Let's use /p=7/
* EQN:2^{\small{7-1}}-1=2^6-1=64-1=63, a multiple of 7
* EQN:3^{\small{7-1}}-1=3^6-1=729-1=728, a multiple of 7
* EQN:4^{\small{7-1}}-1=4^6-1=4096-1=4095, a multiple of 7
Let's use /p=5/
* EQN:2^{\small{5-1}}-1=2^4-1=16-1=15, a multiple of 5
* EQN:3^{\small{5-1}}-1=3^4-1=81-1=80, a multiple of 5
* EQN:4^{\small{5-1}}-1=4^4-1=256-1=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, EQN:a^p-a will
be evenly divisible by p. This can be expressed in the notation of modular arithmetic as follows:
be evenly divisible by p. This can be expressed in the notation of modulo arithmetic as follows:
EQN:a^p\equiv{a} /(mod/p)/
A variant of this theorem is stated in the following form: if p is a prime number
and a is an integer coprime to p, then EQN:a^{p-1}-{1} will be evenly divisible by p.
A variant of this theorem is stated in the following form:
* If p is a prime number
** and /a/ is an integer with no factors in common with /p/
*** then EQN:a^{p-1}-{1} is a multiple of /p./
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 public-key cryptosystem.
* If /n/ is a positive integer
** and EQN:\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 EQN:a^{\small\phi(n)}-1 is a multiple of /n./
----
!! Proof
[[[>30
This proof can be adapted to prove Euler's result by taking the product of all the numbers
co-prime to /n,/ rather than using the numbers from /1/ to /p-1./ ]]]
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 EQN:F, the other will give EQN:a^{p-1}F,
and so these are equal.
[[[>
In the integers modulo a prime, every number _
from 1 to /p-1/ has a multiplicative inverse. _ _
We'll use that several times. ]]]
Everything is being done modulo /p./
So, let's start by looking at the product EQN:(p-1)! which is EQN:F=1\text{x}{2}\text{x}\ldots\text{x}(p-1).
This is some number which, because we are working modulo a prime, has a multiplicative inverse, EQN:F^{-1}.
Now let's look at the product
* EQN:P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p-1)a).
This is the magic formula that we'll evaluate in two different ways.
[[[>50 If EQN:ma{\equiv}na, multiplying by EQN:a^{-1} shows that EQN:m=n. _
That means that each of the terms /a,/2a,/3a,/.../(p-1)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 /p-1/ 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
* EQN:P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p-1)a)\quad\quad (equation 1)
is the same as
* EQN:P{\equiv}a^{p-1}(1)\text{x}(2)\text{x}(3)\text{x}\ldots\text{x}(p-1)\quad\quad (equation 2)
Equation (1) shows that EQN:P{\equiv}F (because it's the same product in a different order)
Equation (2) shows that EQN:P{\equiv}a^{p-1}F
So EQN:F{\equiv}a^{p-1}F
Now we can multiply by EQN:F^{-1} and we can see that EQN:1{\equiv}a^{p-1}
which is the result we wanted!