Current

Other

Index

Printing

The fermat's little theorem

Let \(a \in \mathbb{Z}\) be an integer and \(p \in \mathbb{P}\) a prime number.

Fermat's small theorem tells us that:

Demonstration

The fermat's little theorem

1. By recurrence

Let \(a \in \mathbb{Z}\) be an integer and \(p \in \mathbb{P}\) a prime number.

Let show that the following statement \((S_a)\) is true:

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (S_a) $$

1. First term calculation

Let verify if is true for the first term, that is to say for \( a = 0 \).

$$ 0^p \hspace{0.2em} \equiv \hspace{0.2em} 0 \hspace{0.2em} \bigl[p\bigr] $$

\((S_0)\) is true.

2. Heredity

1. In the natural numbers set\(: \mathbb{N} \)

Let \( k \in \mathbb{N} \) be a natural number.

Let us assume that \((S_k)\) is true for all \( k \).

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k}) $$

We will verify that is also the case for \((S_{k + 1})\).

$$ (k+1)^p \equiv k+1 \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k + 1}) $$

Let us calculate \( (k+1)^p\).

With the Newton's binomial, we know that:

$$\forall n \in \mathbb{N}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{R}^2,$$

$$ (a + b)^n = \sum_{p = 0}^n \binom{n}{p} a^{n-p}b^p $$

So,

$$ (k+1)^p = k^p + \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} + 1 \qquad (1) $$

Well, for all \( p, i \), with \( 1 \leqslant i \leqslant p \) we can apply the binomial's pawn formula :

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

But, we know by the Gauss' theorem that:

$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3, \enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

In our case,

$$ \forall i \in \hspace{0.05em} 1 \leqslant i \leqslant (p-1),$$
$$ p / i\binom{p}{i} \enspace et \enspace p \wedge i = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p / \binom{p}{i} $$

If \( p \) divides the \( \binom{p}{i} \) binom, then \( p \) also divides the central member of \( (1) \).

$$ (k+1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _\text{\( = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{N} \)} \hspace{0.1em} + 1 \qquad (1) $$

So,

$$ \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} \equiv 0 \bigl[p\bigr] $$

And as our recurrence hypothesis is:

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

These are all the congruences for the \( (k+1)^p \) calculation:

$$ (k+1)^p = \underbrace{ k^p } _\text{\( \equiv \hspace{0.2em} k \hspace{0.2em} [p] \)} + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _\text{\( \equiv \hspace{0.2em} 0 \hspace{0.2em} [p] \)} \hspace{0.2em} + 1 $$

We then have by addition of the congruences:

$$ (k+1)^p \equiv k + 1 \bigl[p\bigr] \qquad (S_{k + 1}) $$

Thus, \((S_{k + 1})\) est vraie.

2. In the relative numbers set\(: \mathbb{Z} \)

Here, we have to prove it in the contrary direction, to verify if it is still true inside the \( \mathbb{Z}\) set.

In other words, let verify that \((P_{k - 1})\) is true.

$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

Let us calculate \( (k-1)^p \).

$$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} + (-1)^p \qquad (P_{k - 1}) $$

\(p\) being a prime number by hypothesis, it will always be odd, and then:

$$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} -1 \qquad (1') $$

Likewise, if \( p \) divise the \( \binom{p}{i} \) binom, then \( p \) also divides the central member of \( (1') \) :

$$ (k-1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _\text{\( = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{Z} \)}\hspace{0.2em} - 1 \qquad (1') $$

Even if this central member contains an alternance of positive and negative numbers, its general quotient \( Q \) remains inside the \( \mathbb{Z} \) set.

We will also, like previously:

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

So these are all the congruences for the \( (k-1)^p \) calculation:

$$ (k-1)^p = \underbrace{ k^p } _\text{\( \equiv \hspace{0.2em} k \hspace{0.2em} [p] \)} + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _\text{\( \equiv \hspace{0.2em} 0 \hspace{0.2em} [p] \)} \hspace{0.2em} - 1 $$

And finally,

$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

\((P_{k - 1})\) est vraie.

3. Conclusion

The statement \((S_a)\) is true for its fisrt term \(a_0 = 0\) and it's hereditary from terms to terms for all \(k \in \mathbb{Z}\), upwards and downwards.

By the recurrence principle, that statement is true for all \(a \in \mathbb{Z}\).




And finally,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad \bigl(\text{Fermat's little theorem} \bigr) $$

This therefore means that:

$$ p / (a^p - a) \Longrightarrow p / a(a^{p - 1} - 1) $$

Now, we know from the Gauss' theorem that:

$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3, \enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

So on the other hand, if \((a \land p = 1)\), then:

$$ p / (a^{p - 1} - 1) $$

And also,

$$ a^{p - 1} - 1 \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

And as a result,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, \enspace (a \land p = 1), $$
$$ a^{p - 1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$

Go to the top of the page