This page aims to present Fermat's little theorem, and to prove it

Statement of Fermat's little theorem

We will see it stated in two different ways:

Statement 1

Let p be Prime number. Then, for any integer a:

a^p \equiv a [p]

Statement 2

Let p be a prime number. So, for all of a who is not a multiple from p:

a^{p-1} \equiv 1 [p]

With divisors, it can also be written:

p | a^{p-1}-1

Demonstration

We are going to demonstrate statement 1 which comes to us from Euler and Leibniz.
Remark : As with Fermat's great theorem, he did not prove this theorem.

Lemma

Let's show that:

(k+1)^p \equiv k^p +1 [p]

To do this, let's use Newton's binomial:

(k+1)^p =\sum_{i=0}^p \biname{p}{i} k^i

Is

1 \leq i \leq p -1

We have the following formula:

\begin{array}{ll} \displaystyle\binom{p}{i} & = \displaystyle \dfrac{p!}{i!(pi)!}\\ & = \displaystyle\dfrac{p}{i} \dfrac{(p-1)!}{(i-1)!(pi)!}\\ & = \displaystyle\dfrac{p}{i} \biname{p-1}{i-1} \end {array}

So we have :

i\binom{p}{i} = p \binom{p-1}{i-1}

Yet

i \wedge p = 1

because p is prime.
So we have :

\forall 1 \leq i \leq p-1, p | \biname{p}{i} 

So if we go back modulo p:

\begin{array}{ll} (k+1)^p& =\displaystyle\sum_{i=0}^p \binom{p}{i} k^i\\ &\displaystyle = 1+k^p + \sum_{i=1}^{p-1} \binom{p}{i} k^i\\ & \equiv 1+k^p [p] \end{array}

Proof by induction

Let p be a fixed prime number. Let us then prove the result by induction on a. Let's start with initialization which is easy. We have :

0^p \equiv 0 [p]

Now let's move on to heredity. Let a be a fixed integer for which the property is assumed to be true. Thanks to the lemma:

(k+1)^p \equiv k^p +1 [p]

However, by induction hypothesis

k^p +1 \equiv k +1 [p]

So,

(k+1)^p \equiv k+1 [p]

Which concludes heredity. We have therefore clearly demonstrated the result in the case by induction:

\forall a \in \mathbb {N}, a^p \equiv a [p]

It is also valid for relative integers:

• Either we do a recurrence on -a.
• Either we use the following property

(-a)^p \match -a^p \match -a [p]

When p is odd, we have (-a)^p ≡ -a^p [p]. And when p = 2, we always have: -a ≡ a [2] which suffices for our property.

Equivalence between the two statements

direct direction :
We have :

p | a^p - a = a(a^{p-1}-1)

Now, since a is not a multiple of p.

p \wedge a = 1

So, by Gauss's theorem:

p |a^{p-1}-1

Return direction :
We have :

a^{p-1}\equiv 1 [p]

We multiply by a on each side:

a^{p}\equiv a[p]

The case where a is a multiple of p is obvious.

Corrected exercises

Exercise 911

Let's start by using Fermat's little theorem with p = 13
We have :

a^{13} \equiv a [13]

Which means that we have:

13 |a^{13}-a

We will now show that 2 divides our number. It is easy to see that a and its powers we even parity. Therefore

2 |a^{13}-a

Urban artist

13 \wedge 2 = 1

So :

26 = 13 \times 2 | a^{13}-a

This concludes this first exercise.

Exercise 912

Here too we will use Fermat's little theorem. We have, according to statement 2:

3^{6} =3^{7-1}\equiv 1 [7]

Now, by raising on each side at the power :

(3^6)^n \match 1^n [7] \iff 3^{6n} \match 1 [7]

We then have the desired result:

7 |3^{6n}-1

Exercise 913

We used Fermat's little theorem with p = 5 which is a prime number:

n^5 \equiv n [5]

So :

5 |n^5 -n 

Next, let's factor. We have :

\begin{array}{ll}
n^5-n &= n(n^4-1) \\
&= n(n^2-1)(n^2+1)\\
&=n(n-1)(n+1)(n^2+1)
\end{array}

We have 3 consecutive integers, n-1, n and n+1. 3 divides one of these three numbers:

3 | n(n-1)(n+1) \Rightarrow 3|n^5-n

We have 2 consecutive integers n and n+1. 2 divides one of these 2 numbers.

2 |n(n+1) \Rightarrow 2|n^5-n

Their GCD is 1. So

6 | n^5 - n

The GCD of 6 and 5 is 1. So there too:

30 = 6 \times 5 |n^5-n

Which is the desired result.

Did you like this article? Find our latest articles on the same theme:

• Even and odd functions: lessons and corrected exercises
• Poisson's Law: Corrected lessons and exercises
• Geometric law: Corrected lessons and exercises
• The transpose of a matrix: Courses and properties
• Catalan numbers: Properties and applications