NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 24/09/2022 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Théorie des Nombres
Débutants Général	Le petit théorème de Fermat				Glossaire Général
INDEX Théorie des nombres	Découverte	Exploration	Démonstration		Généralisation
	Perles et collier	Applications	Puissances		Avec Pascal
		Sommaire de cette page >>> Magie du théorème >>> Approche >>> Modulo et résidus >>> Puissance 3 >>> Puissance 4 >>> Puissance 5 >>> Puissance 7		>>> Notation finale >>> Formulation classique >>> Exemples de calculs >>> Historique >>> Anglais

PETIT THÉORÈME DE FERMAT

Nous allons approcher par l'expérience (et amusement) le Petit Théorème de Fermat (PTF) relatif à la divisibilité des nombres.

L'expérience est relativement simple et très amusante. Instructive de surcroît ! Laissez-vous prendre par la main… Vous aurez la satisfaction de comprendre un point important de la théorie des nombres.

Pour ceux qui ont des notions sur le modulo, vous pouvez allez directement voir Modulo et Fermat.

Impatient ! Tout de suite, donnez-moi la formulation du théorème.

D'un coup d'œil

Petit théorème de Fermat avec p premier ne divisant pas a

Théorème d'Euler (généralisation) avec (a, m) = 1

Exemple

Soit le nombre 5 à la puissance 7; 7 étant un nombre premier. Ce nombre est un multiple de 7 plus 5; 5 étant le nombre de départ. La puissance et le nombre ont le même reste lorsque divisés par un nombre premier.

C'est ce genre de découverte qui fait bouillir

les sangs d'un mathématicien.

Marcus du Sautoy – La symphonie des nombres premiers

Cette formule se lit: divisés par un nombre premier p un nombre et sa puissance p ont le même reste.

Exemple: 5³ = 125, divisé par 3, reste 2 et 5 divisé par 3, reste 2.

Sous forme de koan Zen

Voir Citations de maths / Pensées & humour

La magie du théorème en un coup d'œil
Principe p étant un nombre premier: Un nombre et sa puissance p, divisés par p donnent le même reste.	Exemple Trouvez le reste de la division de 8^7 par 7: Il suffit de donner le reste de la division de 8 par 7, soit 1. En effet 8^7 = 2 097152 = 299 593 x 7 + 1
Comme souvent en maths, l'idée est de trouver des routes plus simples, moins fastidieuses. Ici on remplace la voie du bas, difficile à calculer, par celle du haut qui donne un résultat immédiat.

Voir Magie

Exemples de divisibilités

Toutes ces configurations en puissance 3 sont divisibles par 3 (petit théorème de Fermat) et certaines aussi par le nombre (bleu). Les exclus sont les multiples de 3 (lignes de couleur bleu clair).

Voir Divisibilité

Approche

D'abord 

Observons le tableau suivant qui donne la puissance 7 des nombres a de 1 à 6
et, également, le reste de leur division par 7 lui-même

a	a ^7	a ^7 / 7	Reste
1	1	0	1
2	128	18	2
3	2 187	312	3
4	16 384	2 340	4
5	78 125	11 160	5
6	279 936	39 990	6

Extraordinaire !

Le reste est égal au nombre de départ.

C'est le constat que Fermat a dû faire.

Mais d'une curiosité, il en a tiré un théorème.

Ce pourrait être du style:

Divisé par p, un nombre et sa puissance p donnent le même reste.

MODULO ET RÉSIDUS
Modulo m	Je divise par m et ne m'intéresse qu'au reste.	15 mod 12 = 3 Pensez à 15 heures modulo 12 3 heures.
Résidu b	Le reste b de cette division.	3 est le reste ou résidu.

Voir explications complètes en Modulo 

PUISSANCE jusqu'à 3 modulo 3

Procédons par étapes

Nombres à la puissance 3.

On veut obtenir les résidus, et en dégager les propriétés.

Étape 1 - Exploration de la puissance des nombres jusqu'à n = 3

Calculons la puissance p de 1 à 3

de tous les nombres a de 1 à 3.

m = 3	a =1	a =2	a =3
n = 1	1^1 = 1	2^1 = 2	3^1 = 3
n = 2	1^2 = 1	2^2 = 4	3^2 = 9
n = 3	1^3 = 1	2^3 = 8	3^3 = 27

Étape 2 - Résidus en modulo 3

Calculons les restes de la division par 3 de chacun des nombres du tableau.
Soit " les résidus de N = a ^p modulo m avec m = 3 ".

