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 :

Écrire tous les entiers de 2 à n
Prendre le premier nombre non barré (p = 2)
Barrer tous les multiples de p strictement supérieurs à p
Répéter avec le prochain nombre non barré
S'arrêter quand p^2 > n
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.

Si p a, alors PGCD(a, p) = 1
Si ab 0 p, alors a 0 p ou b 0 p
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 :

Écrire n = q(p-1) + r avec 0 r < p-1 (division euclidienne)
a^n = a^{q(p-1) + r} = (a^{p-1})^q a^r 1^q a^r = a^r p
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. Fonction indicatrice d'Euler

Fonction d'Euler : Pour n N^*, on note (n) le nombre d'entiers k avec 1 k n tels que PGCD(k, n) = 1.

(n) est appelée la fonction indicatrice d'Euler.

Exemples :

(1) = 1
(p) = p - 1 si p est premier (tous les entiers de 1 à p-1 sont premiers avec p)
(12) = 4 (les nombres premiers avec 12 sont 1, 5, 7, 11)
(8) = 4 (les nombres premiers avec 8 sont 1, 3, 5, 7)

Formule pour : Si n = p_1^{_1} p_2^{_2} p_k^{_k} est la décomposition en facteurs premiers de n, alors :

[formule]

Exemple : (12) = (2^2 3) = 12 (1 - 1{2}) (1 - 1{3}) = 12 1{2} 2{3} = 4

8. Théorème d'Euler (généralisation)

Théorème d'Euler : Soient n N^* et a un entier premier avec n. Alors :

[formule]

Exemple : Calculer 3^{20} 8.

(8) = 4, et PGCD(3, 8) = 1, donc 3^4 1 8.

Ainsi 3^{20} = (3^4)^5 1^5 = 1 8.

Remarque : Le petit théorème de Fermat est un cas particulier du théorème d'Euler lorsque n = p est premier (car (p) = p - 1).

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 :

Le calcul de (n) nécessite la factorisation de n
Le petit théorème de Fermat permet de calculer des puissances modulo n

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 :

Comme PGCD(a, p) = 1, a admet un inverse modulo p
Par le petit théorème de Fermat : a^{p-1} 1 p, donc a^{-1} a^{p-2} p
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é :

Nombres premiers : infinité (théorème d'Euclide), test jusqu'à n
Lemme d'Euclide : si p premier et p ab, alors p a ou p b
Petit théorème de Fermat : si p premier et p a, alors a^{p-1} 1 p
Fonction d'Euler : (n) = nombre d'entiers n premiers avec n
Théorème d'Euler : si PGCD(a, n) = 1, alors a^{(n)} 1 n
Applications : calcul de puissances modulo p, résolution d'équations, cryptographie