Petit théorème de Fermat
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
1. Préliminaire
Théorème
se lit "modulo p".
Preuve
Utilisons la formule du binôme :
.
Or, étant donné un entier
,
,
on trouve que
. Cela prouve que p divise
.
Or, p est premier avec k! puisqu'on a
.
Donc, d'après le théorème de Gauss, p divise
. En d'autres termes
.
Cela implique :
.
Soit a un entier naturel et p un nombre premier.
On a :
.
On a :


Preuve
Utilisons la formule du binôme :

Or, étant donné un entier


on trouve que


Or, p est premier avec k! puisqu'on a

Donc, d'après le théorème de Gauss, p divise


Cela implique :

2. Le petit théorème de Fermat
Théorème
Remarque
Ce théorème a été énoncé en 1640 puis démontré en 1683 par Leibniz et de nouveau démontré par Euler en 1736.
Preuve
Nous allons démontrer ce théorème par récurrence sur l'entier a. Pour cela, fixons un nombre premier p et raisonnons modulo p.
Soit Pa la phrase "
".
Pour a = 0, on a bien
. P0 est donc vraie.
Soit a un entier naturel quelconque. Supposons que Pa soit vraie et démontrons Pa+1 :
d'après le
théorème précédent.
d'après l'hypothèse
de récurrence.
On en déduit que
et donc Pa+1 est
vraie.
Bilan : Pa est vraie pour tout entier naturel a et p quelconque.
Soit a un entier naturel et p un nombre premier ne
divisant pas a. Alors :
.

Remarque
Ce théorème a été énoncé en 1640 puis démontré en 1683 par Leibniz et de nouveau démontré par Euler en 1736.
Preuve
Nous allons démontrer ce théorème par récurrence sur l'entier a. Pour cela, fixons un nombre premier p et raisonnons modulo p.
Soit Pa la phrase "

Pour a = 0, on a bien

Soit a un entier naturel quelconque. Supposons que Pa soit vraie et démontrons Pa+1 :


On en déduit que

Bilan : Pa est vraie pour tout entier naturel a et p quelconque.
3. Un corollaire
Théorème
Preuve
D'après le théorème précédent, on sait que p divise
, donc
.
Ne divisant pas a, p est premier avec a. D'après le théorème de Gauss p divise
, donc
modulo p, ce qu'il fallait démontrer.
Remarque
Le petit théorème de Fermat et son corollaire sont à la source de certaines méthodes de cryptographie, notamment la méthode RSA (initiales des inventeurs : Ronald Rivest, Ali Shamir et Leonard Adleman dans les années 1970) et la méthode de Tahar El Gamal, au milieu des années 1980.
Soit a un entier naturel et p un nombre premier ne
divisant pas a.
Alors :
.
Alors :

Preuve
D'après le théorème précédent, on sait que p divise


Ne divisant pas a, p est premier avec a. D'après le théorème de Gauss p divise


Remarque
Le petit théorème de Fermat et son corollaire sont à la source de certaines méthodes de cryptographie, notamment la méthode RSA (initiales des inventeurs : Ronald Rivest, Ali Shamir et Leonard Adleman dans les années 1970) et la méthode de Tahar El Gamal, au milieu des années 1980.
Vous avez obtenu75%de bonnes réponses !