Nombres premiers

Un nombre premier n'a que deux diviseurs, 1 et lui-même : ce sont les « briques » avec lesquelles on fabrique, par multiplication, tous les autres nombres entiers.

Objectifs

Savoir reconnaître un nombre premier.
Trouver les nombres premiers avec le crible d'Ératosthène.
Tester rapidement si un nombre est premier.
Décomposer un nombre en produit de facteurs premiers et s'en servir (fractions, PGCD, PPCM).
Connaître quelques propriétés et usages célèbres des nombres premiers.

1. Qu'est-ce qu'un nombre premier ?

Un diviseur d'un nombre entier \(n\) est un entier \(d\) tel que \(n = d \times k\) avec \(k\) entier. Par exemple, les diviseurs de \(12\) sont \(1, 2, 3, 4, 6, 12\).

\(2, 3, 5, 7, 11, 13\) sont premiers.
\(12\) n'est pas premier (il a six diviseurs) : on dit qu'il est composé.
\(1\) n'est pas premier : il n'a qu'un seul diviseur.
\(2\) est le seul nombre premier pair : tout autre nombre pair est divisible par \(2\).

Les nombres premiers inférieurs à \(50\) sont :

\[2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47\]

Lequel de ces nombres est premier ?

\(1\)
\(51\)
\(29\)

\(29\) n'est divisible que par \(1\) et \(29\). \(1\) n'a qu'un diviseur, et \(51 = 3 \times 17\) est composé.

2. Trouver les nombres premiers : le crible d'Ératosthène

Méthode pour les nombres de \(2\) à \(30\) :

Étape 1 : on écrit tous les nombres de \(2\) à \(30\). On barre \(1\), qui n'est pas premier.

Étape 2 : \(2\) est premier ; on barre tous ses multiples : \(4, 6, 8, \dots, 30\).

Étape 3 : le premier nombre non barré est \(3\) : il est premier ; on barre ses multiples \(9, 15, 21, 27\) (les autres sont déjà barrés).

Étape 4 : le suivant est \(5\) : premier ; on barre \(25\) (les autres multiples de \(5\) sont déjà barrés).

Étape 5 : on peut s'arrêter, car \(7 \times 7 = 49 > 30\). Il reste les nombres premiers : \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\).

Nombres de 1 à 30 : les nombres premiers sont en gras
1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30

Combien y a-t-il de nombres premiers entre \(1\) et \(30\) ?

\(9\)
\(10\)
\(15\)

Ce sont \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\) : il y en a \(10\).

3. Tester si un nombre est premier

Exemple résolu : 97 et 91 sont-ils premiers ?

Cherche d'abord, puis ouvre la solution.

Voir la solution

Pour \(97\) : \(10 \times 10 = 100 > 97\), donc on teste \(2, 3, 5, 7\).

\(97\) est impair : pas divisible par \(2\).
\(9 + 7 = 16\), pas multiple de \(3\) : pas divisible par \(3\).
Il ne finit ni par \(0\) ni par \(5\) : pas divisible par \(5\).
\(97 = 7 \times 13 + 6\) : pas divisible par \(7\).

Donc \(97\) est premier.

Pour \(91\) : on teste \(2, 3, 5, 7\) : \(91 = 7 \times 13\). Donc \(91\) n'est pas premier, même s'il « a l'air » premier !

Pour savoir si \(143\) est premier, quels nombres premiers suffit-il de tester ?

\(2, 3, 5, 7, 11\)
Tous les nombres de \(2\) à \(142\)
Seulement \(2\) et \(3\)

\(11 \times 11 = 121 \leq 143\) mais \(13 \times 13 = 169 > 143\) : on teste jusqu'à \(11\). Et justement \(143 = 11 \times 13\), il n'est pas premier.

4. Décomposer un nombre en facteurs premiers

Exemple : décomposons \(60\) avec un arbre. On divise à chaque fois par le plus petit nombre premier possible.

60 est pair : on divise par 2. On obtient 2 (premier, en rouge) et 30.

30 est pair : on divise encore par 2. On obtient 2 et 15.

15 n'est pas pair mais divisible par 3 : on obtient 3 et 5, tous deux premiers. L'arbre est fini.

On multiplie toutes les feuilles rouges : c'est la décomposition de 60 en facteurs premiers.

\[60 = 2^2 \times 3 \times 5\]

Exemple résolu : simplifier une fraction, PGCD et PPCM

Décompose \(84\), puis simplifie \(\frac{60}{84}\) et trouve le PGCD et le PPCM de \(60\) et \(84\). Cherche d'abord.

