insight.Se connecter

Maths expertes · Terminale

Nombres premiers et petit théorème de Fermat : cours et fiche de révision (Maths expertes, Terminale)

Programme officiel, session 2027. Mis à jour le 7 novembre 2026. 8 min de lecture.

Ce que contient ce chapitre

  • Reconnaître un nombre premier
  • Raisonner avec les nombres premiers
  • Décomposer un entier et trouver ses diviseurs
  • Calculer des restes avec le petit théorème de Fermat
  • Trouver un témoin de non-primalité
  • Chiffrer et déchiffrer avec une clé affine
  • Comprendre le chiffrement RSA

Les nombres premiers sont les briques des entiers : tout entier au moins égal à 22 est, de façon unique, un produit de nombres premiers. Avec le petit théorème de Fermat, ils fondent le chiffrement RSA, qui protège tes échanges sur internet. À la fin du chapitre, tu sauras reconnaître un nombre premier, décomposer un entier, calculer le reste d'une énorme puissance et chiffrer un message.

Reconnaître un nombre premier

Un entier naturel pp est premier s'il a exactement deux diviseurs positifs : 11 et pp. Donc 00 et 11 ne sont pas premiers, et 22 est le seul premier pair.

Propriété. Tout entier n≥2n \geq 2 a au moins un diviseur premier : son plus petit diviseur supérieur ou égal à 22.

Critère. Si n≥2n \geq 2 n'est divisible par aucun nombre premier pp tel que p2≤np^2 \leq n, alors nn est premier. En effet, si n=abn = ab avec 2≤a≤b2 \leq a \leq b, alors a2≤na^2 \leq n, et tout diviseur premier pp de aa divise nn avec p2≤np^2 \leq n.

Exemple résolu

211211 est-il premier ?

  • 142=196≤211<225=15214^2 = 196 \leq 211 < 225 = 15^2 : tu testes les premiers jusqu'à 1313.
  • Ni 22, ni 33 (2+1+1=42 + 1 + 1 = 4), ni 55 ne divisent 211211.
  • 211=7×30+1211 = 7 \times 30 + 1, 211=11×19+2211 = 11 \times 19 + 2 et 211=13×16+3211 = 13 \times 16 + 3 : aucun reste nul, donc 211211 est premier.

Le crible d'Ératosthène

Pour lister les premiers jusqu'à NN, écris les entiers de 22 à NN. Le premier nombre non barré est premier : garde-le et barre ses autres multiples, puis recommence avec le suivant non barré. Dès que ce nombre pp vérifie p2>Np^2 > N, arrête : tous les nombres non barrés sont premiers.

Exemple résolu

Jusqu'à 5050, tu barres les multiples de 22, 33, 55 et 77 ; le suivant, 1111, vérifie 112=121>5011^2 = 121 > 50. Il reste quinze premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Raisonner avec les nombres premiers

Lemme d'Euclide. Si un nombre premier pp divise un produit abab, alors pp divise aa ou pp divise bb. En effet, si pp ne divise pas aa, pp et aa sont premiers entre eux (leur PGCD divise pp et n'est pas pp), et le théorème de Gauss donne p∣bp \mid b.

Exemple résolu

Si 55 divise 3n3n, comme 55 est premier et ne divise pas 33, alors 55 divise nn.

L'ensemble des nombres premiers est infini

Démonstration par l'absurde.

  1. Suppose qu'il n'y ait qu'un nombre fini de nombres premiers, p1,p2,…,pkp_1, p_2, \dots, p_k, et pose N=p1p2⋯pk+1N = p_1 p_2 \cdots p_k + 1.
  2. Comme N≥2N \geq 2, NN a un diviseur premier pp, qui est l'un des pip_i.
  3. Alors pp divise NN et p1p2⋯pkp_1 p_2 \cdots p_k, donc leur différence, 11 : impossible, car p≥2p \geq 2.
  4. L'hypothèse est fausse : il existe une infinité de nombres premiers.

Montrer qu'un nombre n'est pas premier

Exemple résolu 1. Pour n≥3n \geq 3, n2−1=(n−1)(n+1)n^2 - 1 = (n - 1)(n + 1) est un produit de deux entiers au moins égaux à 22 : il n'est pas premier.

