Nombres premiers et petit théorème de Fermat
Nombres premiers, infinité, crible d'Ératosthène et test de primalité, décomposition en produit de facteurs premiers, nombre de diviseurs, petit théorème de Fermat et principe du chiffrement RSA.
1. Nombres premiers
Définition · Nombre premier
Un entier naturel $p \geq 2$ est premier s'il a exactement deux diviseurs positifs : $1$ et lui-même. $1$ n'est pas premier.
Propriété · Test de primalité
Si $n \geq 2$ n'est divisible par aucun nombre premier $p$ tel que $p^2 \leq n$, alors $n$ est premier. Exemple : $97$ n'est divisible ni par $2$, ni $3$, ni $5$, ni $7$ (et $11^2 > 97$) : il est premier.
Propriété · Infinité des nombres premiers (Euclide)
Il existe une infinité de nombres premiers. Preuve : si $p_1, \ldots, p_k$ étaient tous les nombres premiers, $N = p_1 p_2 \cdots p_k + 1$ aurait un diviseur premier, qui diviserait aussi $p_1 \cdots p_k$, donc $1$ : absurde.
2. Décomposition en facteurs premiers
Propriété · Théorème fondamental
Tout entier $n \geq 2$ s'écrit de façon unique (à l'ordre près) comme un produit de nombres premiers : $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$. Il a alors $(\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_k + 1)$ diviseurs positifs.
Exemple · 360
$360 = 2^3 \times 3^2 \times 5$ : il a $(3 + 1)(2 + 1)(1 + 1) = 24$ diviseurs.
Propriété · Lemme d'Euclide
Si un nombre premier $p$ divise un produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$.
3. Petit théorème de Fermat
Propriété · Petit théorème de Fermat
Si $p$ est premier et si $a$ n'est pas divisible par $p$, alors $a^{p - 1} \equiv 1\ [p]$. Pour tout entier $a$ : $a^p \equiv a\ [p]$.
Méthode · Reste d'une puissance avec Fermat
$13$ est premier : $2^{12} \equiv 1\ [13]$. Comme $100 = 12 \times 8 + 4$, $2^{100} \equiv 2^4 = 16 \equiv 3\ [13]$.
Attention · Le chiffrement RSA
Il repose sur deux grands nombres premiers $p$ et $q$ : on publie $n = pq$, mais retrouver $p$ et $q$ à partir de $n$ est extrêmement long. Le déchiffrement fonctionne grâce au théorème de Fermat.
S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
97 est-il premier ?
★☆☆Montrer que $97$ est premier.
221
★☆☆$221$ est-il premier ?
Décomposition de 360
★☆☆Décomposer $360$ en facteurs premiers et donner son nombre de diviseurs.
1001
★☆☆Décomposer $1001$ en facteurs premiers.
PGCD et PPCM par décomposition
★★☆Calculer $\mathrm{PGCD}(360\,;\,84)$ et $\mathrm{PPCM}(360\,;\,84)$ à l'aide des décompositions.
Carré parfait
★★☆Quel est le plus petit entier $n \geq 1$ tel que $360n$ soit un carré parfait ?
Fermat : 2¹?? modulo 13
★★☆Déterminer le reste de $2^{100}$ dans la division par $13$.
Fermat : 3²?²? modulo 7
★★☆Déterminer le reste de $3^{2026}$ dans la division par $7$.
n? ? n
★★☆Montrer que $n^7 - n$ est divisible par $7$ pour tout entier $n$.
n? ? n divisible par 30
★★★Montrer que $n^5 - n$ est divisible par $30$.
Crible
★☆☆Lister les nombres premiers inférieurs à $50$.
Infinité des premiers
★★★Rédiger la démonstration d'Euclide de l'infinité des nombres premiers.
Nombre de Mersenne
★★☆$2^{11} - 1 = 2047$ est-il premier ?
Nombre parfait
★☆☆Vérifier que $28$ est égal à la somme de ses diviseurs stricts.
p² ? 1 divisible par 24
★★★Soit $p$ un nombre premier supérieur à $3$. Montrer que $24$ divise $p^2 - 1$.
Test de primalité en Python
★★☆Écrire une fonction Python est_premier(n) qui teste les diviseurs jusqu'à $\sqrt{n}$.
Mini-RSA
★★★On prend $n = 33 = 3 \times 11$, $e = 3$ et $d = 7$. Chiffrer le message $m = 4$ par $c \equiv m^e\ [33]$, puis vérifier que $c^d \equiv m\ [33]$.
Diviseurs de 2? × 3²
★☆☆Combien $2^4 \times 3^2$ a-t-il de diviseurs positifs ?
999 999 et 7
★★☆Montrer que $999\,999$ est divisible par $7$ à l'aide du petit théorème de Fermat.
Lemme d'Euclide
★★☆Soit $p$ premier. Montrer que si $p$ divise $n^2$, alors $p$ divise $n$.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.