Exercices Corrigés sur les Nombres Premiers : Crible et Répartition
Compétences travaillées : Identifier et générer des nombres premiers, comprendre et appliquer le crible d'Ératosthène, utiliser la fonction de compte des nombres premiers ($\pi(x)$), comprendre les concepts de répartition des nombres premiers (conjecture de Goldbach, théorème des nombres premiers).
Erreurs fréquentes : Confusion entre nombres premiers et nombres composés, erreurs dans l'application du crible (ne pas barrer tous les multiples), mauvaise interprétation de la répartition des nombres premiers (tendance à penser qu'ils sont réguliers), difficultés avec les preuves théoriques.
Les nombres premiers sont les briques élémentaires de l'arithmétique. Cette série d'exercices te permettra de bien comprendre comment les identifier, comment ils sont distribués et quelques-uns des grands problèmes ouverts qui les entourent.
Exercice 1 : Identification des nombres premiers
Parmi les nombres suivants, lesquels sont premiers ? Pour chaque nombre composé, donne sa factorisation en nombres premiers : 17, 21, 29, 33, 41, 51, 57, 67, 77, 87.
Correction :
Un nombre premier est un entier naturel supérieur à 1 qui n'admet que deux diviseurs distincts : 1 et lui-même.
- 17 : Diviseurs : 1, 17. C'est un nombre premier.
- 21 : Diviseurs : 1, 3, 7, 21. Composé. Factorisation : $3 \times 7$.
- 29 : Diviseurs : 1, 29. C'est un nombre premier.
- 33 : Diviseurs : 1, 3, 11, 33. Composé. Factorisation : $3 \times 11$.
- 41 : Diviseurs : 1, 41. C'est un nombre premier.
- 51 : Diviseurs : 1, 3, 17, 51. Composé. Factorisation : $3 \times 17$. (Vérifier la divisibilité par 3 : somme des chiffres $5+1=6$, qui est divisible par 3).
- 57 : Diviseurs : 1, 3, 19, 57. Composé. Factorisation : $3 \times 19$. (Vérifier la divisibilité par 3 : somme des chiffres $5+7=12$, qui est divisible par 3).
- 67 : Diviseurs : 1, 67. C'est un nombre premier. (On peut vérifier jusqu'à $\sqrt{67} \approx 8.1$, donc on teste 2, 3, 5, 7. 67 n'est divisible par aucun).
- 77 : Diviseurs : 1, 7, 11, 77. Composé. Factorisation : $7 \times 11$.
- 87 : Diviseurs : 1, 3, 29, 87. Composé. Factorisation : $3 \times 29$. (Vérifier la divisibilité par 3 : somme des chiffres $8+7=15$, qui est divisible par 3).
Les nombres premiers sont : 17, 29, 41, 67.
Astuce : Pour vérifier si un nombre $N$ est premier, il suffit de tester sa divisibilité par tous les nombres premiers $p$ tels que $p^2 \le N$.
Exercice 2 : Application du Crible d'Ératosthène (petit ensemble)
Utilise le crible d'Ératosthène pour trouver tous les nombres premiers inférieurs à 30.
Correction :
Le crible d'Ératosthène consiste à lister tous les nombres entiers à partir de 2 jusqu'à la limite souhaitée, puis à barrer systématiquement les multiples des nombres premiers rencontrés.
Liste des nombres de 2 à 29 :
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.
1. Le premier nombre premier est 2. Barre tous ses multiples : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28.
Nombres restants : 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.
2. Le prochain nombre premier est 3. Barre tous ses multiples parmi ceux qui restent : 9, 15, 21, 27.
Nombres restants : 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29.
3. Le prochain nombre premier est 5. Barre tous ses multiples parmi ceux qui restent : 25.
Nombres restants : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
4. Le prochain nombre premier est 7. Le plus petit multiple de 7 qui n'a pas encore été barré est $7 \times 7 = 49$, qui est supérieur à 29. Donc, nous n'avons plus rien à barrer pour 7, ni pour les premiers suivants (11, 13, etc.), car leurs carrés dépassent 29.
Les nombres premiers inférieurs à 30 sont les nombres restants :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Astuce : Il suffit de considérer les multiples des nombres premiers $p$ tels que $p^2 \le N$ (ici $N=29$). Les premiers à considérer sont donc 2, 3, 5, car $7^2=49 > 29$.
Exercice 3 : Petit théorème de Fermat
Le petit théorème de Fermat stipule que si $p$ est un nombre premier, alors pour tout entier $a$ non divisible par $p$, on a $a^{p-1} \equiv 1 \pmod{p}$.
a) Vérifie ce théorème pour $p=5$ et $a=3$.
b) Vérifie ce théorème pour $p=7$ et $a=2$.
c) Utilise le petit théorème de Fermat pour calculer le reste de la division euclidienne de $3^{10}$ par 11.
Correction :
a) Pour $p=5$ et $a=3$ :
On doit vérifier si $3^{5-1} \equiv 1 \pmod{5}$, c'est-à-dire $3^4 \equiv 1 \pmod{5}$.
$3^4 = 81$.
$81 \div 5$. Le reste est 1, car $81 = 16 \times 5 + 1$. Donc $81 \equiv 1 \pmod{5}$. Le théorème est vérifié.
b) Pour $p=7$ et $a=2$ :
On doit vérifier si $2^{7-1} \equiv 1 \pmod{7}$, c'est-à-dire $2^6 \equiv 1 \pmod{7}$.
$2^6 = 64$.
$64 \div 7$. Le reste est 1, car $64 = 9 \times 7 + 1$. Donc $64 \equiv 1 \pmod{7}$. Le théorème est vérifié.
c) Calcul de $3^{10} \pmod{11}$ en utilisant le petit théorème de Fermat :
Ici, $p=11$ est un nombre premier. L'entier $a=3$ n'est pas divisible par 11.
D'après le petit théorème de Fermat, $3^{11-1} \equiv 1 \pmod{11}$, donc $3^{10} \equiv 1 \pmod{11}$.
Le reste de la division euclidienne de $3^{10}$ par 11 est 1.
Théorème : Le petit théorème de Fermat est un résultat clé pour simplifier les calculs impliquant de grandes puissances dans le contexte de l'arithmétique modulaire, notamment avec des modules premiers.
Exercice 4 : Fonction de compte des nombres premiers $\pi(x)$
La fonction $\pi(x)$ compte le nombre de nombres premiers inférieurs ou égaux à $x$.
a) Calcule $\pi(10)$.
b) Calcule $\pi(20)$.
c) Calcule $\pi(30)$.
d) Donne une approximation de $\pi(100)$ en utilisant l'approximation $\pi(x) \approx x / \ln(x)$.
Correction :
a) Les nombres premiers inférieurs ou égaux à 10 sont : 2, 3, 5, 7. Donc, $\pi(10) = 4$.
b) Les nombres premiers inférieurs ou égaux à 20 sont : 2, 3, 5, 7, 11, 13, 17, 19. Donc, $\pi(20) = 8$.
c) Les nombres premiers inférieurs ou égaux à 30 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Donc, $\pi(30) = 10$.
d) Approximation de $\pi(100)$ :
On utilise la formule $\pi(x) \approx x / \ln(x)$.
Pour $x=100$, $\pi(100) \approx 100 / \ln(100)$.
$\ln(100) = \ln(10^2) = 2 \ln(10)$. En utilisant $\ln(10) \approx 2.302585$, on a $\ln(100) \approx 2 \times 2.302585 = 4.60517$.
$\pi(100) \approx 100 / 4.60517 \approx 21.71$.
La valeur exacte de $\pi(100)$ est 25. L'approximation est raisonnable pour des grands nombres, mais pas toujours précise pour des nombres plus petits.
Théorème : Le théorème des nombres premiers stipule que $\lim_{x \to \infty} \frac{\pi(x)}{x/\ln(x)} = 1$. Cela signifie que $x/\ln(x)$ est une bonne approximation de $\pi(x)$ pour $x$ grand.
Exercice 5 : Conjecture de Goldbach
La conjecture de Goldbach, non prouvée à ce jour, affirme que tout nombre entier pair supérieur à 2 peut être écrit comme la somme de deux nombres premiers.
a) Vérifie la conjecture de Goldbach pour les nombres pairs suivants : 10, 12, 18, 24.
b) Trouve un contre-exemple si la conjecture était fausse.
c) Pourquoi est-il difficile de prouver cette conjecture ?
Correction :
a) Vérification de la conjecture :
Pour 10 : $10 = 3 + 7$ (3 et 7 sont premiers).
Pour 12 : $12 = 5 + 7$ (5 et 7 sont premiers).
Pour 18 : $18 = 5 + 13$ (5 et 13 sont premiers) ou $18 = 7 + 11$.
Pour 24 : $24 = 5 + 19$ (5 et 19 sont premiers) ou $24 = 7 + 17$ ou $24 = 11 + 13$.
b) Contre-exemple :
Si un contre-exemple existait, ce serait un nombre pair (supérieur à 2) qui ne pourrait pas être exprimé comme la somme de deux nombres premiers. Aucun tel nombre n'a été trouvé malgré des recherches intensives.
c) Difficulté de la preuve :
La difficulté réside dans la nature "irrégulière" de la distribution des nombres premiers. Bien qu'il existe des tendances globales (comme le théorème des nombres premiers), les petites et moyennes échelles montrent des irrégularités qui rendent difficile de garantir qu'il n'y aura jamais un nombre pair qui échappe à la règle. Prouver une propriété pour "tous" les nombres pairs demande une compréhension parfaite du comportement des nombres premiers à toutes les échelles, ce que nous n'avons pas encore.
Conjecture : La conjecture de Goldbach est l'un des problèmes les plus célèbres et les plus anciens en mathématiques. Elle a été vérifiée pour un nombre extrêmement grand d'entiers pairs, mais une preuve formelle fait toujours défaut.
Exercice 6 : Théorème des Nombres Premiers (Approximation de la densité)
Le théorème des nombres premiers (TNP) donne une approximation de la densité des nombres premiers. La probabilité qu'un grand nombre aléatoire soit premier est approximativement $1/\ln(x)$.
a) Calcule cette probabilité approximative pour $x=1000$.
b) Compare le résultat obtenu à la valeur réelle de $\pi(1000)$.
Correction :
a) Probabilité approximative pour $x=1000$ :
La probabilité est $1/\ln(1000)$.
$\ln(1000) = \ln(10^3) = 3 \ln(10) \approx 3 \times 2.302585 = 6.907755$.
Probabilité $\approx 1 / 6.907755 \approx 0.14477$.
Cela signifie qu'environ 14.5% des nombres autour de 1000 seraient premiers.
b) Comparaison avec la valeur réelle de $\pi(1000)$ :
La valeur exacte de $\pi(1000)$ est 168.
L'approximation du TNP donne $\pi(1000) \approx 1000 / \ln(1000) \approx 1000 / 6.907755 \approx 144.77$.
La valeur calculée (144.77) est proche de la valeur réelle (168). L'approximation $x/\ln(x)$ est une première étape. Une meilleure approximation est donnée par la fonction intégrale logarithmique $Li(x)$.
Théorème : Le théorème des nombres premiers établit la répartition asymptotique des nombres premiers.
Exercice 7 : Recherche de nombres premiers jumeaux
Les nombres premiers jumeaux sont des paires de nombres premiers qui diffèrent de 2 (par exemple, 3 et 5, 11 et 13).
a) Trouve les trois prochaines paires de nombres premiers jumeaux après (11, 13).
b) Formule une conjecture sur la distribution des nombres premiers jumeaux.
Correction :
a) Trois prochaines paires de nombres premiers jumeaux après (11, 13) :
Vérifions les nombres consécutifs de premiers :
Les premiers après 13 sont : 17, 19. Donc (17, 19) est une paire de nombres premiers jumeaux.
Les premiers après 19 sont : 23, 29, 31. Donc (29, 31) est une paire de nombres premiers jumeaux.
Les premiers après 31 sont : 37, 41, 43. Donc (41, 43) est une paire de nombres premiers jumeaux.
Les trois prochaines paires sont donc (17, 19), (29, 31), (41, 43).
b) Conjecture sur la distribution des nombres premiers jumeaux :
Il semble qu'il y ait une infinité de nombres premiers jumeaux. C'est la "conjecture des nombres premiers jumeaux", qui est également non prouvée.
De plus, l'écart entre les nombres premiers jumeaux semble augmenter globalement, mais ils continuent d'apparaître, bien que peut-être moins fréquemment à mesure que les nombres deviennent plus grands.
Conjecture : La conjecture des nombres premiers jumeaux est un autre problème majeur en théorie des nombres qui est non résolu.
Exercice 8 : Facteurs premiers et algorithme de Pollard's rho
L'algorithme de Pollard's rho est un algorithme probabiliste de factorisation de grands nombres composés. Il utilise une fonction itérative pour trouver des facteurs.
Soit $n=21$. Utilise une fonction simple comme $f(x) = x^2 + 1 \pmod{21}$ pour trouver un facteur premier de $n$. Commence avec $x_0 = 2$.
Calcule la suite $x_i$ et les valeurs $\text{pgcd}(|x_i - x_{2i}|, n)$.
Correction :
Nous avons $n=21$. La fonction est $f(x) = x^2 + 1 \pmod{21}$. On commence avec $x_0 = 2$.
On calcule la suite $x_i = f(x_{i-1})$ et on cherche $\text{pgcd}(|x_i - x_{2i}|, n)$.
Calculons les premiers termes de la suite :
$x_0 = 2$.
$x_1 = f(x_0) = f(2) = 2^2 + 1 \pmod{21} = 4 + 1 \pmod{21} = 5$.
$x_2 = f(x_1) = f(5) = 5^2 + 1 \pmod{21} = 25 + 1 \pmod{21} = 26 \pmod{21} = 5$.
Nous avons trouvé un cycle : $x_1 = 5$ et $x_2 = 5$. La suite devient stationnaire rapidement.
L'algorithme de Pollard's rho cherche un cycle dans la suite modulo un facteur premier de $n$. Ici, les termes deviennent identiques trop vite.
Le principe est de trouver $i$ et $j$ avec $i \neq j$ tels que $x_i \equiv x_j \pmod{p}$ pour un facteur premier $p$ de $n$. Cela implique $\text{pgcd}(|x_i - x_j|, n) > 1$.
Ici, $x_1 = 5$ et $x_2 = 5$. Donc $x_1 \equiv x_2 \pmod{21}$. Le pgcd sera $\text{pgcd}(|5-5|, 21) = \text{pgcd}(0, 21) = 21$. Cela ne nous donne pas un facteur propre.
Ce choix de fonction $f(x)$ et de $x_0$ n'est pas optimal pour $n=21$.
Essayons avec une autre fonction, par exemple $g(x) = x^2 - 1 \pmod{21}$ et $x_0=2$.
$x_0 = 2$.
$x_1 = g(2) = 2^2 - 1 \pmod{21} = 3$.
$x_2 = g(3) = 3^2 - 1 \pmod{21} = 8$.
$x_3 = g(8) = 8^2 - 1 \pmod{21} = 64 - 1 \pmod{21} = 63 \pmod{21} = 0$.
$x_4 = g(0) = 0^2 - 1 \pmod{21} = -1 \pmod{21} = 20$.
$x_5 = g(20) = 20^2 - 1 \pmod{21} = (-1)^2 - 1 \pmod{21} = 1 - 1 = 0$.
On a un cycle $0, 20$. Voyons les pgcd :
Cherchons $i, j$ tels que $x_i \equiv x_j \pmod p$.
Si on prend $x_0=2, x_1=3, x_2=8, x_3=0, x_4=20, x_5=0$.
Nous avons $x_3 \equiv x_5 \pmod{21}$ ($0 \equiv 0$). Le pgcd est $\text{pgcd}(|0-0|, 21) = 21$.
Il faut tester à chaque étape $\text{pgcd}(|x_i - x_{2i}|, n)$.
Pour $x_0 = 2$, $f(x) = x^2+1 \pmod{21}$: $x_0=2$. $x_1=5$. $x_2=5$. Cycle très court. Le facteur trouvé est 21.
Pour $x_0 = 2$, $g(x) = x^2-1 \pmod{21}$: $x_0=2$. $x_1=3$. $x_2=8$. $x_3=0$. $x_4=20$. $x_5=0$. Cycle $0, 20$.
Ici, on peut faire une recherche plus directe :
Pour $i=1, j=2$: $\text{pgcd}(|x_1-x_2|, 21) = \text{pgcd}(|3-8|, 21) = \text{pgcd}(5, 21) = 1$.
Pour $i=1, j=3$: $\text{pgcd}(|3-0|, 21) = \text{pgcd}(3, 21) = 3$. On a trouvé un facteur !
Le facteur premier est 3.
Algorithme : L'algorithme de Pollard's rho est efficace pour trouver de petits facteurs premiers de grands nombres composés, mais il n'est pas garanti de succès en un temps fini, et le choix de la fonction et du point de départ peut influencer la performance.
Exercice 9 : Théorème de Wilson
Le théorème de Wilson stipule que pour un entier $p > 1$, $p$ est un nombre premier si et seulement si $(p-1)! \equiv -1 \pmod{p}$.
a) Vérifie ce théorème pour $p=5$ (qui est premier).
b) Vérifie ce théorème pour $p=6$ (qui est composé).
c) Utilise ce théorème pour déterminer si 13 est premier.
Correction :
a) Pour $p=5$ (premier) :
On doit calculer $(5-1)! \pmod{5}$, c'est-à-dire $4! \pmod{5}$.
$4! = 4 \times 3 \times 2 \times 1 = 24$.
$24 \pmod{5}$. $24 = 4 \times 5 + 4$. Donc $24 \equiv 4 \pmod{5}$.
Le théorème dit $(p-1)! \equiv -1 \pmod{p}$. Ici, $-1 \pmod{5}$ est $5-1=4$.
On a bien $4! \equiv 4 \equiv -1 \pmod{5}$. Le théorème est vérifié pour $p=5$.
b) Pour $p=6$ (composé) :
On doit calculer $(6-1)! \pmod{6}$, c'est-à-dire $5! \pmod{6}$.
$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.
$120 \pmod{6}$. $120 = 20 \times 6 + 0$. Donc $120 \equiv 0 \pmod{6}$.
Le théorème dit que pour un nombre composé $p>4$, $(p-1)! \equiv 0 \pmod{p}$. Ici, $0 \not\equiv -1 \pmod{6}$. Le théorème est vérifié (dans le sens où il ne donne pas -1).
c) Utilisation du théorème pour déterminer si 13 est premier :
On doit calculer $(13-1)! \pmod{13}$, c'est-à-dire $12! \pmod{13}$.
Si $12! \equiv -1 \pmod{13}$, alors 13 est premier.
Calculons $12! \pmod{13}$ :
Par le théorème de Wilson, comme 13 est premier, on doit avoir $12! \equiv -1 \pmod{13}$.
$-1 \pmod{13}$ est $13-1 = 12$.
Donc, $12! \equiv 12 \pmod{13}$.
Le théorème de Wilson nous dit que si ce résultat est $-1 \pmod{p}$, alors $p$ est premier. Puisque $12 \equiv -1 \pmod{13}$, 13 est un nombre premier.
Théorème : Le théorème de Wilson fournit un critère nécessaire et suffisant pour qu'un entier soit premier, bien que son application directe pour tester la primalité de grands nombres soit inefficace en raison du calcul du factoriel.
Exercice 10 : Approximation de Legendre et distribution des premiers
Une formule plus ancienne pour l'approximation de $\pi(x)$ est celle de Legendre : $\pi(x) \approx \frac{x}{\ln(x) - 1.08366}$.
a) Calcule cette approximation pour $x=1000$.
b) Compare-la avec l'approximation $x/\ln(x)$ et la valeur réelle $\pi(1000)=168$.
Correction :
a) Approximation de Legendre pour $x=1000$ :
On a $\ln(1000) \approx 6.907755$.
$\pi(1000) \approx 1000 / (\ln(1000) - 1.08366)$
$\pi(1000) \approx 1000 / (6.907755 - 1.08366) = 1000 / 5.824095 \approx 171.70$.
b) Comparaison :
Approximation $x/\ln(x)$ : environ 144.77.
Approximation de Legendre : environ 171.70.
Valeur réelle $\pi(1000) = 168$.
L'approximation de Legendre (171.70) est plus proche de la valeur réelle (168) que l'approximation simple $x/\ln(x)$ (144.77) pour $x=1000$. Cela montre que des formules plus sophistiquées donnent de meilleurs résultats.
Amélioration : L'approximation de Legendre est une amélioration de celle du Théorème des Nombres Premiers. La fonction intégrale logarithmique $Li(x)$ est encore plus précise.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy t'accompagne dans ta découverte et ta maîtrise de la théorie des nombres :
- Accès à une collection complète d'exercices corrigés sur les nombres premiers et autres sujets fondamentaux.
- Des explications détaillées pour chaque étape, facilitant la compréhension des concepts abstraits.
- Des outils d'IA pour t'aider à visualiser les distributions et à comprendre les preuves complexes.
- Un environnement d'apprentissage interactif pour te motiver et te permettre de progresser à ton rythme.