ℂ Option Mathématiques expertes Terminale Générale · Chapitre 6

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.

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
Crible d'Ératosthène : on barre les multiples de 2, 3, 5 et 7 (car √50 < 8). Restent les 15 nombres premiers inférieurs à 50.

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.

⚠️ Une erreur dans ce cours ? Signalez-la

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.

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.