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 : [formule]

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_1a_2 a_n, alors p divise au moins un des a_i.

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_1, p_2, , p_k.

Considérons N = p_1p_2 p_k + 1.

  • N > 1, donc N admet au moins un diviseur premier p.
  • p est l'un des p_i, donc p p_1p_2 p_k.
  • Comme p N et p p_1p_2 p_k, on a p (N - p_1p_2 p_k) = 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 2 = 1 (non divisible par 2)
  • 97 3 = 1 (non divisible par 3)
  • 97 5 = 2 (non divisible par 5)
  • 97 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^2 > 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 Z.

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

Exemple : Résoudre 3x 6 7.

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

Les solutions sont x = 7k + 2 pour k Z.

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 : [formule]

  • Pour tout a Z : [formule]

Exemples :

  • 2^6 = 64 1 7 (car 7 est premier et 7 2)
  • 3^{10} = 59049 1 11 (car 11 est premier et 11 3)
  • 5^7 = 78125 5 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) p

D'où a^{p-1}(p-1)! (p-1)! p.

Comme p (p-1)!, on peut simplifier : a^{p-1} 1 p.

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

6.1 Calcul de puissances modulo p

Calcul efficace : Pour calculer a^n p avec p premier et p a :

  1. Écrire n = q(p-1) + r avec 0 r < p-1 (division euclidienne)
  2. a^n = a^{q(p-1) + r} = (a^{p-1})^q a^r 1^q a^r = a^r p
  3. Calculer a^r p (plus petit exposant)

Exemple : Calculer 2^{100} 7.

Comme 7 est premier et 7 2, on a 2^6 1 7.

100 = 6 16 + 4, donc 2^{100} = 2^{6 16 + 4} = (2^6)^{16} 2^4 1^{16} 16 = 16 2 7.

Ainsi 2^{100} 2 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^{n-1} 1 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^{14} = 16384 4 15 (car 16384 = 15 1092 + 4).

Comme 2^{14} 1 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_n c_1 c_0 = _k c_k,10^{,k}.

Pour tester la divisibilité par d, il suffit donc de remplacer chaque 10^{,k} par sa congruence modulo d.

Divisibilité par 9 (et par 3) : 10 1 9, donc 10^{,k} 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 11, donc 10^{,k} (-1)^k : 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 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^{,k} 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_1 c_2 c_{10} est valide lorsque

[formule]

Le dernier chiffre c_{10} 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

[formule]

Or 121 = 11 11, donc la clé qui convient est c_{10} = 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. La sécurité repose sur :

  • factoriser un très grand nombre est hors de portée, alors que le multiplier ne coûte rien
  • le petit théorème de Fermat permet en revanche de calculer des puissances modulo n très efficacement

9.2 Nombres de Mersenne et de Fermat

Nombres de Mersenne : Un nombre de Mersenne est de la forme M_n = 2^n - 1 avec n N^*.

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

Nombres de Fermat : Un nombre de Fermat est de la forme F_n = 2^{2^n} + 1 avec n N.

Les seuls nombres de Fermat premiers connus sont F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257, F_4 = 65537.

10. Résolution d'équations modulo p

Résolution de ax b p : Pour résoudre ax b 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^{p-1} 1 p, donc a^{-1} a^{p-2} p
  3. La solution unique est x ba^{p-2} p

Exemple : Résoudre 5x 3 7.

L'inverse de 5 modulo 7 est 5^{7-2} = 5^5 = 3125 3 7 (car 5^3 = 125 6 7, donc 5^5 = 5^3 5^2 6 4 = 24 3 7).

Donc x 3 3 = 9 2 7.

Vérification : 5 2 = 10 3 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^{p-1} 1 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