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?


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!

(none) AlgebraicGeometry
ModuloArithmetic PierreDeFermat

You are here

EuclideanAlgorithm (none) Calculus

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