Les nombres premiers sont les « atomes » des entiers : tout entier s’écrit de façon unique comme produit de nombres premiers. Ils sont infinis, et le petit théorème de Fermat révèle une régularité étonnante de leurs puissances, à la base de méthodes de chiffrement modernes.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Reconnaître un nombre premier et tester la primalité d’un entier
- Démontrer qu’il existe une infinité de nombres premiers
- Décomposer un entier en produit de facteurs premiers et l’exploiter
- Utiliser le petit théorème de Fermat pour calculer des restes
1. Nombres premiers
Nombre premier : Un entier naturel p est premier s’il admet exactement deux diviseurs positifs : 1 et p. Ainsi 1 n’est pas premier ; 2 est le seul nombre premier pair.
- Tout entier n ≥ 2 admet au moins un diviseur premier.
- Test de primalité : si n ≥ 2 n’a aucun diviseur premier p tel que p² ≤ n, alors n est premier.
- Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.
221 est-il premier ?
- √221 ≈ 14,9 : on teste 2, 3, 5, 7, 11, 13.
- 221 = 13 × 17.
221 n’est pas premier.
2. Une infinité de nombres premiers
Démonstration (Euclide)
- Supposons qu’il n’y ait qu’un nombre fini de nombres premiers p₁, p₂, …, pₙ.
- Posons N = p₁ × p₂ × … × pₙ + 1. N ≥ 2 a un diviseur premier p, qui est l’un des pₖ.
- pₖ divise N et le produit p₁ × … × pₙ, donc il divise leur différence 1 : absurde.
Il existe une infinité de nombres premiers.
3. Décomposition en facteurs premiers
Tout entier n ≥ 2 se décompose en produit de nombres premiers, et cette décomposition est unique à l’ordre près : n = p₁α₁ × p₂α₂ × … × pₖαₖ.
- 360 = 2³ × 3² × 5.
- Nombre de diviseurs positifs de n : (α₁ + 1)(α₂ + 1)…(αₖ + 1). Pour 360 : 4 × 3 × 2 = 24.
- PGCD : produit des facteurs communs avec le plus petit exposant.
4. Petit théorème de Fermat
Reste de 52026 dans la division par 11
- 11 est premier et ne divise pas 5 : 5¹⁰ ≡ 1 [11].
- 2026 = 10 × 202 + 6, donc 52026 ≡ 5⁶ [11].
- 5² = 25 ≡ 3, donc 5⁶ ≡ 3³ = 27 ≡ 5 [11].
Le reste est 5.
À retenir
- Un nombre premier a exactement deux diviseurs positifs ; 1 n’est pas premier.
- Pour tester n, on cherche un diviseur premier p avec p² ≤ n.
- Il existe une infinité de nombres premiers ; la décomposition en facteurs premiers est unique.
- Fermat : p premier ne divisant pas a ⟹ ap−1 ≡ 1 [p].
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.