BURHAN.

Petit théorème de Fermat : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

Petit théorème de Fermat : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

Notions du cours (11)

Apprendre avec Burhan

Petit théorème de Fermat

Étape 1 sur 4

Observer des restes

Calculer le reste de 520265^{2026} dans la division par 1111, sans calculatrice ni patience infinie : voilà ce que permet le petit théorème de Fermat. Il sert dans 11 des 13 exercices d'arithmétique consultés. Tout part d'une observation sur des restes.

Devine : Les multiples de 3 modulo 11

On écrit les dix entiers 3,6,9,…,303, 6, 9, \dots, 30, puis leurs restes dans la division par 1111. Combien de restes différents obtient-on ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :1010

Juste.

Les restes sont 3,6,9,1,4,7,10,2,5,83, 6, 9, 1, 4, 7, 10, 2, 5, 8 : chaque entier de 11 à 1010 apparaît une fois.

Choix B :1111

Faux.

Il n'y a que dix entiers, donc au plus dix restes. Et le reste 00 n'apparaît pas : aucun de ces entiers n'est multiple de 1111.

Choix C :99

Faux.

Tu as supposé que deux restes se répètent, ou que le reste 00 apparaît. Calcule-les : aucun n'est nul, et ils sont tous distincts.

Besoin d'aide ? Indice 1

Calcule 3k3k pour k=1,…,10k = 1, \dots, 10, puis retire 1111 autant de fois que possible.

Encore bloqué ? Indice 2

Par exemple, 12=11+112 = 11 + 1 donne le reste 11.

Voir la correction complète
kk 11 22 33 44 55 66 77 88 99 1010
3k3k 33 66 99 1212 1515 1818 2121 2424 2727 3030
reste 33 66 99 11 44 77 1010 22 55 88

Les dix restes sont 1,2,…,101, 2, \dots, 10, chacun une fois, dans le désordre.

Ce que tu viens d'observer pour 33 et 1111 vaut-il pour tout premier pp et tout entier aa que pp ne divise pas ? L'énoncé suivant l'affirme. Pourquoi est-ce vrai ? La preuve, sous l'énoncé, répond à deux questions. Un multiple kaka peut-il être divisible par pp ? Deux multiples distincts peuvent-ils avoir le même reste ?

Continuer : Le lemme des multiples →

Étape 2 sur 4

Le lemme des multiples

PropriétéMultiples d'un entier modulo p

Soient pp un nombre premier et aa un entier relatif tel que p∤ap \nmid a. Les restes, dans la division euclidienne par pp, des p−1p - 1 entiers a, 2a, 3a, …, (p−1)aa, \ 2a, \ 3a, \ \dots, \ (p - 1)a sont les entiers 1,2,…,p−11, 2, \dots, p - 1, chacun exactement une fois.

Démonstration

Étape 1 (aucun reste nul). Soit kk un entier tel que 1≤k≤p−11 \leq k \leq p - 1. Alors p∤kp \nmid k (« Propriétés de la divisibilité », point 3) et p∤ap \nmid a, donc p∤kap \nmid ka (« Conséquences du théorème de Gauss », point 2) : le reste de kaka n'est pas nul (« Congruence et reste »).

Étape 2 (restes distincts). Supposons que kaka et lala aient le même reste, avec 1≤l<k≤p−11 \leq l < k \leq p - 1. Alors ka≡la [p]ka \equiv la \ [p] (« Congruence et reste »), donc p∣(k−l)ap \mid (k - l)a. Comme a∧p=1a \wedge p = 1 (« Conséquences du théorème de Gauss », point 1), le théorème de Gauss donne p∣k−lp \mid k - l. Or 0<k−l<p0 < k - l < p : c'est impossible (« Propriétés de la divisibilité », point 3).

Étape 3. Les p−1p - 1 restes sont deux à deux distincts et appartiennent à {1,2,…,p−1}\{1, 2, \dots, p - 1\}, qui a p−1p - 1 éléments. Ils sont donc exactement 1,2,…,p−11, 2, \dots, p - 1.

À retenirCe qu'il faut retenir de la preuve

Pour montrer que p−1p - 1 restes sont exactement 1,2,…,p−11, 2, \dots, p - 1, on ne les calcule pas. On montre qu'ils sont non nuls et deux à deux distincts, puis on compte : p−1p - 1 valeurs distinctes dans un ensemble à p−1p - 1 éléments les prennent toutes.