m = 3	a = 1	a = 2	a = 3
n = 1	1^1 mod 3 = 1	2^1 mod 3 = 2	3^1 mod 3 = 0
n = 2	1^2 mod 3 = 1	2^2 mod 3 = 1	3^2 mod 3 = 0
n = 3	1^3 mod 3 = 1	2^3 mod 3 = 2	3^3 mod 3 = 0

C'est le même tableau que précédemment, mais en y reportant que les restes de la division par m = 3.

On va éliminer tout de suite la colonne triviale qui donne un reste évident de zéro, car a = m.

Étape 3 – Divisibilité

On va écrire ces résultats autrement.
Du nombre de départ, on soustrait son reste dans la division par 3.
Évidemment, le reste de la division par 3 du nouveau nombre devient nul!

En effet

4 / 3 donne un reste de 1, et, en retranchant le reste.

(4 – 1) / 3 donne un reste de 0.

Voici le tableau avec ce nouveau look

m = 3	a = 1	a = 2
n = 1	(1^1 – 1) mod 3 = 0	(2^1 – 2) mod 3 = 0
n = 2	(1^2 – 1) mod 3 = 0	(2^2 – 1) mod 3 = 0
n = 3	(1^3 – 1) mod 3 = 0	(2^3 – 2) mod 3 = 0

Étape 4 - Simplification de l'écriture

Le modulo m = 3 est sous-entendu: il est rappelé en rouge dans le coin du tableau

m = 3	a = 1	a = 2
n = 1	1^1 – 1	2^1 – 2
n = 2	1^2 – 1	2^2 – 1
n = 3	1^3 – 1	2^3 – 2

Rappel de notre notation: tous les nombres internes au tableau sont divisibles par 3.

Notons tout de suite les chiffres en rouge dans le cœur du tableau:

en puissance n = 2, on a toujours 1

en puissance n = 3, on a des chiffres qui tous valent a

Étape 5 – Propriétés

La ligne 1, de la puissance n = 1, est triviale : un nombre à la puissance 1 redonne le nombre. La différence est nulle.

La ligne 3, de la puissance n = m, redonne les nombres du départ: on dit qu'alors le " tableau est complètement reconstitué ". Nous verrons que cette propriété peut, parfois, apparaître plutôt sur une ligne.

La ligne 2, de la puissance n = m – 1, donne un résidu égal à 1.

Étape 6 – Expressions littérales

On remplace les chiffres par les lettres: n = 3, devient n = m

m = 3	a = 1	a = 2	On lit:
n = 1	1^1 – 1	2^1 – 2
n = m – 1	a^m–1 – 1	a^m–1 – 1	(a^m–1 – 1) mod m = 0 Un nombre a, à la puissance m–1 diminué de 1, est divisible par m.
n = m	a^m – a	a^m – a	(a^m – a) mod m = 0 Un nombre a, à la puissance m diminué de a, est divisible par m.

Vrai dans cet exemple! Est-ce toujours vrai? C'est ce que nous allons voir.

Remarquons toujours nos chiffres en rouge:

en n = m – 1 , on a 1.

en n = m, on a des chiffres qui valent a.

En jaune, on rappelle la lecture du tableau avec le modulo.

Étape 7 - Théorème ? On peut déjà imaginer des propriétés générales.

Avec diverses formulations équivalentes

aⁿ – a divisé par m

donne 0 comme reste.

aⁿ – a est un multiple de m.

Tout nombre a à la puissance m

divisé par m donne un reste a

aⁿ / m donne a comme reste

aⁿ º a _{mod m}

Mais attention à ne pas généraliser trop vite !!!

Nous allons voir que ça n'est pas complètement exact.

Étape 8 – Nous avons vu le cas de m = 3, voyons le même tableau avec m = 4 …

PUISSANCE jusqu'à 4 modulo 4

Tableau avec m = 4

m = 4	a =1	a =2	a =3
n = 1	1^1 – 1	2^1 – 2	3^1 – 3
n = 2	1^2 – 1	2^2 – 0	3^2 – 1
n = 3	1^3 – 1	2^3 – 0	3^3 – 3
n = 4	1^4 – 1	2^4 – 0	3^4 – 1

On rappelle la lecture du tableau:

Tous les nombres internes au tableau sont divisible par 4 (= 0 mod 4)..

Exemple: 3² – 1 = 9 – 1 = 8 et 8 est divisible par 4.

Expressions littérales

m = 4	a = 1	a = 2	a = 3
n = 1	a^1 – 1	a^1 – 2	a^1 – 3
n = 2	a^2 – 1	a^2 – 0	a^2 – 1
n = 3 = m –1	a^m–1 – 1	a^m–1 – 0	a^m–1 – 3
n = 4 = m	a^m – 1	a^m – 0	a^m – 1

