Leçon 121 — Nombres premiers. Applications.

Points clés

• Infinité des premiers
• Décomposition unique
• Théorème de Dirichlet (énoncé)
• Répartition des premiers
• Tests de primalité

Plan

1. Définition et propriétés fondamentales
   • Nombre premier : [formule] dont les seuls diviseurs sont [formule] et [formule]
   • Lemme d'Euclide : si [formule], alors [formule] ou [formule]
   • Théorème fondamental de l'arithmétique
2. Infinité des nombres premiers
   • Preuve d'Euclide
   • Preuve par la divergence de [formule]
   • Preuve topologique de Furstenberg
3. Répartition des nombres premiers
   • Fonction de comptage [formule]
   • Encadrement de Tchebychev : [formule]
   • Théorème des nombres premiers (énoncé) : [formule]
4. Premiers dans les progressions arithmétiques
   • Théorème de Dirichlet (énoncé)
   • Cas particuliers démontrables : [formule], [formule]
   • Utilisation des polynômes cyclotomiques
5. Tests de primalité et factorisation
   • Test naïf : divisibilité par les premiers [formule]
   • Test de Fermat et nombres de Carmichael
   • Test de Miller-Rabin
6. Applications
   • Cryptographie RSA
   • Petit théorème de Fermat
   • Crible d'Ératosthène

Théorèmes clés

• Théorème fondamental de l'arithmétique : tout entier [formule] s'écrit de manière unique en produit de premiers
• Infinité des premiers (Euclide) : l'ensemble des nombres premiers est infini
• Encadrement de Tchebychev : [formule] pour [formule] assez grand
• Théorème de Dirichlet : pour [formule], il existe une infinité de premiers [formule]

Exemples importants

• Infinité des premiers [formule] par argument de parité
• Les nombres de Mersenne [formule]
• Les nombres de Fermat [formule]
• Identité d'Euler : [formule] pour [formule]
• [formule] est un nombre de Carmichael

Erreurs courantes

• Croire que [formule] est toujours premier dans la preuve d'Euclide
• Confondre le théorème des nombres premiers avec un encadrement explicite
• Affirmer que le test de Fermat est un test de primalité

Conseils du jury

• Connaître plusieurs preuves de l'infinité des premiers montre une bonne culture
• Le résultat de Tchebychev est un bon développement
• Le jury apprécie le lien entre [formule] et la répartition des premiers

Développements associés

• Infinitude des nombres premiers
• Constructibilité des polygones réguliers
• Polynômes cyclotomiques
• Irréductibilité des polynômes cyclotomiques
• Somme de deux carrés
• Critère d'Eisenstein
• Existence et unicité des corps finis
• Entiers de Gauss
• Polygones réguliers et Gauss
• Loi de réciprocité quadratique
• Algorithme RSA

Prérequis

arithmetique z