Some examples:

Let's use p=7
  • $2^{\small{7-1}}-1%3D2^6-1%3D64-1%3D63,$ a multiple of 7
  • $3^{\small{7-1}}-1=3^6-1=729-1=728,$ a multiple of 7
  • $4^{\small{7-1}}-1=4^6-1=4096-1=4095,$ a multiple of 7
Let's use p=5
  • $2^{\small{5-1}}-1=2^4-1=16-1=15,$ a multiple of 5
  • $3^{\small{5-1}}-1=3^4-1=81-1=80,$ a multiple of 5
  • $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, $a^p-a$ 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 public-key cryptosystem.

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?


Proof

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 $F,$ the other will give $a^{p-1}F,$ and so these are equal.

So suppose we have a number $a$ which is between 1 and $p-1$ inclusive. Everything is being done modulo p.

We start by looking at the product $(p-1)!$ which is $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, $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

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,~\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

is the same as Equation (1) shows that $P{\equiv}F$ (because it's the same product in a different order)

Equation (2) shows that $P{\equiv}a^{p-1}F$

So $F{\equiv}a^{p-1}F$

Now we can multiply by $F^{-1}$ and we can see that $1{\equiv}a^{p-1}$ which is the result we wanted!


EuclideanAlgorithm
Factorial
(none) AlgebraicGeometry
FermatNumber
FermatPrime
FermatsLastTheorem
ModuloArithmetic PierreDeFermat

You are here

FermatsLittleTheorem
Euler
FermatsLastTheorem
Integer
PrimeNumber
EuclideanAlgorithm (none) Calculus
CompositeNumber
CountingNumber
DiophantineEquation
Divisor
FamousPeople
GraphTheory
PierreDeFermat
PrimePair
Pythagoras
RealNumber
WholeNumber

Local neighbourhood - D3


Last change to this page
Full Page history
Links to this page
Edit this page
  (with sufficient authority)
Change password
Recent changes
All pages
Search