Les Nombres Premiers
Un nombre premier est un entier naturel supérieur à 1 qui n'est divisible
que par 1 et par lui-même. Les nombres premiers sont les "briques de base" de l'arithmétique.
📐 Définition
Un nombre p > 1 est premier si ses seuls diviseurs sont 1 et p.
Exemples de nombres premiers :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
Note : 1 n'est PAS considéré comme premier
Note : 2 est le seul nombre premier pair
🔢 Premiers 100 Nombres Premiers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541
✅ Tests de Primalité
| Méthode |
Description |
Complexité |
| Division par essais |
Tester divisibilité par tous nombres jusqu'à √n |
O(√n) |
| Crible d'Ératosthène |
Générer tous les premiers jusqu'à n |
O(n log log n) |
| Test de Miller-Rabin |
Test probabiliste rapide |
O(k log³ n) |
| Test AKS |
Premier test déterministe polynomial |
O(log⁶ n) |
🎯 Propriétés des Nombres Premiers
- Infinité : Il existe une infinité de nombres premiers (Euclide, ~300 av. J.-C.)
- Distribution : Les premiers deviennent plus rares en grandissant
- Théorème des nombres premiers : π(n) ≈ n/ln(n) où π(n) = nombre de premiers ≤ n
- Écart : Il peut y avoir des écarts arbitrairement grands entre nombres premiers
- Jumeaux : Premiers jumeaux = premiers qui diffèrent de 2 (ex: 11 et 13)
- Mersenne : Premiers de Mersenne = 2^p - 1 (très grands premiers connus)
🔐 Applications des Nombres Premiers
| Domaine |
Application |
| Cryptographie |
RSA, chiffrement à clé publique |
| Hash tables |
Tailles premières réduisent les collisions |
| Générateurs aléatoires |
PRNG avec modules premiers |
| Codes correcteurs |
Corps de Galois d'ordre premier |
| Musique |
Gammes et harmonies |
| Nature |
Spirales de tournesol, cigales périodiques |
💎 Nombres Premiers Remarquables
Plus petit premier : 2
Seul premier pair : 2
Premiers jumeaux : (3,5), (5,7), (11,13), (17,19), (29,31)...
Premiers de Mersenne : 3, 7, 31, 127, 8191...
Premiers de Fermat : 3, 5, 17, 257, 65537
Plus grand connu (2024) : 2^82589933 - 1 (24 862 048 chiffres)
🧮 Théorèmes Célèbres
- Théorème fondamental de l'arithmétique : Tout entier > 1 a une factorisation première unique
- Petit théorème de Fermat : Si p premier et a non divisible par p, alors a^(p-1) ≡ 1 (mod p)
- Théorème de Wilson : p est premier ⟺ (p-1)! ≡ -1 (mod p)
- Conjecture de Goldbach : Tout entier pair > 2 est somme de deux premiers (non prouvée)
- Hypothèse de Riemann : Liée à la distribution des nombres premiers (problème du millénaire)
🌟 Records et Curiosités
| Record |
Valeur |
| Plus grand premier connu |
2^82589933 - 1 (premier de Mersenne) |
| Prix pour trouver un premier > 100M de chiffres |
150 000$ (GIMPS project) |
| Nombre de premiers < 1 000 000 |
78 498 |
| Écart premier le plus grand connu |
> 10^18 |