Nombres premiers et petit théorème de Fermat

Arithmétique — Terminale Maths Expertes

Nombres premiers et petit théorème de Fermat

1. Propriétés des nombres premiers

Caractérisation : Un entier p ≥ 2 est premier si et seulement si pour tout entier a, on a : p | a ou PGCD(p, a) = 1

Lemme d'Euclide : Si un nombre premier p divise un produit ab, alors p | a ou p | b (ou les deux).

Plus généralement, si p est premier et p | a₁a₂ … aₙ, alors p divise au moins un des aᵢ.

Exemple : Si 7 | (n × 15) et 7 ∤ 15, alors par le lemme d'Euclide, 7 | n.

Théorème fondamental de l'arithmétique (unicité) : La décomposition en facteurs premiers d'un entier n ≥ 2 est unique à l'ordre près des facteurs.


2. Infinité des nombres premiers

Théorème d'Euclide : Il existe une infinité de nombres premiers.

Démonstration (par l'absurde) : Supposons qu'il n'y ait qu'un nombre fini de nombres premiers : p₁, p₂, …, pₖ.

Considérons N = p₁p₂ … pₖ + 1.

  • N > 1, donc N admet au moins un diviseur premier p.
  • p est l'un des pᵢ, donc p | p₁p₂ … pₖ.
  • Comme p | N et p | p₁p₂ … pₖ, on a p | (N - p₁p₂ … pₖ) = 1.

Contradiction ! Donc il y a une infinité de nombres premiers.


3. Test de primalité

Test de primalité naïf : Pour tester si un entier n ≥ 2 est premier, il suffit de vérifier qu'aucun entier d avec 2 ≤ d ≤ √(n) ne divise n.

En effet, si n = ab avec a, b > 1, alors au moins un des deux est ≤ √(n).

Exemple : Tester si 97 est premier.

On teste les diviseurs d avec 2 ≤ d ≤ √(97) ≈ 9,85, donc d ∈ {2, 3, 5, 7}.

  • 97 mod 2 = 1 (non divisible par 2)
  • 97 mod 3 = 1 (non divisible par 3)
  • 97 mod 5 = 2 (non divisible par 5)
  • 97 mod 7 = 6 (non divisible par 7)

Donc 97 est premier.

Crible d'Ératosthène : Pour trouver tous les nombres premiers ≤ n :

  1. Écrire tous les entiers de 2 à n
  2. Prendre le premier nombre non barré (p = 2)
  3. Barrer tous les multiples de p strictement supérieurs à p
  4. Répéter avec le prochain nombre non barré
  5. S'arrêter quand p² > n
  6. Les nombres non barrés sont premiers

4. Congruences modulo un nombre premier

Propriétés modulo p : Soit p un nombre premier et a, b ∈ ℤ.

  1. Si p ∤ a, alors PGCD(a, p) = 1
  2. Si ab ≡ 0 (mod p), alors a ≡ 0 (mod p) ou b ≡ 0 (mod p)
  3. Si ac ≡ bc (mod p) et p ∤ c, alors a ≡ b (mod p) (simplification)

Exemple : Résoudre 3x ≡ 6 (mod 7).

Comme PGCD(3, 7) = 1, on peut simplifier : x ≡ 2 (mod 7).

Les solutions sont x = 7k + 2 pour k ∈ ℤ.


5. Petit théorème de Fermat

Petit théorème de Fermat : Soit p un nombre premier et a un entier.

  • Si p ∤ a, alors : aᵖ⁻¹ ≡ 1 (mod p)

  • Pour tout a ∈ ℤ : aᵖ ≡ a (mod p)

Exemples :

  • 2⁶ = 64 ≡ 1 (mod 7) (car 7 est premier et 7 ∤ 2)
  • 3¹⁰ = 59049 ≡ 1 (mod 11) (car 11 est premier et 11 ∤ 3)
  • 5⁷ = 78125 ≡ 5 (mod 7) (deuxième forme)

Idée de la démonstration : On considère les nombres a, 2a, 3a, …, (p-1)a modulo p.

On montre qu'ils sont tous distincts et non nuls modulo p, donc ils forment une permutation de {1, 2, …, p-1}.

Ainsi : a × 2a × ⋯ × (p-1)a ≡ 1 × 2 × ⋯ × (p-1) (mod p)

D'où aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p).

Comme p ∤ (p-1)!, on peut simplifier : aᵖ⁻¹ ≡ 1 (mod p).


6. Applications du petit théorème de Fermat

6.1 Calcul de puissances modulo p

Calcul efficace : Pour calculer aⁿ mod p avec p premier et p ∤ a :

  1. Écrire n = q(p-1) + r avec 0 ≤ r < p-1 (division euclidienne)
  2. aⁿ = aq⁽ᵖ⁻¹⁾ ⁺ ʳ = (aᵖ⁻¹)q × aʳ ≡ 1q × aʳ = aʳ (mod p)
  3. Calculer aʳ mod p (plus petit exposant)

Exemple : Calculer 2¹⁰⁰ mod 7.

Comme 7 est premier et 7 ∤ 2, on a 2⁶ ≡ 1 (mod 7).

100 = 6 × 16 + 4, donc 2¹⁰⁰ = 2⁶ × ¹⁶ ⁺ ⁴ = (2⁶)¹⁶ × 2⁴ ≡ 1¹⁶ × 16 = 16 ≡ 2 (mod 7).

Ainsi 2¹⁰⁰ ≡ 2 (mod 7).

6.2 Test de primalité (test de Fermat)

Test de Fermat (contraposée) : Si pour un entier a avec 1 < a < n et PGCD(a, n) = 1, on a aⁿ⁻¹ ≡ 1 (mod n), alors n n'est pas premier.

Attention : la réciproque est fausse (nombres de Carmichael).

Exemple : Montrer que 15 n'est pas premier.

On teste avec a = 2 : 2¹⁴ = 16384 ≡ 4 (mod 15) (car 16384 = 15 × 1092 + 4).

Comme 2¹⁴ ≡ 1 (mod 15), le nombre 15 n'est pas premier.


7. Critères de divisibilité par les congruences

Les critères appris au collège ne sont pas des recettes : ils se démontrent, et tous par la même question — à quoi 10 est-il congru ?

Le principe : Un nombre s'écrit cₙ … c₁ c₀̅ = Σₖ cₖ 10 ᵏ.

Pour tester la divisibilité par d, il suffit donc de remplacer chaque 10 ᵏ par sa congruence modulo d.

Divisibilité par 9 (et par 3) : 10 ≡ 1 (mod 9), donc 10 ᵏ ≡ 1 pour tout k.

Un nombre est donc congru à la somme de ses chiffres modulo 9 — et modulo 3, puisque 3 divise 9.

123456 : somme des chiffres = 21, et 21 ≡ 3 9. Le nombre est donc divisible par 3 mais pas par 9, et son reste modulo 9 vaut 3.

Divisibilité par 11 : Cette fois 10 ≡ -1 (mod 11), donc 10 ᵏ ≡ (-1)ᵏ : les rangs pairs comptent positivement, les rangs impairs négativement.

Un nombre est donc congru à la somme alternée de ses chiffres, en partant des unités.

81 753 : 3 - 5 + 7 - 1 + 8 = 12 ≡ 1 (mod 11). Le nombre n'est pas divisible par 11, et il laisse le reste 1 — en effet 81 753 = 11 × 7 432 + 1.

Le rang se compte depuis les unités : Sur un nombre à nombre PAIR de chiffres, lire depuis la gauche donne la somme opposée. La divisibilité reste correcte, mais le reste calculé est faux.

Divisibilité par 2, 5 et 10 : Ici 10 ≡ 0, donc 10 ᵏ ≡ 0 dès que k ≥ 1 : tous les chiffres disparaissent sauf celui des unités.

C'est pourquoi seul le dernier chiffre compte pour ces trois diviseurs.

Trois critères, une seule idée : Par 9 on additionne car 10 ≡ 1 · par 11 on alterne car 10 ≡ -1 · par 2 ou 5 seul le dernier chiffre compte car 10 ≡ 0.

Et il n'existe pas de critère simple pour 7 ou 13, précisément parce que 10 n'y est congru à aucune valeur remarquable.


8. Application : les clés de contrôle

Les congruences servent tous les jours à détecter les erreurs de saisie. Le principe est le même partout : on ajoute au nombre un chiffre choisi pour que l'ensemble soit divisible par un entier fixé.

Clé de contrôle d'un ISBN à 10 chiffres : Un ISBN c₁ c₂ … c₁₀ est valide lorsque

10 c₁ + 9 c₂ + 8 c₃ + ⋯ + 2 c₉ + c₁₀ ≡ 0 (mod 11)

Le dernier chiffre c₁₀ est la clé : il est choisi pour que la somme tombe juste.

Exemple : Pour les neuf premiers chiffres 2 0 1 5 3 0 9 0 2, la somme pondérée vaut

10(2) + 9(0) + 8(1) + 7(5) + 6(3) + 5(0) + 4(9) + 3(0) + 2(2) = 121

Or 121 = 11 × 11, donc la clé qui convient est c₁₀ = 0 : l'ISBN complet est 2-01-530902-0.

Pourquoi le symbole X existe sur les ISBN : La clé doit valoir un entier entre 0 et 10 — car on travaille modulo 11. Quand elle vaut 10, un seul chiffre ne suffit plus : on écrit alors X.

C'est la trace visible du choix du module 11, qui est premier — et c'est justement sa primalité qui garantit qu'une clé existe toujours, et une seule.

Ce que la clé détecte, et ce qu'elle ne détecte pas : Modulo 11 avec des poids tous différents, une clé ISBN détecte toute erreur sur un seul chiffre, et toute inversion de deux chiffres voisins.

En revanche elle ne peut pas détecter deux erreurs qui se compensent — aucune clé à un seul caractère ne le pourrait.


9. Applications avancées

9.1 Cryptographie RSA (idée)

Le système RSA utilise le fait qu'il est difficile de factoriser de grands nombres. Il repose sur trois faits :

  • factoriser un très grand nombre est hors de portée, alors que le multiplier ne coûte rien : c'est ce qui fait la sécurité
  • chiffrer et déchiffrer reviennent à calculer des puissances modulo n, ce qui est rapide grâce à l'exponentiation rapide (élévations au carré successives)
  • le petit théorème de Fermat (plus précisément sa généralisation, le théorème d'Euler) garantit que le déchiffrement redonne bien le message

9.2 Nombres de Mersenne et de Fermat

Nombres de Mersenne : Un nombre de Mersenne est de la forme Mₙ = 2ⁿ - 1 avec n ∈ ℕ^*.

Si Mₙ est premier, alors n est premier (mais la réciproque est fausse).

Nombres de Fermat : Un nombre de Fermat est de la forme Fₙ = 2²^ⁿ + 1 avec n ∈ ℕ.

Les seuls nombres de Fermat premiers connus sont F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65537.


10. Résolution d'équations modulo p

Résolution de ax ≡ b (mod p) : Pour résoudre ax ≡ b (mod p) avec p premier et p ∤ a :

  1. Comme PGCD(a, p) = 1, a admet un inverse modulo p
  2. Par le petit théorème de Fermat : aᵖ⁻¹ ≡ 1 (mod p), donc a⁻¹ ≡ aᵖ⁻² (mod p)
  3. La solution unique est x ≡ baᵖ⁻² (mod p)

Exemple : Résoudre 5x ≡ 3 (mod 7).

L'inverse de 5 modulo 7 est 5⁷⁻² = 5⁵ = 3125 ≡ 3 (mod 7) (car 5³ = 125 ≡ 6 (mod 7), donc 5⁵ = 5³ × 5² ≡ 6 × 4 = 24 ≡ 3 (mod 7)).

Donc x ≡ 3 × 3 = 9 ≡ 2 (mod 7).

Vérification : 5 × 2 = 10 ≡ 3 (mod 7) ✓


À retenir

Résumé :

  1. Nombres premiers : infinité (théorème d'Euclide), test jusqu'à √(n)

  2. Lemme d'Euclide : si p premier et p | ab, alors p | a ou p | b

  3. Petit théorème de Fermat : si p premier et p ∤ a, alors aᵖ⁻¹ ≡ 1 (mod p)

  4. Critères de divisibilité : ils découlent tous de la congruence de 10 — somme des chiffres pour 9, somme alternée pour 11, dernier chiffre pour 2 et 5

  5. Clés de contrôle : un chiffre ajouté pour que le total soit divisible par un entier fixé, ce qui détecte les erreurs de saisie

  6. Applications : calcul de puissances modulo p, résolution d'équations, cryptographie