Edit made on January 23, 2013 by ColinWright at 18:34:26
Deleted text in red
/
Inserted text in green
WW WM
HEADERS_END
[[[>50
!!! Some examples:
Let's use /p=7/
* EQN:2^{\small{7-1}}-1%3D2^6-1%3D64-1%3D63, 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 modulo arithmetic as follows:
EQN:a^p\equiv{a} /(mod/p)/
A variant of this theorem is stated in the following form: if
* If p is a prime number
** and a /a/ is an integer coprime to p, with no factors in common with /p/
*** then EQN:a^{p-1}-{1} will be evenly divisible by p. 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.
[[[>50
!! Page Challenge
This theorem only ~works in one direction. Every prime
satisfies the equation, but there are non-primes that
also satisfy it.
Can you find one?
]]]
* 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.
So suppose we have a number EQN:a which is between 1 and EQN:p-1 inclusive.
Everything is being done modulo /p./
We 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}.
[[[>
In the integers modulo a prime, every number _
from 1 to /p-1/ has a multiplicative inverse. _ _
We'll use that several times. ]]]
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.
[[[> If EQN:ma{\equiv}na, multiplying by EQN:a^{-1} shows that EQN:m=n. _
That means that each of the terms EQN:a,~2a,~3a,~\ldots~(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!