Propriétés

Avec un nombre non premier comme m = 4, nos belles propriétés ne semblent pas se reproduire. La colonne 2 donne 0 (sauf première ligne).

La ligne n = m ne donne pas la belle liste des résidus égaux au nombre de départ a.

Les lignes 2 et 4 (puissances 2 et 4) sont identiques.

Il semble que 2, qui divise 4, entraîne la formation de sous tableaux.

Conclusion

Notre tentative de théorème ne semble par marcher avec un nombre composé, c'est-à-dire non premier.

Continuons notre exploration avec m = 5, qui est premier comme 3

Allons-nous retrouver les mêmes propriétés intéressantes que celles obtenues avec 3?

PUISSANCE jusqu'à 5 modulo 5

Tableau avec m = 5, ou plutôt p = 5, pour bien témoigner du fait que 5 est premier

p = 5	a = 1	a = 2	a = 3	a = 4
n = 1	1^1 – 1	2^1 – 2	3^1 – 3	4^1 – 4
n = 2	1^2 – 1	2^2 – 4	3^2 – 4	4^2 – 1
n = 3	1^3 – 1	2^3 – 3	3^3 – 2	4^3 – 4
n = 4	1^4 – 1	2^4 – 1	3^4 – 1	4^4 – 1
n = 5	1^5 – 1	2^5 – 2	3^5 – 3	4^5 – 4

Ouais ! ! !  Ça marche, nous retrouvons nos singularités sur les deux dernières lignes. L'effet nombre premier!

Expressions littérales

p = 5	a = 1	a = 2	a = 3	a = 4
n = 1	a^1 – a	a^1 – a	a^1 – a	a^1 – a
n = 2	a^2 – 1	a^2 – 4	a^2 – 4	a^2 – 1
n = 3	a^3 – 1	a^3 – 3	a^3 – 2	a^3 – a
n = 4 = p –1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1
n = 5 = p	a^p – a	a^p – a	a^p – a	a^p – a

Propriétés

On retrouve la ligne n = 5 = p qui semble donner une propriété générale

un nombre à la puissance p moins ce nombre est divisible par p.

a ^p – a est divisible par p

pour tout p premier.

C'est le petit théorème de Fermat qui pointe son nez !

La ligne n = 4 = p – 1 aussi, semble nous montrer une propriété:

a ^p–1 – 1 est divisible par p

pour tout p premier et pour tout a premier avec p.

Les deux formulations sont proches. Normal ! La seconde est la première dans laquelle on divise tout par a.

En effet, en effectuant la division Or, le petit théorème de Fermat dit.	(a ^p – a) / a = a ^p–1 – 1 (a ^p – a) = k.p
D'une manière générale p est premier et ne peut être divisé par a C'est le facteur k qui l'est.	a ^p–1 – 1 = k.p / a a ^p–1 – 1 = k/a . p a ^p–1 – 1 = k' . p
Sauf, si a est un multiple de p Alors c'est p qui est divisible par p (k peut l'être aussi, mais on n'en sait rien) Dans ce cas pas de conclusion possible.	a = h . p a ^p–1 – 1 = k . p / (h.p) a ^p–1 – 1 = k . h
D'où la divisibilité par p pour tout a premier avec p.	a ^p–1 – 1 divisible par p

PUISSANCE jusqu'à 7 modulo 7

Tableau avec p = 7

Testons une dernière fois avec le nombre premier suivant

p = 7	a = 1	a = 2	a = 3	a = 4	a = 5	a = 6
n = 1	1^1 – 1	2^1 – 2	3^1 – 3	4^1 – 4	5^1 – 5	6^1 – 6
n = 2	1^2 – 1	2^2 – 4	3^2 – 2	4^2 – 2	5^2 – 4	6^2 – 1
n = 3	1^3 – 1	2^3 – 1	3^3 – 6	4^3 – 1	5^3 – 6	6^3 – 6
n = 4	1^4 – 1	2^4 – 2	3^4 – 4	4^4 – 4	5^4 – 2	6^4 – 1
n = 5	1^5 – 1	2^5 – 4	3^5 – 5	4^5 – 2	5^5 – 3	6^5 – 6
n = 6	1^6 – 1	2^6 – 1	3^6 – 1	4^6 – 1	5^6 – 1	6^6 – 1
n = 7	1^7 – 1	2^7 – 2	3^7 – 3	4^7 – 4	5^7 – 5	6^7 – 6

On retrouve bien nos propriétés sur les deux dernières lignes, routine, maintenant !

Symboles

