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

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

*** then EQN:a^{p-1}-{1}

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!