Étape 1 : \(84 = 2 \times 42 = 2 \times 2 \times 21 = 2^2 \times 3 \times 7\).

Étape 2 : facteurs communs à \(60 = 2^2 \times 3 \times 5\) et \(84 = 2^2 \times 3 \times 7\) : \(2^2 \times 3\), donc \(\text{PGCD}(60 ; 84) = 12\).

Étape 3 : \[\frac{60}{84} = \frac{2^2 \times 3 \times 5}{2^2 \times 3 \times 7} = \frac{5}{7}\]

Étape 4 : le PPCM prend tous les facteurs avec le plus grand exposant : \(2^2 \times 3 \times 5 \times 7 = 420\).

Quelle est la décomposition en facteurs premiers de \(72\) ?

\(8 \times 9\)
\(2^3 \times 3^2\)
\(2 \times 36\)

\(72 = 2 \times 2 \times 2 \times 3 \times 3 = 2^3 \times 3^2\). Les écritures \(8 \times 9\) et \(2 \times 36\) sont justes, mais \(8\), \(9\) et \(36\) ne sont pas premiers.

5. Quelques propriétés et une petite histoire

Il y a une infinité de nombres premiers : le mathématicien grec Euclide l'a démontré il y a plus de 2 000 ans.
Plus on avance, plus ils se font rares, mais on en trouve toujours d'autres.
Multiplier deux grands nombres premiers est facile ; retrouver ces deux nombres à partir de leur produit est extrêmement long, même pour un ordinateur. C'est l'idée du chiffrement RSA.

Il y a environ 20 000 ansL'os d'Ishango, trouvé en République démocratique du Congo, porte des groupes d'encoches ; certains chercheurs y voient les nombres 11, 13, 17 et 19, mais cette lecture reste une hypothèse discutée.
Vers 300 av. J.-C.Euclide démontre, dans ses Éléments, qu'il existe une infinité de nombres premiers.
IIIe siècle av. J.-C.Ératosthène, savant d'Alexandrie, décrit son crible.
1977Rivest, Shamir et Adleman inventent le chiffrement RSA, fondé sur les grands nombres premiers.

L'idée de la preuve d'Euclide

Supposons qu'il n'y ait qu'un nombre fini de nombres premiers, par exemple \(2, 3, 5\). Cherche d'abord : que penses-tu du nombre \(2 \times 3 \times 5 + 1\) ?

Voir la solution

\(N = 2 \times 3 \times 5 + 1 = 31\). Divisé par \(2\), \(3\) ou \(5\), il reste toujours \(1\) : aucun de ces nombres ne divise \(N\). Donc \(N\) est premier, ou alors il a un facteur premier qui n'est pas dans la liste. Dans les deux cas, la liste était incomplète. Ce raisonnement marche avec n'importe quelle liste finie : il y a donc une infinité de nombres premiers.

Combien existe-t-il de nombres premiers ?

Exactement \(25\)
Environ un million
Une infinité

Euclide a démontré qu'il y en a une infinité. (Il y en a \(25\) inférieurs à \(100\), mais la liste ne s'arrête jamais.)

Erreurs fréquentes

Dire que \(1\) est premier : il n'a qu'un seul diviseur.
Croire que tous les nombres impairs sont premiers (\(9\), \(21\), \(91\) ne le sont pas).
Oublier que \(2\) est premier.
S'arrêter trop tôt dans une décomposition : \(60 = 4 \times 15\) n'est pas une décomposition en facteurs premiers.

Récapitulatif

Un nombre premier a exactement deux diviseurs : \(1\) et lui-même.
Le crible d'Ératosthène permet de les trouver en barrant les multiples.
Pour tester \(n\), on essaie les nombres premiers \(p\) avec \(p \times p \leq n\).
Tout entier \(\geq 2\) se décompose de façon unique en produit de facteurs premiers ; cela sert à simplifier les fractions et à calculer PGCD et PPCM.
Il existe une infinité de nombres premiers (Euclide) ; ils protègent nos communications (RSA).

Nombre premier

Entier qui a exactement deux diviseurs : \(1\) et lui-même. Exemples : \(2, 3, 5, 7, 11\).

Le nombre \(1\)

N'est pas premier : il n'a qu'un seul diviseur.

Crible d'Ératosthène

On barre les multiples de \(2\), \(3\), \(5\)… ; les nombres restants sont premiers.

Test de primalité

Tester les diviseurs premiers \(p\) tels que \(p \leq \sqrt{n}\).

Décomposition

Produit unique de facteurs premiers, par exemple \(60 = 2^2 \times 3 \times 5\).