p = 7	a = 1	a = 2	a = 3	a = 4	a = 5	a = 6
n = 1	a^1 – 1
n = 2						a^2 – 1
n = 3		a^3 – 1		a^3 – 1
n = 4
n = 5
n = 6 = p –1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1	a^p–1 – 1
n = 7 = p	a^p – a	a^p – a	a^p – a	a^p – a	a^p – a	a^p – a

Remarque

Pour chaque ligne, on a noté (cas bleue) la première apparition d'un résidu égal à 1. Alors n = 1, 2, 3 ou 6, tous les diviseurs de p – 1 = 6.

Ces exposants (1, 2, 3 et 6) sont les gaussiens de Z7

Le pourquoi de ce nom de baptême Z7, sera vu ultérieurement.

Notation simplifiée

Une fois bien familier à cette manière de présenter, on peut encore simplifier l'écriture:

On élimine la ligne 1 (puissance 1), et on ne note plus que les résidus.

p = 7	1	2	3	4	5	6
Puissance 2	1	4	2	2	4	1
Puissance 3	1	1	6	1	6	6
Puissance 4	1	2	4	4	2	1
Puissance 5	1	4	5	2	3	6
Puissance 6	1	1	1	1	1	1
Puissance 7	1	2	3	4	5	6

Ces deux dernières lignes témoignent du petit théorème de Fermat.

FORMULATION CLASSIQUE

Formulations classiques (à retenir) du petit théorème de Fermat

Si p est un nombre premier, alors divisé par p, un nombre et sa puissance p donne le même reste.	a^p a mod p	4^3 = 64 = 3 x 21 + 1 4 = 3 x 1 + 1
Si en plus, a et p sont étrangers, la puissance p – 1 de ce nombre divisée par p donne 1 pour reste.	a^p–1 1 mod p avec (a,p) = 1	4^2 = 16 = 3 x 5 + 1

(a,p) = PGCD et (a,p) = 1 indiquent que a et b sont étrangers (premiers entre eux)

Autres formulations

a^p a mod p a^p est congru à a modulo p. a^p – a 0 mod p a^p – a est congru à 0 modulo p.	a^p – a divisé par p donne 0 comme reste. a^p – a est un multiple de p. a^p / p donne un multiple de a comme reste.
a^p – 1 – 1 0 mod p si (a,b) = 1 a^p – 1 1 mod p si (a,b) = 1	a^p – 1 est congru à 1 mod p si a et b sont étrangers.

Quelques exemples pour bien se remettre en tête cette extraordinaire propriété:

2² – 1 = 0 mod 3

3² – 1 0 mod 3

4² – 1 = 0 mod 3

5² – 1 = 0 mod 3

6² – 1 0 mod 3

Tous les carrés sont de la forme 3k + 1 sauf pour les nombres divisibles par 3.

Exemples de calculs
Calculer le reste de la division par 37 de 2^52. On extrait d'abord 37 de 52; reste 16. Le nombre 37 est premier et le petit théorème de Fermat (PTF) s'applique: 2^37 – 1 = 2^36 divisé par 37 donne 1 pour reste. Pour le second terme (2^16), son reste est obtenu par simple calcul ordinaire. Calculer le reste de la division par 37 de 2^70.

Voir Calculs du même style / Algorithme de calcul modulaire

HISTORIQUE
En 1640, Fermat adresse une lettre à son ami Bernard Frenicle de Bessy et lui indique qu'il détient la preuve de ce théorème. La démonstration est un peu longue et il promet de la lui envoyer plus tard. Ce qu'il ne fit pas. En 1736, c'est Euler qui fournira la démonstration. Il se permet de généraliser le petit théorème au nombre N produit de deux nombres premiers.

ENGLISH CORNER
Fermat's Little Theorem: Let p be a prime and a any integer, then a^p = a (mod p). Let p be a prime which does not divide the integer a, then a^p – 1= 1 (mod p).

Suite	Le petit théorème de Fermat Cas où a = 2 Découverte Exploration Démonstration classique Démonstration avec le triangle de Pascal Application à la factorisation Les puissances de 7 modulo 11 Sa programmation en Python
Voir	Divisibilité des puissances Nombre pseudo-premier Test de primalité Divisibilité par 11 Divisibilité par 42
Avancé	Voir un sujet complet utilisant ces notions: Nombres de Carmichaël  On y verra en particulier le cas de la puissance 15
Découvrir	Pierre de Fermat Modulo & Congruences Primalité Nombres Premiers Pseudo Premiers Absolus Théorème de Fermat-Wiles
Cette page	http://villemin.gerard.free.fr/ThNbDemo/PtThFerm.htm