p∈ℕ, p≥2 est PREMIER si ses seuls diviseurs positifs sont 1 et p.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …
Tests de primalité :
Pour tester si n est premier : essayer les diviseurs ≤√n
(Si aucun ne divise n, alors n est premier)
Exemple : 97 premier ?
√97≈9,8 → tester 2,3,5,7 → aucun ne divise 97 → premier ✓
Infinité des nombres premiers (Euclide)
ThéorèmeIl existe une infinité de nombres premiers.
DÉMONSTRATION PAR L'ABSURDE :
Supponsons qu'il n'y en ait qu'un nombre fini : p₁,…,pₙ
Poser N = p₁×p₂×…×pₙ + 1
• N>pᵢ pour tout i → N n'est pas dans la liste
• Soit q un facteur premier de N
• q ne peut être aucun des pᵢ (sinon q|N et q|p₁…pₙ → q|1, impossible)
• CONTRADICTION : il existe un premier hors de la liste.
⚡ Cette preuve d'Euclide date d'environ 300 av. J.-C. C'est l'une des plus belles preuves de mathématiques.
Théorème fondamental de l'arithmétique (TFA)
ThéorèmeTout entier n≥2 s'écrit de manière UNIQUE comme produit de nombres premiers :
n = p₁^α₁ × p₂^α₂ × … × pₖ^αₖ
(p₁<p₂<…<pₖ premiers, αᵢ≥1)
Exemples :
360 = 2³×3²×5
1001 = 7×11×13
NOMBRE DE DIVISEURS :
Si n=p₁^α₁×…×pₖ^αₖ : nb de diviseurs = (α₁+1)(α₂+1)…(αₖ+1)