Exemple résolu 2 (nombres de Mersenne). 23≡1 [7]2^3 \equiv 1 \ [7], donc 215=(23)5≡1 [7]2^{15} = (2^3)^5 \equiv 1 \ [7] : 77 divise 215−1=327672^{15} - 1 = 32767, qui n'est pas premier. De même, 2a−12^a - 1 divise 2ab−12^{ab} - 1 : si nn n'est pas premier, 2n−12^n - 1 ne l'est pas non plus.

Décomposer en facteurs premiers

Théorème. Tout entier n≥2n \geq 2 s'écrit de façon unique n=p1α1p2α2⋯pkαkn = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, avec p1<p2<⋯<pkp_1 < p_2 < \dots < p_k premiers et α1,…,αk\alpha_1, \dots, \alpha_k entiers naturels non nuls.

L'existence s'obtient en divisant nn par son plus petit diviseur premier, puis le quotient par le sien, jusqu'à obtenir 11. L'unicité découle du lemme d'Euclide.

Exemple résolu

Tu divises 360360 par 22 tant que c'est possible, puis par 33, puis par 55 :

360=2×180=22×90=23×45=23×3×15=23×32×5.360 = 2 \times 180 = 2^2 \times 90 = 2^3 \times 45 = 2^3 \times 3 \times 15 = 2^3 \times 3^2 \times 5.

Les diviseurs d'un entier

Les diviseurs positifs de n=p1α1⋯pkαkn = p_1^{\alpha_1} \cdots p_k^{\alpha_k} sont les entiers p1β1⋯pkβkp_1^{\beta_1} \cdots p_k^{\beta_k} avec 0≤βi≤αi0 \leq \beta_i \leq \alpha_i pour chaque ii ; il y en a (α1+1)⋯(αk+1)(\alpha_1 + 1) \cdots (\alpha_k + 1).

Exemple résolu

360=23×32×5360 = 2^3 \times 3^2 \times 5 a (3+1)(2+1)(1+1)=24(3 + 1)(2 + 1)(1 + 1) = 24 diviseurs positifs. 12=22×312 = 2^2 \times 3 en est un ; 16=2416 = 2^4 n'en est pas un, car l'exposant 44 dépasse 33.

Le petit théorème de Fermat

Théorème. Si pp est premier et si aa est un entier non divisible par pp, alors ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].

Conséquence. Pour tout entier aa, ap≡a [p]a^p \equiv a \ [p] : si pp divise aa, les deux membres sont congrus à 00 ; sinon, multiplie le théorème par aa.

Exemple résolu 1. Reste de 31003^{100} dans la division par 77.

  • 77 est premier et ne divise pas 33, donc 36≡1 [7]3^6 \equiv 1 \ [7].
  • 100=6×16+4100 = 6 \times 16 + 4, donc 3100=(36)16×34≡34 [7]3^{100} = (3^6)^{16} \times 3^4 \equiv 3^4 \ [7].
  • 34=81=7×11+43^4 = 81 = 7 \times 11 + 4 : le reste est 44.

Exemple résolu 2. Pour tout entier nn, n7≡n [7]n^7 \equiv n \ [7], donc 77 divise n7−nn^7 - n.

Un test de non-primalité

Par contraposée, s'il existe un entier aa tel que 1≤a≤n−11 \leq a \leq n - 1 et an−1≢1 [n]a^{n-1} \not\equiv 1 \ [n], alors nn n'est pas premier : aa est un témoin. Pour n=15n = 15 et a=2a = 2 : 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], et 1515 n'est pas premier.

La réciproque du théorème est fausse : 210=1024=3×341+12^{10} = 1024 = 3 \times 341 + 1, donc 2340=(210)34≡1 [341]2^{340} = (2^{10})^{34} \equiv 1 \ [341], alors que 341=11×31341 = 11 \times 31. Les nombres de Carmichaël, comme 561=3×11×17561 = 3 \times 11 \times 17, trompent même le test pour tout aa premier avec eux.

Chiffrer et déchiffrer

Le chiffrement affine

