Petit théorème de Fermat
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 :
.
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 :
.
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
. 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.
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
, 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.
Fiches de cours les plus recherchées
Découvrir le reste du programme
Des profs en ligne
- 6j/7 de 17 h à 20 h
- Par chat, audio, vidéo
- Sur les matières principales
Des ressources riches
- Fiches, vidéos de cours
- Exercices & corrigés
- Modules de révisions Bac et Brevet
Des outils ludiques
- Coach virtuel
- Quiz interactifs
- Planning de révision
Des tableaux de bord
- Suivi de la progression
- Score d’assiduité
- Un compte Parent
Message envoyé