Vérifie : L'argument de l'étape 2

Dans la preuve, on arrive à p∣(k−l)ap \mid (k - l)a. Quel argument permet d'en déduire p∣k−lp \mid k - l ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Le petit théorème de Fermat.

Faux.

Fermat se démontre à partir de ce lemme : l'utiliser ici serait un raisonnement circulaire.

Choix B :Le théorème de Gauss, car a∧p=1a \wedge p = 1.

Juste.

pp divise le produit (k−l)a(k - l)a et pp est premier avec aa (conséquences du théorème de Gauss, point 1, car p∤ap \nmid a) : Gauss donne p∣k−lp \mid k - l.

Choix C :L'encadrement 0<k−l<p0 < k - l < p.

Faux.

Cet encadrement sert juste après, pour obtenir une contradiction. Il ne transforme pas p∣(k−l)ap \mid (k - l)a en p∣k−lp \mid k - l.

Besoin d'aide ? Indice 1

On cherche à « enlever » le facteur aa d'une divisibilité.

Encore bloqué ? Indice 2

Quel théorème fait passer de p∣bcp \mid bc à p∣cp \mid c, et sous quelle hypothèse ?

Voir la correction complète

On a p∣(k−l)ap \mid (k - l)a. Comme pp est premier et p∤ap \nmid a, on a a∧p=1a \wedge p = 1 (conséquences du théorème de Gauss, point 1). Le théorème de Gauss donne alors p∣k−lp \mid k - l. L'encadrement 0<k−l<p0 < k - l < p rend cette divisibilité impossible : deux restes ne sont jamais égaux.

ExempleContre-exemple : un facteur commun

Prends le module 99 et a=6a = 6, qui ont le facteur 33 en commun. Les restes de 6,12,18,…,486, 12, 18, \dots, 48 modulo 99 sont :

6, 3, 0, 6, 3, 0, 6, 3.6, \ 3, \ 0, \ 6, \ 3, \ 0, \ 6, \ 3.

Le reste 00 apparaît, et les restes se répètent. Avec un premier pp tel que p∤ap \nmid a, on a a∧p=1a \wedge p = 1 : c'est exactement ce qui manque ici.

← Étape précédenteContinuer : Le petit théorème de Fermat →

Étape 3 sur 4

Le petit théorème de Fermat

Reprends a=3a = 3 et p=11p = 11. Le produit des dix entiers 3,6,…,303, 6, \dots, 30 vaut 310×10!3^{10} \times 10!, où 10!=1×2×⋯×1010! = 1 \times 2 \times \cdots \times 10. Il est congru modulo 1111 au produit de leurs restes, qui sont 1,2,…,101, 2, \dots, 10 dans le désordre. Donc 310×10!≡10! [11]3^{10} \times 10! \equiv 10! \ [11]. Si l'on peut « simplifier » par 10!10!, on obtient 310≡1 [11]3^{10} \equiv 1 \ [11]. Vérifie : 35=243=22×11+13^5 = 243 = 22 \times 11 + 1, donc 310≡1 [11]3^{10} \equiv 1 \ [11]. Pourquoi est-ce vrai pour tout premier ? C'est le théorème suivant.

ThéorèmePetit théorème de Fermat

Soit pp un nombre premier.

  1. Pour tout entier relatif aa tel que p∤ap \nmid a : ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].
  2. Pour tout entier relatif aa : ap≡a [p]a^p \equiv a \ [p].

Démonstration

Étape 1. Soit aa tel que p∤ap \nmid a. On note (p−1)!=1×2×⋯×(p−1)(p-1)! = 1 \times 2 \times \cdots \times (p-1). Chaque kaka, pour 1≤k≤p−11 \leq k \leq p - 1, est congru à son reste (« Congruence et reste ») ; d'après « Multiples d'un entier modulo p », ces restes sont 1,2,…,p−11, 2, \dots, p - 1 dans un autre ordre. En multipliant ces p−1p - 1 congruences une à une (« Opérations sur les congruences », point 2, de proche en proche) : a×2a×⋯×(p−1)a≡(p−1)! [p],soitap−1 (p−1)!≡(p−1)! [p].a \times 2a \times \cdots \times (p-1)a \equiv (p-1)! \ [p], \quad \text{soit} \quad a^{p-1} \, (p-1)! \equiv (p-1)! \ [p].