Chaque lettre a un rang xx (A=0A = 0, B=1B = 1, …, Z=25Z = 25) et elle est codée par la lettre de rang yy, reste de ax+bax + b modulo 2626, où aa et bb sont des entiers fixés. Pour déchiffrer, il faut que aa soit premier avec 2626 : aa a alors un inverse a′a' modulo 2626, et x≡a′(y−b) [26]x \equiv a'(y - b) \ [26].

Exemple résolu

Avec a=3a = 3 et b=5b = 5 :

  • M a le rang 1212 et 3×12+5=41=26+153 \times 12 + 5 = 41 = 26 + 15 : M est codée par la lettre de rang 1515, P.
  • 3×9=27≡1 [26]3 \times 9 = 27 \equiv 1 \ [26] : 99 est un inverse de 33, et x≡9(y−5) [26]x \equiv 9(y - 5) \ [26].
  • Pour P : 9×(15−5)=90=3×26+129 \times (15 - 5) = 90 = 3 \times 26 + 12, tu retrouves M.

Avec a=2a = 2, A et N sont codées par la même lettre, car 2×13=26≡0 [26]2 \times 13 = 26 \equiv 0 \ [26] : le déchiffrement est impossible.

Le principe du chiffrement RSA

  1. Choisis deux nombres premiers distincts pp et qq, et pose n=pqn = pq.
  2. Choisis ee premier avec (p−1)(q−1)(p-1)(q-1) et dd un inverse de ee modulo (p−1)(q−1)(p-1)(q-1).
  3. Un message mm, entier tel que 0≤m<n0 \leq m < n, est chiffré par cc, reste de mem^e modulo nn.
  4. Le reste de cdc^d modulo nn redonne mm : le petit théorème de Fermat, appliqué modulo pp puis modulo qq, prouve que med≡m [n]m^{ed} \equiv m \ [n].

Le couple (n;e)(n ; e) est public et dd secret : on ne sait pas factoriser rapidement un nn de plusieurs centaines de chiffres.

Exemple résolu

p=5p = 5 et q=11q = 11, donc n=55n = 55 et (p−1)(q−1)=40(p-1)(q-1) = 40.

  • Avec e=3e = 3 : 3×27=81=2×40+13 \times 27 = 81 = 2 \times 40 + 1, donc d=27d = 27.
  • Le message m=2m = 2 est chiffré par c=23=8c = 2^3 = 8.
  • c27=281c^{27} = 2^{81} ; or 24≡1 [5]2^4 \equiv 1 \ [5] donne 281=(24)20×2≡2 [5]2^{81} = (2^4)^{20} \times 2 \equiv 2 \ [5], et 210≡1 [11]2^{10} \equiv 1 \ [11] donne 281=(210)8×2≡2 [11]2^{81} = (2^{10})^8 \times 2 \equiv 2 \ [11].
  • 55 et 1111, premiers entre eux, divisent 281−22^{81} - 2, donc 5555 aussi : tu retrouves m=2m = 2.

Les pièges

  • S'arrêter trop tôt : pour 169169, teste jusqu'à 1313 inclus, car 169=132169 = 13^2.
  • Le lemme d'Euclide sans pp premier : 66 divise 4×3=124 \times 3 = 12, mais ni 44 ni 33.
  • Croire que p1⋯pk+1p_1 \cdots p_k + 1 est premier : 2×3×5×7×11×13+1=30031=59×5092 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509.
  • Fermat sans ses hypothèses : il faut pp premier et pp ne divisant pas aa ; par exemple 76≡0 [7]7^6 \equiv 0 \ [7].
  • Mauvais diviseur de l'exposant : pour 31003^{100} modulo 77, divise 100100 par p−1=6p - 1 = 6, pas par 77.
  • Diviser dans une congruence : pour déchiffrer, multiplie par l'inverse a′a' ; écrire x=(y−b)/ax = (y - b)/a n'a pas de sens modulo 2626.

