Niveau : supérieur, du facile au difficile. Durée estimée : 90 min. 10 exercices avec corrections détaillées.
Rappel des notions clés
Pour savoir si un entier $n \ge 2$ est premier (divisible seulement par 1 et par lui-même), teste sa divisibilité par les nombres premiers $p$ tels que $p^2 \le n$ : si aucun ne divise $n$, il est premier. Exemple : pour 97, tu testes 2, 3, 5 et 7, car $11^2 = 121 > 97$ ; aucun ne divise 97, il est premier. La raison : si $n$ est composé, c'est-à-dire $n = ab$ avec $1 < a \le b$, alors $a^2 \le n$, et un facteur premier de $a$ divise $n$.
Le crible d'Ératosthène applique ce test à tous les entiers de 2 à $N$ d'un coup. Le plus petit entier non barré, $p$, est premier : barre ses multiples à partir de $p^2$, puis passe au suivant non barré. Arrête-toi dès que $p^2 > N$ : ce qui reste, ce sont les nombres premiers jusqu'à $N$.
Formules à retenir :
- Petit théorème de Fermat : si $p$ est premier et ne divise pas $a$, alors $a^{p-1} \equiv 1 \pmod{p}$.
- Théorème des nombres premiers : $\pi(x)$, le nombre de premiers inférieurs ou égaux à $x$, vérifie $\pi(x) \sim \dfrac{x}{\ln x}$, c'est-à-dire $\dfrac{\pi(x)}{x / \ln x} \to 1$ quand $x \to +\infty$.
- Près d'un grand $x$, environ un entier sur $\ln x$ est premier.
- Entre 1 et $x$, il y a $\lfloor x/d \rfloor$ multiples de $d$ (partie entière de $x/d$).
Piège classique : pour prouver l'infinité des nombres premiers, Euclide suppose qu'il n'y en a que $k$, $p_1, \dots, p_k$, et pose $N = p_1 p_2 \cdots p_k + 1$. Aucun $p_i$ ne divise $N$ (sinon il diviserait $N - p_1 p_2 \cdots p_k = 1$), donc un facteur premier de $N$ est nouveau. Écrire que $N$ est premier est faux en général, et inutile.
Exercices : niveau facile
Exercice 1 : Parmi 51, 67, 87, 91, 97 et 143, lesquels sont premiers ? Justifie avec le moins de divisions possible.
Correction :
On teste les diviseurs premiers $p$ tels que $p^2 \le n$. Pour $n < 121 = 11^2$, il suffit de tester 2, 3, 5 et 7 : $51 = 3 \times 17$, $87 = 3 \times 29$ (somme des chiffres multiple de 3) et $91 = 7 \times 13$, tandis que 67 et 97 ne sont divisibles par aucun des quatre.
Pour 143, $\sqrt{143} \approx 11,96$ : il faut aussi tester 11, et $143 = 11 \times 13$.
Seuls 67 et 97 sont premiers. Erreur à éviter : s'arrêter à 7 pour 143, qui dépasse $11^2$.
Exercice 2 : On applique le crible d'Ératosthène aux entiers de 2 à 50.
a) Par quels nombres premiers faut-il cribler ? Justifie.
b) Pourquoi peut-on commencer à barrer les multiples de $p$ à partir de $p^2$ ?
c) Donne la liste obtenue et la valeur de $\pi(50)$.
Correction :
a) Un composé $n \le 50$ a un facteur premier $p$ avec $p^2 \le 50$ : on crible par 2, 3, 5 et 7, puis on s'arrête, car $11^2 = 121 > 50$.
b) Un multiple $kp$ avec $2 \le k < p$ a un facteur premier qui divise $k$, donc plus petit que $p$ : il est déjà barré.
c) Il reste 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 et 47, donc $\pi(50) = 15$.
Exercice 3 : Calcule le reste de la division euclidienne de $2^{100}$ par 13.
Correction :
On réduit l'exposant grâce au petit théorème de Fermat. Comme 13 est premier et ne divise pas 2, $2^{12} \equiv 1 \pmod{13}$. Or $100 = 12 \times 8 + 4$, donc $2^{100} = (2^{12})^8 \times 2^4 \equiv 2^4 = 16 \equiv 3 \pmod{13}$.
Le reste vaut 3. Erreur à éviter : réduire l'exposant modulo 13 au lieu de modulo 12.
Exercices : niveau moyen
Exercice 4 : On donne $\pi(100) = 25$, $\pi(1000) = 168$ et $\pi(10^6) = 78\,498$ (valeurs de l'OEIS, l'encyclopédie en ligne des suites d'entiers).
a) Pour chaque $x$, calcule $\dfrac{x}{\ln x}$, puis le rapport $r(x) = \dfrac{\pi(x)}{x / \ln x}$ arrondi au centième.
b) Ces rapports sont-ils cohérents avec le théorème des nombres premiers ? L'écart $\pi(x) - \dfrac{x}{\ln x}$ devient-il petit ?
Correction :
On calcule $\ln x$ avec $\ln(10^k) = k \ln 10$ et $\ln 10 \approx 2,3026$, puis on divise.
a) $\dfrac{100}{4,6052} \approx 21,7$ ; $\dfrac{1000}{6,9078} \approx 144,8$ ; $\dfrac{10^6}{13,8156} \approx 72\,382$. D'où $r(100) \approx 1,15$, $r(1000) \approx 1,16$ et $r(10^6) \approx 1,08$.
b) Le théorème annonce que $r(x)$ tend vers 1 : les rapports s'en approchent, lentement et pas de façon régulière. L'écart, lui, grandit : environ 3, puis 23, puis $6\,116$. Erreur à éviter : $\pi(x) \sim \dfrac{x}{\ln x}$ porte sur le rapport, pas sur la différence.
Exercice 5 : Un logiciel de chiffrement cherche un nombre premier proche de $10^{100}$ : il tire au hasard des entiers impairs de cette taille et les teste un par un. À l'aide du théorème des nombres premiers, estime le nombre moyen de tirages nécessaires.
Correction :
On utilise la proportion $\dfrac{1}{\ln x}$, puis on se restreint aux impairs.
$\ln(10^{100}) = 100 \ln 10 \approx 230,3$ : près de $10^{100}$, environ un entier sur 230 est premier. Ces premiers sont tous impairs, et les impairs ne forment que la moitié des entiers : parmi eux, la proportion double, $\dfrac{2}{230,3} \approx \dfrac{1}{115}$.
Si chaque tirage réussit avec la probabilité $q$, il faut en moyenne $\dfrac{1}{q}$ tirages (espérance d'une loi géométrique) : environ 115 tirages. Erreur à éviter : oublier le facteur 2 et répondre 230.
Exercice 6 : Deux nombres premiers sont jumeaux s'ils diffèrent de 2, comme 11 et 13.
a) Montre que tout nombre premier $p > 3$ s'écrit $6k - 1$ ou $6k + 1$, avec $k$ entier.
b) Déduis-en que, pour une paire de jumeaux $(p, p + 2)$ avec $p > 3$, on a $p = 6k - 1$.
c) Liste toutes les paires de jumeaux inférieurs à 50.
Correction :
On raisonne sur le reste $r$ de la division de $p$ par 6.
a) Si $r$ vaut 0, 2 ou 4, $p$ est pair ; si $r = 3$, $p$ est divisible par 3. Comme $p > 3$ est premier, $r$ vaut 1 ou 5 : $p = 6k + 1$ ou $p = 6k - 1$.
b) Si $p = 6k + 1$, alors $p + 2 = 3(2k + 1)$ est un multiple de 3 plus grand que 3, donc pas premier. Il reste $p = 6k - 1$.
c) On teste $(6k - 1, 6k + 1)$ pour $k$ de 1 à 8 : $(23, 25)$, $(35, 37)$ et $(47, 49)$ échouent. En ajoutant $(3, 5)$, on obtient 6 paires : $(3, 5)$, $(5, 7)$, $(11, 13)$, $(17, 19)$, $(29, 31)$ et $(41, 43)$.
Exercice 7 : On note $N_k = p_1 p_2 \cdots p_k + 1$, où $p_1 = 2$, $p_2 = 3$, $p_3 = 5$… sont les nombres premiers dans l'ordre. Un étudiant affirme que $N_k$ est toujours premier.
a) Vérifie son affirmation pour $k$ de 1 à 4.
b) Calcule $N_6$ et montre qu'il est divisible par 59. Conclus.
c) Que démontre vraiment la preuve d'Euclide ?
Correction :
On calcule, puis on relit la preuve.
a) $N_1 = 3$, $N_2 = 7$, $N_3 = 31$ et $N_4 = 211$ sont premiers : pour 211, aucun premier jusqu'à 13 ne le divise, et $17^2 > 211$.
b) $N_6 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30\,031 = 59 \times 509$ : $N_6$ n'est pas premier, l'affirmation est fausse.
c) Elle donne un facteur premier de $N_k$ hors de la liste, rien de plus : $N_k$ lui-même s'il est premier, sinon un plus petit, comme 59.
Exercices : niveau difficile
Exercice 8 : Soit $n \ge 2$ un entier.
a) Montre que les $n - 1$ entiers consécutifs $n! + 2$, $n! + 3$, …, $n! + n$ sont tous composés.
b) Déduis-en que deux nombres premiers consécutifs peuvent être aussi éloignés qu'on veut, puis donne 9 entiers consécutifs composés.
Correction :
On cherche un diviseur évident de chaque terme.
a) Pour $2 \le k \le n$, $k$ divise $n!$, donc il divise $n! + k$. Comme $2 \le k < n! + k$, c'est un diviseur différent de 1 et de $n! + k$ : ce nombre est composé.
b) Le nombre premier qui précède $n! + 2$ et celui qui suit $n! + n$ sont donc distants d'au moins $n$, avec $n$ aussi grand qu'on veut. Avec $10! = 3\,628\,800$ : les 9 entiers de $3\,628\,802$ à $3\,628\,810$ sont composés.
Exercice 9 : On veut retrouver $\pi(100)$ sans écrire le crible.
a) Par inclusion-exclusion, compte les entiers de 1 à 100 divisibles par au moins un des nombres 2, 3, 5 et 7, puis ceux qui ne le sont par aucun.
b) Quels sont ces derniers ? Déduis-en $\pi(100)$.
Correction :
On compte les multiples en alternant les signes (inclusion-exclusion), puis on soustrait de 100.
a) Pour 2, 3, 5 et 7 : $50 + 33 + 20 + 14 = 117$. Pour 6, 10, 14, 15, 21 et 35 : $16 + 10 + 7 + 6 + 4 + 2 = 45$. Pour 30, 42, 70 et 105 : $3 + 2 + 1 + 0 = 6$. Pour 210 : 0. Divisibles par au moins un : $117 - 45 + 6 - 0 = 78$ entiers, donc 22 entiers ne sont divisibles par aucun des quatre.
b) Un composé $n \le 100$ a un facteur premier $p$ avec $p^2 \le 100$, donc 2, 3, 5 ou 7. Les 22 entiers sont donc 1, qui n'est pas premier, et les 21 nombres premiers compris entre 11 et 100. En ajoutant 2, 3, 5 et 7 : $\pi(100) = 21 + 4 = 25$.
Exercice 10 : Montre qu'il existe une infinité de nombres premiers de la forme $4k + 3$. Indication : suppose qu'il n'y en a qu'un nombre fini, $p_1, \dots, p_m$, et étudie $N = 4 p_1 p_2 \cdots p_m - 1$.
Correction :
On reprend la preuve d'Euclide en suivant les restes modulo 4.
Comme 3 fait partie de la liste, $N \ge 11$. De plus $N \equiv -1 \equiv 3 \pmod 4$ : $N$ est impair, donc chacun de ses facteurs premiers est congru à 1 ou à 3 modulo 4.
Si tous étaient congrus à 1, leur produit $N$ le serait aussi. Donc $N$ a un facteur premier $q \equiv 3 \pmod 4$, qui est l'un des $p_i$. Alors $q$ divise $4 p_1 \cdots p_m$ et $N$, donc leur différence, 1 : c'est absurde.
Il existe une infinité de nombres premiers de la forme $4k + 3$. Erreur à éviter : recopier la preuve pour $4k + 1$ ; un produit de facteurs congrus à 3 peut être congru à 1 modulo 4 ($3 \times 7 = 21$).
Bilan et conseils
Pour tester un entier ou cribler jusqu'à $N$, ne va jamais au-delà de la racine carrée.
Ce qu'il faut retenir : la preuve d'Euclide fournit un facteur premier nouveau, pas un nombre premier. Une propriété vérifiée sur quelques cas n'est pas démontrée pour autant : $N_6 = 30\,031$ le rappelle.
Sources
Valeurs de $\pi(10^n)$ utilisées dans l'exercice 4 : OEIS, suite A006880, oeis.org/A006880.