Étape 2. Donc p∣(p−1)! (ap−1−1)p \mid (p-1)! \, (a^{p-1} - 1). Aucun des facteurs 1,…,p−11, \dots, p - 1 n'est divisible par pp (« Propriétés de la divisibilité », point 3), donc p∤(p−1)!p \nmid (p-1)! (« Conséquences du théorème de Gauss », point 4), puis (p−1)!∧p=1(p-1)! \wedge p = 1 (« Conséquences du théorème de Gauss », point 1). Le théorème de Gauss donne p∣ap−1−1p \mid a^{p-1} - 1 : c'est le point 1.

Étape 3 (point 2). Si p∤ap \nmid a, on multiplie le point 1 par aa (« Opérations sur les congruences »). Si p∣ap \mid a, alors a≡0 [p]a \equiv 0 \ [p], donc ap≡0≡a [p]a^p \equiv 0 \equiv a \ [p].

À retenirCe qu'il faut retenir de la preuve

On multiplie les p−1p - 1 congruences du lemme : ap−1×(p−1)!≡(p−1)! [p]a^{p-1} \times (p-1)! \equiv (p-1)! \ [p]. Puis on « simplifie » par (p−1)!(p-1)! : toute la question est de savoir pourquoi on en a le droit. Le point 2 s'en déduit en séparant les cas p∤ap \nmid a et p∣ap \mid a.

Vérifie : La simplification de l'étape 2

Dans la preuve, on obtient p∣(p−1)! (ap−1−1)p \mid (p-1)! \, (a^{p-1} - 1). Pourquoi a-t-on le droit d'en déduire p∣ap−1−1p \mid a^{p-1} - 1 ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Parce que (p−1)!≠0(p-1)! \neq 0.

Faux.

Un facteur non nul ne suffit pas : 6∣2×36 \mid 2 \times 3, et pourtant 6∤36 \nmid 3. Il faut un facteur premier avec le diviseur.

Choix B :Parce que (p−1)!≡1 [p](p-1)! \equiv 1 \ [p].

Faux.

C'est faux en général : pour p=5p = 5, 4!=24≡4 [5]4! = 24 \equiv 4 \ [5].

Choix C :Parce que (p−1)!∧p=1(p-1)! \wedge p = 1, puis par le théorème de Gauss.

Juste.

Aucun des facteurs 1,…,p−11, \dots, p - 1 n'est divisible par pp, donc p∤(p−1)!p \nmid (p-1)!, puis (p−1)!∧p=1(p-1)! \wedge p = 1 : Gauss s'applique.

Choix D :Par le petit théorème de Fermat.

Faux.

C'est ce qu'on est en train de démontrer : le raisonnement serait circulaire.

Besoin d'aide ? Indice 1

Simplifier une divisibilité par un facteur, c'est appliquer Gauss.

Encore bloqué ? Indice 2

Gauss exige que ce facteur soit premier avec pp.

Voir la correction complète

pp ne divise aucun des entiers 1,2,…,p−11, 2, \dots, p - 1. Comme pp est premier, il ne divise pas leur produit (conséquences du théorème de Gauss, point 4). Donc (p−1)!∧p=1(p-1)! \wedge p = 1 (même énoncé, point 1). Le théorème de Gauss donne p∣ap−1−1p \mid a^{p-1} - 1.

ExempleContre-exemple : un module composé

Le théorème exige un module premier. Avec 1515, composé, et a=2a = 2, premier avec 1515 : 24=16≡1 [15]2^4 = 16 \equiv 1 \ [15], donc

214=(24)3×22≡4 [15].2^{14} = (2^4)^3 \times 2^2 \equiv 4 \ [15].

On n'a donc pas 215−1≡1 [15]2^{15 - 1} \equiv 1 \ [15] : sans module premier, la conclusion peut être fausse.

← Étape précédenteContinuer : Réduire l'exposant →

Étape 4 sur 4

Réduire l'exposant

MéthodeFermat et réduction de l'exposant