Ce qu'il faut retenir

  • Si n≥2n \geq 2 n'a aucun diviseur premier pp tel que p2≤np^2 \leq n, alors nn est premier.
  • Il existe une infinité de nombres premiers.
  • Si un premier pp divise abab, alors pp divise aa ou bb.
  • Tout n≥2n \geq 2 a une unique décomposition p1α1⋯pkαkp_1^{\alpha_1} \cdots p_k^{\alpha_k} en facteurs premiers, et (α1+1)⋯(αk+1)(\alpha_1 + 1) \cdots (\alpha_k + 1) diviseurs positifs.
  • Si pp est premier et ne divise pas aa, ap−1≡1 [p]a^{p-1} \equiv 1 \ [p] ; pour tout aa, ap≡a [p]a^p \equiv a \ [p].
  • Chiffrement affine : déchiffrable si et seulement si aa est premier avec 2626, et x≡a′(y−b) [26]x \equiv a'(y - b) \ [26].
  • RSA : n=pqn = pq, ed≡1 [(p−1)(q−1)]ed \equiv 1 \ [(p-1)(q-1)], c≡me [n]c \equiv m^e \ [n], m≡cd [n]m \equiv c^d \ [n].

À l'épreuve

Les maths expertes sont évaluées en contrôle continu. En devoir surveillé, ce chapitre donne des questions enchaînées : décomposer un entier puis dénombrer ses diviseurs, trouver un inverse modulo 2626 puis déchiffrer, démontrer que 77 divise n7−nn^7 - n. La démonstration de l'infinité des nombres premiers peut être demandée telle quelle.

Ton professeur attend les hypothèses citées avant chaque théorème (« 77 est premier et ne divise pas 33 ») et chaque division posée. Tu perds des points si tu calcules une puissance en entier au lieu de la réduire, ou si tu déclares un nombre premier sans les divisions testées.

À retenir

  • Reconnaître un nombre premier

    Un nombre premier a exactement deux diviseurs positifs : 11 et lui-même ; 00 et 11 ne sont pas premiers, 22 est le seul premier pair.Tout entier n≥2n \geq 2 a un diviseur premier : son plus petit diviseur supérieur ou égal à 22.Si aucun nombre premier pp tel que p2≤np^2 \leq n ne divise nn, alors nn est premier.Crible d'Ératosthène jusqu'à NN : garde le premier nombre non barré, barre ses autres multiples, recommence, et arrête-toi dès que p2>Np^2 > N.
  • Raisonner avec les nombres premiers

    Lemme d'Euclide : si un nombre premier pp divise abab, alors pp divise aa ou bb ; c'est faux si pp n'est pas premier.Si pp est premier et ne divise pas aa, alors pp et aa sont premiers entre eux.Infinité des premiers, par l'absurde : N=p1p2⋯pk+1N = p_1 p_2 \cdots p_k + 1 aurait un diviseur premier qui diviserait aussi 11.Pour prouver qu'un nombre n'est pas premier, écris-le comme produit de deux entiers au moins égaux à 22 : n2−1=(n−1)(n+1)n^2 - 1 = (n - 1)(n + 1) pour n≥3n \geq 3.
  • Décomposer un entier et trouver ses diviseurs

    Tout entier n≥2n \geq 2 s'écrit de façon unique p1α1⋯pkαkp_1^{\alpha_1} \cdots p_k^{\alpha_k}, avec p1<⋯<pkp_1 < \dots < p_k premiers.Méthode : divise par 22 tant que c'est possible, puis par 33, par 55… jusqu'à obtenir 11.Les diviseurs positifs sont les p1β1⋯pkβkp_1^{\beta_1} \cdots p_k^{\beta_k} avec 0≤βi≤αi0 \leq \beta_i \leq \alpha_i.Il y en a (α1+1)⋯(αk+1)(\alpha_1 + 1) \cdots (\alpha_k + 1) : 360=23×32×5360 = 2^3 \times 3^2 \times 5 en a 2424.
  • Calculer des restes avec le petit théorème de Fermat

    Si pp est premier et ne divise pas aa, alors ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].Pour tout entier aa, ap≡a [p]a^p \equiv a \ [p] : par exemple, 77 divise n7−nn^7 - n.Reste de aNa^N modulo pp : écris N=(p−1)k+rN = (p-1)k + r, alors aN≡ar [p]a^N \equiv a^r \ [p].Cite toujours les deux hypothèses : pp premier et pp ne divise pas aa.
  • Trouver un témoin de non-primalité

    Si 1≤a≤n−11 \leq a \leq n - 1 et si an−1a^{n-1} n'est pas congru à 11 modulo nn, alors nn n'est pas premier : aa est un témoin.Exemple : 214≡4 [15]2^{14} \equiv 4 \ [15], donc 1515 n'est pas premier.La réciproque est fausse : 2340≡1 [341]2^{340} \equiv 1 \ [341] alors que 341=11×31341 = 11 \times 31.Les nombres de Carmichaël, comme 561=3×11×17561 = 3 \times 11 \times 17, passent le test pour tout aa premier avec eux sans être premiers.
  • Chiffrer et déchiffrer avec une clé affine

    Rangs : A=0A = 0, …, Z=25Z = 25 ; la lettre de rang xx est codée par celle de rang yy, reste de ax+bax + b modulo 2626.Le déchiffrement est possible si et seulement si aa est premier avec 2626.On déchiffre par x≡a′(y−b) [26]x \equiv a'(y - b) \ [26], où a′a' est un inverse de aa modulo 2626.Exemple : 3×9=27≡1 [26]3 \times 9 = 27 \equiv 1 \ [26], donc 99 est un inverse de 33 modulo 2626.
  • Comprendre le chiffrement RSA

    n=pqn = pq avec pp et qq premiers distincts ; ee premier avec (p−1)(q−1)(p-1)(q-1).Clé secrète dd : un inverse de ee modulo (p−1)(q−1)(p-1)(q-1).Chiffrement : cc est le reste de mem^e modulo nn ; déchiffrement : le reste de cdc^d modulo nn redonne mm.Le petit théorème de Fermat, appliqué modulo pp puis modulo qq, prouve que med≡m [n]m^{ed} \equiv m \ [n].

