I. Qu'est-ce qu'un nombre premier ?
Dans la leçon précédente, nous avons vu que tout entier possède des diviseurs. La plupart des entiers peuvent être "découpés" en facteurs plus petits. Mais certains entiers résistent à tout découpage : ce sont les nombres premiers.
Un entier \(p \geq 2\) est dit premier s'il admet exactement deux diviseurs positifs : 1 et lui-même.
Un entier \(n \geq 2\) qui n'est pas premier est dit composé : il admet au moins un diviseur \(d\) avec \(1 < d < n\).
.png)
On pourrait se demander pourquoi 1 n'est pas considéré comme premier, puisqu'il ne se décompose pas. La raison est fondamentale : si 1 était premier, le théorème fondamental de l'arithmétique (unicité de la décomposition en facteurs premiers) serait faux, car on pourrait écrire \(6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3\), etc. En excluant 1, la décomposition est unique à l'ordre des facteurs près.
II. Les premiers nombres premiers
Les premiers nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47… Remarques importantes :
- 2 est le seul nombre premier pair. Tout entier pair supérieur à 2 est divisible par 2, donc composé.
- Il existe une infinité de nombres premiers (démontré par Euclide, voir section VI).
- Les nombres premiers deviennent de plus en plus rares à mesure qu'on avance dans les entiers, mais ne s'arrêtent jamais.
Grille des entiers de 2 à 50 — les nombres premiers apparaissent de manière irrégulière et de plus en plus espacés.
III. Tester si un nombre est premier
Comment savoir si un grand entier est premier ? Il existe un critère très efficace qui limite le nombre de diviseurs à tester.
Un entier \(n \geq 2\) est composé si et seulement s'il admet un diviseur premier \(p\) vérifiant \(p \leq \sqrt{n}\).
Autrement dit : pour tester si \(n\) est premier, il suffit de tester sa divisibilité par tous les nombres premiers \(p \leq \sqrt{n}\).
Supposons \(n\) composé : il existe \(a, b\) avec \(n = a \times b\) et \(1 < a \leq b < n\).
Alors \(a^2 \leq a \times b = n\), donc \(a \leq \sqrt{n}\).
Tout diviseur premier de \(a\) est aussi un diviseur de \(n\) inférieur ou égal à \(\sqrt{n}\).
Réciproquement, si \(n\) est premier, il n'a aucun diviseur dans \(\{2, 3, \ldots, \lfloor\sqrt{n}\rfloor\}\). \(\square\)
\(\sqrt{97} \approx 9{,}85\). Il faut donc tester les diviseurs premiers \(\leq 9\) : c'est-à-dire 2, 3, 5, 7.
97 est impair → non divisible par 2.
Somme des chiffres : 9+7 = 16, non divisible par 3.
Ne finit pas par 0 ou 5 → non divisible par 5.
\(97 = 7 \times 13 + 6\) → reste 6, non divisible par 7.
\(\sqrt{221} \approx 14{,}87\). Premiers à tester : 2, 3, 5, 7, 11, 13.
221 est impair → non divisible par 2.
2+2+1 = 5, non divisible par 3.
Ne finit pas par 0 ou 5 → non divisible par 5.
\(221 = 7 \times 31 + 4\) → non divisible par 7.
\(221 = 11 \times 20 + 1\) → non divisible par 11.
\(221 = 13 \times 17 + 0\) → \(221 = 13 \times 17\) ✓
IV. Le crible d'Ératosthène
Pour trouver tous les nombres premiers jusqu'à un certain entier \(N\), l'algorithme le plus élégant est le crible d'Ératosthène, inventé par le mathématicien grec Ératosthène de Cyrène vers 240 av. J.-C.
Algorithme pour trouver tous les premiers jusqu'à \(N\) :
- Écrire tous les entiers de 2 à \(N\).
- Le plus petit nombre non rayé est premier. L'entourer.
- Rayer tous ses multiples (sauf lui-même).
- Répéter les étapes 2 et 3 jusqu'à ce que le plus petit non rayé soit \(> \sqrt{N}\).
- Tous les nombres restants (non rayés) sont premiers.
À l'étape 4, quand le plus petit non rayé est \(p > \sqrt{N}\), tout multiple de \(p\) qui serait \(\leq N\) s'écrirait \(p \times k\) avec \(k \leq N/p < \sqrt{N} < p\). Donc \(k\) est un entier strictement plus petit que \(p\) — or ce plus petit multiple aurait déjà été rayé par un premier précédent. Il n'y a plus rien à faire.
On liste : 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.
2 est premier. On raye : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
3 est premier. On raye : 9, 15, 21, 27 (les autres multiples de 3 déjà rayés).
5 est premier. On raye : 25 (les autres déjà rayés).
\(\sqrt{30} \approx 5{,}47\), donc le prochain serait 7 \(> \sqrt{30}\) : on s'arrête.
Nombres restants non rayés : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
V. Décomposition en facteurs premiers
Rappelons le théorème fondamental de l'arithmétique vu en L1, et voyons comment l'appliquer méthodiquement.
Tout entier \(n \geq 2\) se décompose de façon unique en produit de facteurs premiers : \[n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}\] où \(p_1 < p_2 < \cdots < p_k\) sont des nombres premiers et \(\alpha_i \geq 1\).
On divise successivement par les premiers croissants :
\(2\,310 \div 2 = 1\,155\)
\(1\,155 \div 3 = 385\)
\(385 \div 5 = 77\)
\(77 \div 7 = 11\)
\(11\) est premier.
\(1\,800 = 2^3 \times 3^2 \times 5^2\)
Nombre de diviseurs positifs : Si \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}\), le nombre de diviseurs est \((\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\).
Pour 1 800 : \((3+1)(2+1)(2+1) = 4 \times 3 \times 3 = 36\) diviseurs.
Tout diviseur \(d\) de \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}\) s'écrit \(d = p_1^{\beta_1} \cdots p_k^{\beta_k}\) avec \(0 \leq \beta_i \leq \alpha_i\).
Pour chaque \(p_i\), il y a \(\alpha_i + 1\) choix possibles pour \(\beta_i\) : \(0, 1, \ldots, \alpha_i\).
Les choix étant indépendants, le nombre total de diviseurs est le produit des nombres de choix. \(\square\)
VI. Infinité des nombres premiers
Euclide a démontré il y a plus de 2 300 ans qu'il existe une infinité de nombres premiers. Sa preuve est l'une des plus belles de toute la mathématique.
Supposons par l'absurde qu'il n'existe qu'un nombre fini de premiers : \(p_1, p_2, \ldots, p_k\).
Considérons \(N = p_1 \times p_2 \times \cdots \times p_k + 1\).
\(N > 1\), donc \(N\) admet au moins un diviseur premier \(p\).
Ce premier \(p\) doit être l'un des \(p_i\). Or \(p_i \mid p_1 \cdots p_k\) et \(p_i \mid N\), donc \(p_i \mid (N - p_1 \cdots p_k) = 1\).
Mais aucun premier ne divise 1 — contradiction ! \(\square\)
Donc la liste \(p_1, \ldots, p_k\) ne peut pas être exhaustive : il existe toujours un premier de plus.
VII. Nombres premiers et cryptographie
La cryptographie moderne — qui sécurise les transactions bancaires, les messageries, les accès aux sites web — repose sur un fait arithmétique simple : multiplier deux grands nombres premiers est facile, mais factoriser leur produit est extrêmement difficile.
Le chiffrement RSA (utilisé par les banques, les gouvernements, le BCEAO) utilise des nombres premiers de 300 à 600 chiffres. Même les ordinateurs les plus puissants ne peuvent pas factoriser leur produit en un temps raisonnable. Chaque fois qu'un lycéen de Ouagadougou consulte un site en "https://", des nombres premiers protègent ses données.
VIII. Application burkinabè — Codes et partages
Une artisane de Saponé a tissé 143 nattes. Elle veut les répartir en lots égaux de plus d'une natte, pour les vendre aux grossistes. Est-ce possible ?
\(\sqrt{143} \approx 11{,}96\). Premiers à tester : 2, 3, 5, 7, 11.
143 est impair → pas divisible par 2.
1+4+3 = 8, non divisible par 3.
Ne finit pas par 0 ou 5 → pas par 5.
\(143 = 7 \times 20 + 3\) → pas par 7.
\(143 = 11 \times 13\) ✓
Le chef du village de Laongo veut numéroter les cases de 1 à \(n\). Il veut que \(n\) soit premier, compris entre 100 et 120, et le plus petit possible. Quel est ce \(n\) ?
Testons : 101, 102, 103, 104, 105, 106, 107…
102 = 2×51, 103 : \(\sqrt{103} \approx 10{,}1\), on teste 2, 3, 5, 7.
103 : impair, 1+0+3=4 (non div. par 3), ne finit pas par 5, \(103 = 7 \times 14 + 5\) (non div. par 7).
Aucun premier ≤ 10 ne divise 103 → 103 est premier.
Une coopérative de la région du Centre-Nord a récolté 1 517 kg d'arachides. Le responsable souhaite les répartir en sacs de même poids (entier, en kg), avec plus d'un sac et plus d'un kilo par sac.
- a) Déterminer si 1 517 est premier en testant les diviseurs premiers jusqu'à \(\sqrt{1517} \approx 38{,}9\).
- b) Si 1 517 est composé, donner toutes les façons de constituer des sacs égaux.
- c) Même question pour 1 523 kg.
- d) Lequel des deux nombres, 1 517 ou 1 523, offre le plus de souplesse pour la répartition ? Pourquoi ?
✏️ Exercices d'application
Pour chacun des entiers suivants, déterminer s'il est premier ou composé. Si composé, donner sa décomposition :
- a) 91
- b) 127
- c) 323
- d) 401
b) \(\sqrt{127} \approx 11{,}3\). Tester 2, 3, 5, 7, 11 : 127 impair, 1+2+7=10 (non div. 3), ne finit pas par 5, \(127 = 7\times18+1\), \(127=11\times11+6\). Aucun ne divise. 127 est premier.
c) \(\sqrt{323} \approx 17{,}97\). Tester jusqu'à 17 : \(323 = 17 \times 19\). Composé.
d) \(\sqrt{401} \approx 20{,}02\). Tester 2,3,5,7,11,13,17,19 : 401 impair, 4+0+1=5 (non div. 3), \(401=7\times57+2\), \(401=11\times36+5\), \(401=13\times30+11\), \(401=17\times23+10\), \(401=19\times21+2\). 401 est premier.
Appliquer le crible d'Ératosthène pour trouver tous les nombres premiers entre 50 et 80. Lister les étapes.
Multiples de 2 entre 50 et 80 : 50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80 — rayés.
Multiples de 3 impairs : 51,57,63,69,75 — rayés.
Multiples de 5 impairs restants : 55,65 — rayés.
Multiples de 7 impairs restants : 77 = 7×11 — rayé.
Nombres restants (premiers entre 50 et 80) : 53, 59, 61, 67, 71, 73, 79.
- a) Décomposer 7 560 en facteurs premiers.
- b) Combien de diviseurs positifs 7 560 possède-t-il ?
- c) Vérifier en retrouvant \(\text{PGCD}(7560, 2520)\) par décomposition.
(7560 ÷ 2 = 3780 ÷ 2 = 1890 ÷ 2 = 945 ÷ 3 = 315 ÷ 3 = 105 ÷ 3 = 35 ÷ 5 = 7)
b) Nombre de diviseurs : \((3+1)(3+1)(1+1)(1+1) = 4 \times 4 \times 2 \times 2 = 64\)
c) \(2520 = 2^3 \times 3^2 \times 5 \times 7\)
\(\text{PGCD}(7560, 2520) = 2^3 \times 3^2 \times 5 \times 7 = 8 \times 9 \times 5 \times 7 = 2520\)
Donc 2520 divise 7560 : \(7560 = 2520 \times 3\). ✓
On appelle nombres premiers jumeaux deux nombres premiers de la forme \((p, p+2)\), comme (3,5), (5,7), (11,13), (17,19)…
- a) Trouver toutes les paires de premiers jumeaux entre 20 et 80.
- b) Montrer que pour tout premier \(p \geq 5\), \(p\) est de la forme \(6k+1\) ou \(6k+5\) (c'est-à-dire \(6k-1\)). En déduire que tout couple de jumeaux \((p, p+2)\) avec \(p \geq 5\) est de la forme \((6k-1, 6k+1)\).
b) Tout entier \(n\) est de la forme \(6k, 6k+1, 6k+2, 6k+3, 6k+4\) ou \(6k+5\).
— \(6k\) : divisible par 6 (composé).
— \(6k+2\) : divisible par 2 (composé si \(>2\)).
— \(6k+3\) : divisible par 3 (composé si \(>3\)).
— \(6k+4\) : divisible par 2 (composé).
Donc tout premier \(p \geq 5\) est de la forme \(6k+1\) ou \(6k+5 = 6(k+1)-1\).
Si \(p = 6k+1\), alors \(p+2 = 6k+3 = 3(2k+1)\), divisible par 3 → non premier sauf si \(= 3\). Impossible pour \(p \geq 5\).
Donc \(p\) doit être de la forme \(6k-1\) et \(p+2 = 6k+1\). Tout couple jumeau \((p,p+2)\) avec \(p \geq 5\) est bien de la forme \((6k-1, 6k+1)\).
L'ORTB (Office de Radiodiffusion et Télévision du Burkina) attribue des fréquences en kHz. Un ingénieur choisit des fréquences qui sont des nombres premiers pour minimiser les interférences. Il envisage : 1 009 kHz, 1 013 kHz, et 1 021 kHz.
- a) \(\sqrt{1021} \approx 31{,}95\). Quels premiers faut-il tester ?
- b) Vérifier que 1 009 = 1 009 (tester divisibilité par 7, 11, 13, 17, 19, 23, 29, 31).
- c) 1 013 est-il premier ? (Indication : tester jusqu'à 31.)
- d) Vérifier que \(1\,021 = 1\,021\) est premier.
b) 1009 : impair, somme chiffres = 10 (non div. 3), ne finit pas par 0/5.
\(1009 = 7\times144+1\), \(= 11\times91+8\), \(= 13\times77+8\), \(= 17\times59+6\), \(= 19\times53+2\), \(= 23\times43+20\), \(= 29\times34+23\), \(= 31\times32+17\).
1 009 est premier.
c) 1013 : impair, somme = 5 (non div. 3), pas en 0/5.
\(1013 = 7\times144+5\), \(= 11\times92+1\), \(= 13\times77+12\), \(= 17\times59+10\), \(= 19\times53+6\), \(= 23\times44+1\), \(= 29\times34+27\), \(= 31\times32+21\).
1 013 est premier.
d) 1021 : même démarche, tous les restes sont non nuls jusqu'à 31. 1 021 est premier.
Les trois fréquences sont toutes premières — excellent choix pour l'ingénieur.
Récapitulatif — Nombres premiers
- Définition : \(p \geq 2\) est premier s'il a exactement deux diviseurs positifs : 1 et \(p\). Le nombre 1 n'est pas premier.
- Critère de primalité : pour tester si \(n\) est premier, tester la divisibilité par tous les premiers \(p \leq \sqrt{n}\) seulement.
- Crible d'Ératosthène : algorithme systématique pour trouver tous les premiers jusqu'à \(N\), en rayant les multiples successifs.
- Théorème fondamental : tout entier \(\geq 2\) se décompose de façon unique en produit de premiers. Nombre de diviseurs : \(\prod (\alpha_i + 1)\).
- Infinité : il existe une infinité de nombres premiers (preuve par l'absurde d'Euclide).
- 2 est le seul premier pair. Tout premier \(\geq 5\) est de la forme \(6k \pm 1\).
- Applications : cryptographie RSA, codes, partages et répartitions.