Montrer que le reste de 520265^{2026} dans la division par 1111 est 55.

  1. Hypothèses. 1111 est premier et 11∤511 \nmid 5. D'après le petit théorème de Fermat, 510≡1 [11]5^{10} \equiv 1 \ [11].
  2. Diviser l'exposant par p−1=10p - 1 = 10. 2026=10×202+62026 = 10 \times 202 + 6, avec 0≤6<100 \leq 6 < 10.
  3. Réduire. 52026=(510)202×56≡1202×56 [11]5^{2026} = (5^{10})^{202} \times 5^6 \equiv 1^{202} \times 5^6 \ [11].
  4. Finir le calcul. 52=25≡3 [11]5^2 = 25 \equiv 3 \ [11], donc 56≡33=27≡5 [11]5^6 \equiv 3^3 = 27 \equiv 5 \ [11].
  5. Conclure. 52026≡5 [11]5^{2026} \equiv 5 \ [11] et 0≤5<110 \leq 5 < 11 : le reste est 55.

Rédaction attendue. « 1111 est premier et 11∤511 \nmid 5 : d'après le petit théorème de Fermat, 510≡1 [11]5^{10} \equiv 1 \ [11]. » Le module s'écrit à chaque ligne.

À toi : un reste par Fermat

Détermine le reste de 21002^{100} dans la division par 1313. Rédige en citant les hypothèses du petit théorème de Fermat.

Besoin d'aide ? Indice 1

Écris les hypothèses : 1313 est premier, et 1313 ne divise pas 22.

Encore bloqué ? Indice 2

Fermat donne 212≡1 [13]2^{12} \equiv 1 \ [13] : divise 100100 par 1212.

Encore bloqué ? Indice 3

Il reste à calculer 242^4 modulo 1313.

Voir la solution complète

1313 est premier et 13∤213 \nmid 2. D'après le petit théorème de Fermat, 212≡1 [13]2^{12} \equiv 1 \ [13].

Or 100=12×8+4100 = 12 \times 8 + 4, avec 0≤4<120 \leq 4 < 12. Donc 2100=(212)8×24≡18×16 [13]2^{100} = (2^{12})^8 \times 2^4 \equiv 1^8 \times 16 \ [13].

Comme 16=13×1+316 = 13 \times 1 + 3, on a 2100≡3 [13]2^{100} \equiv 3 \ [13], avec 0≤3<130 \leq 3 < 13 : le reste est 33.

AttentionFermat sans l'hypothèse p ∤ a

Avec p=5p = 5 et a=35a = 35 : 35≡0 [5]35 \equiv 0 \ [5], donc 354≡0 [5]35^4 \equiv 0 \ [5], et non 11. Avant d'écrire ap−1≡1 [p]a^{p-1} \equiv 1 \ [p], écris toujours « pp est premier et p∤ap \nmid a ». La forme ap≡a [p]a^p \equiv a \ [p], elle, vaut pour tout entier aa.

À toi : Coin examen

Montrer que 3030 divise a5−aa^5 - a pour tout entier aa. (2 points, barème indicatif BURHAN.)

Besoin d'aide ? Indice 1

30=2×3×530 = 2 \times 3 \times 5 : montre que 22, 33 et 55 divisent a5−aa^5 - a.

Encore bloqué ? Indice 2

Pour chaque premier pp, utilise la forme ap≡a [p]a^p \equiv a \ [p] du petit théorème de Fermat : elle vaut pour tout entier aa.

Encore bloqué ? Indice 3

Pour assembler, nomme la primalité relative : conséquences du théorème de Gauss, point 3.

Voir la solution complète

Rédaction attendue.

  • 55 est premier : d'après le petit théorème de Fermat (point 2), a5≡a [5]a^5 \equiv a \ [5]. 0,5 pt
  • 33 est premier : a3≡a [3]a^3 \equiv a \ [3], donc a5=a3×a2≡a×a2=a3≡a [3]a^5 = a^3 \times a^2 \equiv a \times a^2 = a^3 \equiv a \ [3]. 0,5 pt
  • 22 est premier : a2≡a [2]a^2 \equiv a \ [2], donc a5=(a2)2×a≡a2×a≡a×a≡a [2]a^5 = (a^2)^2 \times a \equiv a^2 \times a \equiv a \times a \equiv a \ [2]. 0,25 pt
  • 22 et 33 divisent a5−aa^5 - a et 2∧3=12 \wedge 3 = 1, donc 6∣a5−a6 \mid a^5 - a (conséquences du théorème de Gauss, point 3). De même, 6∧5=16 \wedge 5 = 1 donne 30∣a5−a30 \mid a^5 - a. 0,75 pt

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)