Teste-toi

Trois questions. Réponds, la correction s’affiche.

Question 1 sur 3
Lequel de ces entiers est premier ?

Correction

92=81≤97<100=1029^2 = 81 \leq 97 < 100 = 10^2 : il suffit de tester 22, 33, 55 et 77.97=2×48+197 = 2 \times 48 + 1, 97=3×32+197 = 3 \times 32 + 1, 97=5×19+297 = 5 \times 19 + 2, 97=7×13+697 = 7 \times 13 + 6 : aucun reste nul, donc 9797 est premier.Erreur classique : s'arrêter à 55 et croire 9191 premier — 91=7×1391 = 7 \times 13, il faut tester jusqu'à 77.
Question 2 sur 3
Quel est le reste de la division de 5505^{50} par 1111 ?

Correction

1111 est premier et ne divise pas 55, donc 510≡1 [11]5^{10} \equiv 1 \ [11].50=10×550 = 10 \times 5, donc 550=(510)5≡1 [11]5^{50} = (5^{10})^5 \equiv 1 \ [11].Le reste est 11.Erreur classique : diviser l'exposant par 1111 — l'exposant se réduit modulo p−1=10p - 1 = 10, pas modulo pp.
Question 3 sur 3
Dans un chiffrement RSA, on a choisi p=5p = 5 et q=11q = 11. Parmi ces entiers, lequel peut servir d'exposant de chiffrement ee ?

Correction

(p−1)(q−1)=4×10=40(p-1)(q-1) = 4 \times 10 = 40.ee doit être premier avec 4040 : PGCD(3,40)=1\text{PGCD}(3, 40) = 1.PGCD(4,40)=4\text{PGCD}(4, 40) = 4, PGCD(10,40)=10\text{PGCD}(10, 40) = 10 et PGCD(5,40)=5\text{PGCD}(5, 40) = 5 : ces trois valeurs sont refusées.Erreur classique : tester ee avec n=55n = 55 au lieu de 4040 — 44 est premier avec 5555 mais pas avec 4040, donc il n'a pas d'inverse modulo 4040.

Dans Insight, ce chapitre a 119 questions, et l’app te les repose au bon moment pour que tu ne les oublies pas avant le bac.

Contenu préparé avec l’aide d’outils d’IA, vérifié.

Réviser ce chapitre gratuitement