Ch10 — Nombres premiers — Maths Expertes

Sommaire

10.1. Définitions et premiers résultats
10.2. Infinité des nombres premiers
10.3. Décomposition en facteurs premiers
10.4. Crible d’Ératosthène
10.5. Petit théorème de Fermat
10.6. Ordre multiplicatif et théorème d’Euler (complément)
10.7. Résultats remarquables (admis)
10.8. Activités Python
📋 Bilan — Formules essentielles
⚠️ Pièges et contre-exemples

La sécurité de ton téléphone

Le protocole RSA, qui protège tes communications numériques, repose sur l’impossibilité pratique de factoriser de grands entiers. On choisit deux nombres premiers $p$ et $q$ d’environ 150 chiffres chacun, et leur produit $n = pq$ constitue la clé publique.

Une mise en œuvre concrète est proposée en activité Python 6 (RSA), en s'appuyant sur le petit théorème de Fermat et l'inverse modulaire.

Combien de nombres faudrait-il tester pour factoriser un entier à 300 chiffres ? Si un ordinateur teste $10^{12}$ diviseurs par seconde, combien d’années cela prendrait-il ?

Eratosthène, Euclide, Ibn al-Haytham et Al-Farisi

Ératosthène (IIIe siècle av. J.-C.) invente son célèbre crible et calcule la circonférence de la Terre avec une précision remarquable. Euclide (Éléments IX, proposition 20) prouve l’infinité des nombres premiers par l’absurde — une démonstration d’une élégance intemporelle.

Ibn al-Haytham (Xe–XIe siècle) conjecture un résultat lié au théorème de Wilson. Al-Farisi (XIIIe siècle) donne une nouvelle démonstration originale de l’infinité des premiers, témoignant de la vitalité de la recherche mathématique islamique en théorie des nombres.

Sophie Germain (1776–1831), correspondant sous pseudonyme masculin avec Gauss et Legendre, apporte des contributions majeures à la théorie des nombres. Les « nombres premiers de Sophie Germain » ($p$ premier tel que $2p+1$ aussi) jouent un rôle central dans sa démonstration partielle du dernier théorème de Fermat — la plus grande avancée sur ce problème pendant près d’un siècle.

📜 Ératosthène et Euclide : le crible et l’infini → 📜 Ibn al-Haytham et Al-Farisi : les secrets des nombres → 📜 Sophie Germain : la mathématicienne qui signait d’un nom d’homme →

La preuve d’Euclide revisitée

Démontrer qu’il n’existe pas de plus grand nombre premier : supposer que $p_1, p_2, \ldots, p_n$ sont tous les nombres premiers et considérer $N = p_1 \times p_2 \times \cdots \times p_n + 1$.

Pourquoi $N$ ne peut-il être divisible par aucun des $p_i$ ? Qu’implique cela pour la liste supposée complète des premiers ?

→ Solution complète en fin de chapitre

10.1. Définitions et premiers résultats

Définition — Nombre premier

Un entier $p \ge 2$ est premier s’il n’admet pas d’autre diviseur positif que 1 et lui-même.

Un entier $n \ge 2$ non premier est dit composé.

Par convention, 1 n’est ni premier ni composé.

Exemples

Premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …

Composés : $4 = 2^2$, $6 = 2\times3$, $15=3\times5$, $100=2^2\times5^2$.

2 est le seul nombre premier pair.

Lemme — Diviseur premier

Tout entier $n \ge 2$ admet au moins un diviseur premier.

Démonstration

Soit $E$ l’ensemble des diviseurs de $n$ strictement supérieurs à 1. $E$ est non vide (il contient $n$). Par le bon ordre de $\mathbb{N}$, $E$ admet un plus petit élément $p$.

Montrons que $p$ est premier. Si $p$ avait un diviseur $d$ avec $1 < d < p$, alors $d$ diviserait aussi $n$ (par transitivité) et serait dans $E$, contredisant la minimalité de $p$. Donc $p$ est premier. ∎

Méthode — Tester la primalité de n

Pour vérifier si $n$ est premier, il suffit de tester ses diviseurs jusqu’à $\sqrt{n}$.

En effet, si $n = ab$ avec $a \le b$, alors $a \le \sqrt{n}$.

Exemple — 97 est-il premier ?

$\sqrt{97} < 10$. On teste 2, 3, 5, 7 : aucun ne divise 97. Donc 97 est premier.

10.2. Infinité des nombres premiers

Théorème d’Euclide — Infinité des premiers

Il existe une infinité de nombres premiers.

Démonstration (par l’absurde)

Supposons qu’il n’existe qu’un nombre fini de premiers : $p_1, p_2, \ldots, p_k$.

Considérons l’entier $N = p_1 \cdot p_2 \cdots p_k + 1$.

Par le lemme précédent, $N$ admet un diviseur premier $p$. Ce premier $p$ doit figurer dans la liste, soit $p = p_i$ pour un certain $i$. Alors $p \mid N$ et $p \mid p_1\cdots p_k$, donc $p \mid N - p_1\cdots p_k = 1$. Impossible.

Contradiction : la liste ne peut pas être finie. ∎

⚠️ Piège fréquent à éviter

La preuve ne montre pas que $N = p_1\cdots p_k + 1$ est lui-même premier. Elle montre seulement que $N$ admet un diviseur premier nouveau (différent de tous les $p_i$), ce qui suffit pour la contradiction.

Contre-exemple : $2\times3\times5\times7\times11\times13+1 = 30\,031 = 59\times 509$ — composé, mais ses deux facteurs premiers (59 et 509) sont nouveaux.

10.3. Décomposition en facteurs premiers

Lemme d’Euclide

Soit $p$ un nombre premier et $a, b$ deux entiers. Si $p \mid ab$, alors $p \mid a$ ou $p \mid b$.

Démonstration (à partir du lemme de Gauss du chapitre 9)

Supposons $p \mid ab$ et $p \nmid a$. Comme $p$ est premier, ses seuls diviseurs positifs sont $1$ et $p$. Puisque $p \nmid a$, on a nécessairement $\pgcd(p,a) = 1$.

Le lemme de Gauss (chapitre 9) appliqué à $p \mid ab$ avec $\pgcd(p,a)=1$ donne alors $p \mid b$. ∎

Généralisation

Par récurrence sur le nombre de facteurs : si $p$ est premier et $p \mid a_1 a_2 \cdots a_k$, alors $p$ divise au moins l’un des $a_i$.

Théorème fondamental de l’arithmétique

Tout entier $n \ge 2$ s’écrit de façon unique (à l’ordre des facteurs près) comme produit de nombres premiers :

$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$

avec $p_1 < p_2 < \cdots < p_k$ premiers et $\alpha_i \ge 1$.

Démonstration

Existence (par récurrence forte sur $n$).

Pour $n=2$ : $2$ est premier. Supposons le résultat vrai pour tout entier $2 \le m < n$.

Si $n$ est premier, c’est bon. Sinon, $n = ab$ avec $2 \le a, b < n$. Par hypothèse de récurrence, $a$ et $b$ se décomposent en premiers. Le produit donne une décomposition de $n$. ∎

Unicité (par le lemme d’Euclide).

Supposons que $n$ admette deux décompositions : $$n = p_1^{\alpha_1}\cdots p_k^{\alpha_k} = q_1^{\beta_1}\cdots q_l^{\beta_l}$$ avec $p_1 < \cdots < p_k$ et $q_1 < \cdots < q_l$ premiers, et tous les exposants $\alpha_i, \beta_j \ge 1$.

1. Les plus petits premiers coïncident : $p_1 = q_1$.
$p_1$ divise $n$, donc $p_1 \mid q_1^{\beta_1}\cdots q_l^{\beta_l}$. Par le lemme d’Euclide généralisé, $p_1$ divise au moins l’un des $q_j$. Comme $q_j$ est premier et $p_1 \ge 2$, cette divisibilité force $p_1 = q_j$. Le même argument appliqué à $q_1$ montre que $q_1 = p_i$ pour un certain $i$. Mais les deux listes sont rangées par ordre strictement croissant et désignent le plus petit diviseur premier de $n$ : ce plus petit diviseur premier est unique, donc $p_1 = q_1$.

2. Simplification. Comme $p_1 = q_1$, on peut diviser les deux membres par $p_1$ : $$p_1^{\alpha_1 - 1} \cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k} = q_1^{\beta_1 - 1} \cdot q_2^{\beta_2}\cdots q_l^{\beta_l}.$$ On obtient une nouvelle égalité entre produits de premiers, mais portant sur un entier strictement plus petit que $n$ (l’entier $n / p_1$).

3. Conclusion sans récurrence formelle. On répète le procédé : à chaque étape, on identifie le plus petit premier des deux décompositions — qui est forcément le même par l’argument de l’étape 1 — et on simplifie par ce premier. Le processus consomme un facteur de chaque côté à chaque étape, et il s’arrête lorsque l’un des deux membres vaut $1$. Or un produit de nombres premiers tous $\ge 2$ ne vaut $1$ que si aucun facteur ne reste : les deux membres atteignent donc $1$ simultanément. C’est dire que les deux décompositions épuisent leurs facteurs au même rythme, donc $k = l$ et chaque $p_i = q_i$ avec $\alpha_i = \beta_i$. ∎

Exemples de décompositions

$360 = 2^3 \times 3^2 \times 5$
$1001 = 7 \times 11 \times 13$
$2^{10} = 1024$, $2026 = 2 \times 1013$ (1013 est premier)

Propriété — PGCD et PPCM par décomposition

Si $a = \prod p_i^{\alpha_i}$ et $b = \prod p_i^{\beta_i}$ (avec $\alpha_i, \beta_i \ge 0$), alors :

$\pgcd(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}, \qquad \ppcm(a,b) = \prod p_i^{\max(\alpha_i,\beta_i)}$

Démonstration

Notons $d = \prod p_i^{\min(\alpha_i,\beta_i)}$. Alors $d \mid a$ et $d \mid b$ (car $\min \le \alpha_i$ et $\min \le \beta_i$). Si $e \mid a$ et $e \mid b$, alors pour chaque premier $p_i$ la valuation de $e$ en $p_i$ est $\le \alpha_i$ et $\le \beta_i$, donc $\le \min(\alpha_i,\beta_i)$, soit $e \mid d$. Ainsi $d$ est bien le plus grand diviseur commun. Le raisonnement est dual pour le PPCM. ∎

Propriété — Relation PGCD × PPCM

Pour tous entiers naturels non nuls $a$ et $b$ :

$\pgcd(a,b) \times \ppcm(a,b) = a \times b$

Démonstration

Posons $a = \prod p_i^{\alpha_i}$ et $b = \prod p_i^{\beta_i}$.

Alors $\pgcd(a,b) \times \ppcm(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)} \times \prod p_i^{\max(\alpha_i,\beta_i)} = \prod p_i^{\min(\alpha_i,\beta_i) + \max(\alpha_i,\beta_i)}$.

Or pour tous réels $x, y$ : $\min(x,y) + \max(x,y) = x + y$.

Donc $\pgcd(a,b) \times \ppcm(a,b) = \prod p_i^{\alpha_i + \beta_i} = \prod p_i^{\alpha_i} \times \prod p_i^{\beta_i} = a \times b$. ∎

Conséquence pratique

On peut calculer le PPCM à partir du PGCD : $\ppcm(a,b) = \dfrac{a \times b}{\pgcd(a,b)}$.

C’est souvent plus rapide que de passer par la décomposition en facteurs premiers.

Exemple

$360 = 2^3\times3^2\times5^1$ et $756 = 2^2\times3^3\times7^1$.

$\pgcd = 2^{\min(3,2)}\times3^{\min(2,3)}\times5^{\min(1,0)}\times7^{\min(0,1)} = 2^2\times3^2 = 36$.

$\ppcm = 2^3\times3^3\times5\times7 = 7560$.

Vérification : $\pgcd \times \ppcm = 36 \times 7560 = 272\,160 = 360 \times 756$ ✓

10.4. Crible d’Ératosthène

Méthode — Crible d’Ératosthène

Pour trouver tous les premiers jusqu’à $N$ :

Écrire tous les entiers de 2 à $N$.
Le plus petit non barré est premier. Barrer tous ses multiples (sauf lui-même).
Répéter jusqu’à avoir traité tous les entiers jusqu’à $\sqrt{N}$.
Les entiers non barrés sont exactement les premiers jusqu’à $N$.

Il suffit de traiter jusqu’à $\sqrt{N}$ car tout composé $\le N$ a un facteur premier $\le \sqrt{N}$.

Exemple — Premiers jusqu’à 30

On élimine les multiples de 2, puis de 3, puis de 5 ($\sqrt{30} < 6$).

Premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Activités interactives — Crible en ligne

Applique le crible d’Ératosthène en cliquant sur les nombres :

Crible 0–50 Crible 0–100 Crible 0–200 Crible 0–1000

10.5. Petit théorème de Fermat

Petit théorème de Fermat

Soit $p$ un nombre premier et $a$ un entier. Alors :

Forme 1 : $a^p \equiv a \pmod{p}$ (valable pour tout $a \in \mathbb{Z}$).
Forme 2 : si $p$ ne divise pas $a$ (i.e. $\pgcd(a, p) = 1$), alors $a^{p-1} \equiv 1 \pmod{p}$.

Démonstration

Étape 1 — Lemme. Pour $p$ premier et $1 \leqslant k \leqslant p-1$, on a $p \mid \binom{p}{k}$.

En effet, $\binom{p}{k} = \dfrac{p!}{k!(p-k)!}$, donc $k!(p-k)!\,\binom{p}{k} = p!$. Comme $p$ divise $p!$, il divise le membre de gauche. Or les facteurs de $k! = 1\cdot 2\cdots k$ et $(p-k)! = 1\cdot 2\cdots(p-k)$ sont tous strictement inférieurs à $p$ : aucun n’est divisible par le premier $p$, donc $\pgcd(p,\,k!(p-k)!)=1$. Par le lemme de Gauss (chapitre 9, section 9.3), on conclut $p \mid \binom{p}{k}$.

Étape 2 — Forme 1 par récurrence sur $a \in \mathbb{N}$.

Initialisation ($a = 0$) : $0^p = 0 \equiv 0 \pmod{p}$. ✓

Hérédité. Supposons $a^p \equiv a \pmod{p}$. Par la formule du binôme :

$(a+1)^p = a^p + \sum_{k=1}^{p-1}\binom{p}{k}a^k + 1.$

Par l’étape 1, chaque terme $\binom{p}{k}a^k$ ($1 \leqslant k \leqslant p-1$) est divisible par $p$, donc :

$(a+1)^p \equiv a^p + 1 \equiv a + 1 \pmod{p}.$

Par récurrence, la propriété est vraie pour tout $a \in \mathbb{N}$.

Extension à $a \in \mathbb{Z}$. Si $a < 0$, on pose $a = -b$ avec $b \in \mathbb{N}$. Alors $a^p = (-b)^p = (-1)^p b^p$.

Cas $p$ impair : $(-1)^p = -1$, donc $a^p = -b^p$. Par la version pour $b \in \mathbb{N}$ : $b^p \equiv b \pmod p$, d'où $a^p \equiv -b = a \pmod p$. ✓
Cas $p = 2$ : on a $a^2 = b^2$. Par la version pour $b \in \mathbb{N}$ appliquée à $b$ : $b^2 \equiv b \pmod 2$. De plus, $2b \equiv 0 \pmod 2$ donne $-b \equiv b \pmod 2$. En combinant : $a^2 = b^2 \equiv b \equiv -b = a \pmod 2$. ✓

Étape 3 — Passage à la forme 2. Si $p \nmid a$, alors $\pgcd(a, p) = 1$. L’égalité $a^p \equiv a \pmod{p}$ s’écrit $p \mid a^p - a = a(a^{p-1} - 1)$. Par le lemme de Gauss ($p$ premier avec $a$), on en déduit $p \mid a^{p-1} - 1$, soit $a^{p-1} \equiv 1 \pmod{p}$. $\square$

Exemples

$p = 5$, $a = 2$ : $2^4 = 16 = 3 \times 5 + 1$, donc $2^4 \equiv 1 \pmod 5$. ✓
$p = 7$, $a = 3$ : $3^6 = 729 = 104 \times 7 + 1$, donc $3^6 \equiv 1 \pmod 7$. ✓
Calcul de $2^{100} \bmod 7$ : par Fermat, $2^6 \equiv 1 \pmod 7$. Or $100 = 6 \times 16 + 4$, donc $2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1 \cdot 16 \equiv 2 \pmod 7$.

Méthode — Calculer $a^n \bmod p$ avec Fermat

Vérifier que $p$ est premier et que $p \nmid a$.
Réduire l’exposant modulo $p-1$ : écrire $n = (p-1)q + r$ avec $0 \leqslant r < p-1$.
Alors $a^n = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod{p}$.
Calculer $a^r \bmod p$ à la main (exposant petit).

Attention — La réciproque est fausse

Si $a^{n-1} \equiv 1 \pmod{n}$ pour un $a$ premier avec $n$, on ne peut pas conclure que $n$ est premier. Les entiers composés vérifiant $a^{n-1} \equiv 1 \pmod n$ pour tout $a$ premier avec $n$ s’appellent nombres de Carmichael (le plus petit est $561 = 3 \times 11 \times 17$). Le test de primalité de Fermat est donc un test probabiliste, pas une caractérisation.

Application — Cryptographie RSA

Le théorème d’Euler (généralisation du petit théorème de Fermat via l’indicatrice $\varphi$, section 10.6) est à la base du chiffrement RSA : pour un module composé $n=pq$, c’est l’égalité $a^{\varphi(n)}\equiv 1\pmod n$ qui rend possible le déchiffrement. Voir l’activité 6 (Cryptographie RSA) en fin de chapitre.

10.6. Ordre multiplicatif et théorème d’Euler (complément)

⚠ Hors programme officiel BO 2020. Cette section est un complément de culture mathématique et n’est pas exigible au baccalauréat. Elle généralise le petit théorème de Fermat à un module non premier, et fournit le cadre théorique de RSA (activité 6).

Dans cette section, on s’intéresse aux entiers $a$ inversibles modulo $n$ (c’est-à-dire $\pgcd(a, n) = 1$). On cherche quelle est la plus petite puissance $a^k$ qui redonne 1 modulo $n$ — un nombre qui contrôle la périodicité des puissances de $a$ modulo $n$.

Définition — Indicatrice d’Euler $\varphi(n)$

Pour $n \geq 1$, on note $\varphi(n)$ le nombre d’entiers $k$ de l’intervalle $\{1, 2, \ldots, n\}$ qui sont premiers avec $n$ (c’est-à-dire $\pgcd(k, n) = 1$).

La fonction $\varphi$ s’appelle l'indicatrice d’Euler.

Exemples

$\varphi(1) = 1$, $\varphi(2) = 1$, $\varphi(3) = 2$, $\varphi(4) = 2$, $\varphi(5) = 4$, $\varphi(6) = 2$, $\varphi(12) = 4$.

Propriété — Indicatrice d'Euler de $p$ premier et de $pq$

Si $p$ est premier, alors tous les entiers de $1$ à $p-1$ sont premiers avec $p$, donc $\boxed{\varphi(p) = p - 1}$.
Si $p$ et $q$ sont deux premiers distincts, alors $\boxed{\varphi(pq) = (p-1)(q-1)}$. (Formule fondamentale pour le chiffrement RSA, voir Activité 6.)

Définition — Ordre multiplicatif

Soit $n \geq 2$ et $a$ un entier avec $\pgcd(a, n) = 1$. L'ordre (multiplicatif) de $a$ modulo $n$ est le plus petit entier $k > 0$ tel que :

$a^k \equiv 1 \pmod{n}.$

On le note $\text{ord}_n(a)$. Si $\pgcd(a, n) \neq 1$, l’ordre n’est pas défini (aucune puissance de $a$ ne donne 1 modulo $n$).

Exemple — Ordre de 2 modulo 7

On calcule les puissances successives de 2 modulo 7 :

$2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 8 \equiv 1 \pmod{7}.$

Donc $\text{ord}_7(2) = 3$. Les puissances de 2 modulo 7 sont périodiques de période 3 : $2, 4, 1, 2, 4, 1, \ldots$

Théorème d’Euler

Soit $n \geq 2$ et $a$ un entier avec $\pgcd(a, n) = 1$. Alors :

$a^{\varphi(n)} \equiv 1 \pmod{n}.$

Conséquence — l’ordre divise $\varphi(n)$

Si $\pgcd(a, n) = 1$, alors $\text{ord}_n(a)$ divise $\varphi(n)$. (C’est une conséquence du théorème d’Euler et d’une division euclidienne sur les exposants.)

En particulier, pour connaître l’ordre, il suffit de tester les diviseurs de $\varphi(n)$.

Cas particulier — Petit théorème de Fermat

Si $p$ est un nombre premier, alors $\varphi(p) = p - 1$. Le théorème d’Euler donne donc, pour tout $a$ non multiple de $p$ :

$a^{p-1} \equiv 1 \pmod{p}.$

C’est le petit théorème de Fermat démontré de façon autonome en section 10.5.

Méthode — Calculer l’ordre de $a$ modulo $n$

Vérifier que $\pgcd(a, n) = 1$ (sinon l’ordre n’est pas défini).
Calculer $\varphi(n)$.
Tester successivement $a^d \bmod n$ pour chaque diviseur $d$ de $\varphi(n)$, en commençant par le plus petit.
Le premier $d$ tel que $a^d \equiv 1 \pmod{n}$ est l’ordre $\text{ord}_n(a)$.

Exemple : pour $a = 3, n = 7$, on a $\varphi(7) = 6$, diviseurs de 6 : 1, 2, 3, 6. On calcule $3^1 = 3$, $3^2 = 9 \equiv 2$, $3^3 \equiv 6$, $3^6 \equiv 1$. Donc $\text{ord}_7(3) = 6$.

10.7. Résultats remarquables (admis)

Théorème des nombres premiers (Hadamard–de la Vallée-Poussin, 1896)

Notons $\pi(x)$ le nombre de premiers $\le x$. Alors :

$\pi(x) \sim \dfrac{x}{\ln x} \quad (x \to +\infty)$

Par exemple $\pi(10^6) = 78\,498$ et $\frac{10^6}{\ln 10^6} \approx 72\,382$ (erreur ~8%).

Démonstration — admis (hors programme lycée)

Résultat admis. La démonstration rigoureuse, obtenue indépendamment par Jacques Hadamard et Charles-Jean de la Vallée Poussin en 1896, repose sur l’étude analytique de la fonction zêta de Riemann $\zeta(s)$. Elle utilise des outils de variable complexe (théorème des résidus, analyticité de $\zeta$ dans un demi-plan, non-annulation sur la droite $\mathrm{Re}(s) = 1$) qui dépassent totalement le lycée.

Histoire. La conjecture remonte à Legendre (1798) et Gauss (1792-1793, à l’âge de 15 ans, qui constate numériquement que $\pi(x) \approx x/\ln x$). Riemann donne en 1859 le cadre théorique. Il faut attendre près de 40 ans pour qu’Hadamard et de la Vallée Poussin achèvent la preuve.

Démonstration « élémentaire ». Erdős et Selberg ont trouvé en 1948 une preuve ne faisant intervenir que des outils élémentaires (pas d’analyse complexe), mais qui reste longue et technique. ∎

Théorème de Dirichlet (1837)

Si $\pgcd(a,b)=1$, la suite arithmétique $(a + nb)_{n\ge0}$ contient une infinité de nombres premiers.

Par exemple, parmi $1, 5, 9, 13, 17, 21, \ldots$ (suite $1+4n$), il y a une infinité de premiers.

Démonstration — admis (hors programme lycée)

Résultat admis. Dirichlet (1837) démontre ce résultat en introduisant les caractères de Dirichlet et les fonctions L (généralisations de la fonction zêta). La preuve utilise des outils d’analyse (séries, produits infinis, analyticité) inaccessibles au lycée.

Idée directrice. Dirichlet montre que la série $\sum_p \dfrac{1}{p}$ (somme des inverses des premiers dans la progression $a + nb$) est divergente. Ceci entraîne qu’il y a une infinité de tels premiers (car une somme finie serait convergente).

Cas particulier élémentaire. Pour certains cas simples (par exemple $4n+3$ ou $4n+1$), on peut donner une preuve directe inspirée de celle d’Euclide. Exemple : pour $4n+3$, on suppose qu’il n’y a qu’un nombre fini $p_1, \ldots, p_k$ et on considère $N = 4 p_1 \cdots p_k - 1$. Alors $N \equiv 3 \pmod{4}$ et tout diviseur premier impair de $N$ est congru à $1$ ou $3$ modulo $4$ ; comme $N$ est impair et $\equiv 3\pmod 4$, au moins un facteur premier $p \equiv 3 \pmod 4$. Mais $p$ ne peut être aucun des $p_i$ (car $p \mid 4 p_1 \cdots p_k - 1$ imposerait $p \mid 1$), contradiction. ∎

Hors programme — Conjecture de Riemann

Riemann définit en 1859 la fonction $\zeta(s) = \sum_{n=1}^{+\infty} \frac{1}{n^s}$ (pour $s \in \mathbb{C}$ avec $\mathrm{Re}(s) > 1$) et montre que la distribution des nombres premiers est liée aux zéros de $\zeta$.

La conjecture affirme que tous les zéros non triviaux vérifient $\mathrm{Re}(s) = \frac{1}{2}$. Elle reste non prouvée à ce jour, malgré la vérification numérique pour les $10^{13}$ premiers zéros.

10.8. Activités Python

Activité 1 — Tests de primalité

Écrire une fonction est_premier(n) qui teste si $n$ est premier par divisions successives.

Traiter les cas particuliers : $n < 2$ (non premier), $n = 2$ (premier), $n$ pair (non premier).
Tester la divisibilité par les impairs de 3 a $\sqrt{n}$.
Tester la fonction sur 2, 3, 4, 17, 97, 100, 1013, 1001, 10007.
Lister tous les nombres premiers jusqu’a 200 et compter combien il y en a.

Rappel Python : i * i <= n est plus efficace que i <= n**0.5. Listes en compréhension : [n for n in range(2, 200) if condition].

Voir la solution

Activité 2 — Crible d’Ératosthène

Implémenter le crible d’Ératosthène et vérifier le théorème des nombres premiers.

Écrire une fonction crible(N) qui retourne la liste de tous les nombres premiers $\leqslant N$.
Utiliser un tableau de booléens : initialiser tout a True, puis rayer les multiples de chaque premier $p$ a partir de $p^2$.
Vérifier que $\pi(1000) = 168$ (nombre de premiers jusqu’a 1000).
Comparer $\pi(x)$ avec l’approximation $x / \ln(x)$ pour $x = 100, 1000, 10\,000, 100\,000$.

Rappel Python : [True] * (N+1) crée une liste de booléens. range(p*p, N+1, p) pour les multiples de $p$. math.log(x) pour $\ln(x)$.

Voir la solution

Activité 3 — Décomposition en facteurs premiers

Écrire une fonction factorisation(n) qui décompose $n$ en produit de facteurs premiers.

La fonction retourne un dictionnaire {p: exposant} (ex: {2: 3, 3: 2, 5: 1} pour 360).
Algorithme : diviser $n$ par $d = 2, 3, 4, \ldots$ tant que $d^2 \leqslant n$. Si $n > 1$ a la fin, $n$ est un facteur premier.
Écrire une fonction afficher_facto(n) pour un affichage lisible (ex: $360 = 2^3 \times 3^2 \times 5$).
Calculer le PGCD de 360 et 756 en comparant leurs factorisations.

Rappel Python : n //= d pour la division entière en place. dict.get(key, 0) retourne 0 si la clé est absente.

Voir la solution

def factorisation(n):
    """Décompose n en facteurs premiers. Retourne un dict {p: exposant}."""
    facteurs = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            facteurs[d] = facteurs.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        facteurs[n] = facteurs.get(n, 0) + 1
    return facteurs

def afficher_facto(n):
    f = factorisation(n)
    parts = [f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(f.items())]
    print(f"{n} = " + " × ".join(parts))

for n in [360, 1001, 2026, 10080, 123456]:
    afficher_facto(n)

print()
# PGCD et PPCM par factorisation
def pgcd_facto(a, b):
    fa, fb = factorisation(a), factorisation(b)
    primes = set(fa) | set(fb)
    return {p: min(fa.get(p,0), fb.get(p,0)) for p in primes if min(fa.get(p,0), fb.get(p,0)) > 0}

fa = factorisation(360)
fb = factorisation(756)
d = pgcd_facto(360, 756)
print(f"pgcd(360, 756) = {dict(sorted(d.items()))} = ", end="")
print(eval('*'.join(f'{p}**{e}' for p,e in d.items())))

Activité 4 — Conjectures célèbres

Explorer trois grandes conjectures sur les nombres premiers.

Conjecture de Goldbach : vérifier que tout entier pair $n \geqslant 4$ s’écrit comme somme de deux premiers, pour $n$ de 4 a 50.
Premiers jumeaux : lister tous les couples $(p, p+2)$ de premiers jumeaux jusqu’a 200.
Nombres de Mersenne : pour $p \in \{2, 3, 5, 7, 11, 13, 17, 19\}$, tester si $2^p - 1$ est premier.

Rappel Python : range(4, 52, 2) pour les pairs. Liste en compréhension avec double condition : [(p, p+2) for p in range(2, 200) if cond1 and cond2].

Voir la solution

Activité 5 — Test de primalité de Miller-Rabin (hors programme)

Implémenter le test probabiliste de Miller-Rabin, bien plus rapide que le test naif pour les grands nombres.

Écrire $n - 1 = 2^r \times d$ avec $d$ impair.
Pour $k$ témoins aléatoires $a$, calculer $a^d \bmod n$ puis élever au carré successivement.
Si aucun témoin ne prouve que $n$ est composé, conclure « probablement premier ».
Tester sur de grands nombres : $2^{31}-1$, $2^{61}-1$, $10^{15}+37$, $10^{15}+39$.
Mesurer le temps d’exécution et comparer avec le test naif.

Rappel Python : random.randrange(2, n-1) pour un entier aléatoire. pow(a, d, n) pour l’exponentiation modulaire. time.time() pour chronométrer.

Voir la solution

import random

def miller_rabin(n, k=10):
    """Test probabiliste de primalité. k = nombre de tours."""
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    # Écrire n-1 = 2^r * d avec d impair
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    # k tours
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Composé avec certitude
    return True  # Probablement premier

# Tester de grands nombres
grands = [2**31 - 1, 2**61 - 1, 10**15 + 37, 10**15 + 39]
print("Test de grands nombres (Miller-Rabin) :")
for n in grands:
    print(f"  {n} : {'probablement premier' if miller_rabin(n) else 'composé'}")

print()
# Comparer la vitesse sur un grand nombre
import time
n = 10**15 + 37
t = time.time()
result = miller_rabin(n, k=20)
print(f"Miller-Rabin sur {n}: {result}, temps: {(time.time()-t)*1000:.2f} ms")

Activité 6 — Cryptographie RSA (implémentation complète)

Implémenter les étapes du chiffrement RSA avec de petits nombres premiers ($p = 61$, $q = 53$) :

Calculer $n = pq$ et l’indicatrice d’Euler $\varphi(n) = (p-1)(q-1)$
Choisir $e = 17$ (premier avec $\varphi(n)$) comme clé publique, puis calculer la clé privée $d = e^{-1} \bmod \varphi(n)$
Chiffrer le message $m = 65$ par $c = m^e \bmod n$, puis déchiffrer par $m = c^d \bmod n$
Vérifier que le message retrouvé est bien $65$

Rappel : la sécurité de RSA repose sur la difficulté de factoriser $n = pq$. pow(m, e, n) calcule $m^e \bmod n$ et pow(e, -1, phi) l’inverse modulaire.

Voir la solution

Activité 7 — Exploration : périodes des congruences

Explorer l'ordre multiplicatif et le petit théorème de Fermat :

Écrire une fonction ordre(a, n) qui renvoie le plus petit $k > 0$ tel que $a^k \equiv 1 \pmod{n}$, ou None si $a$ n’est pas inversible modulo $n$.
Calculer $\text{ord}_7(a)$ pour chaque entier $a \in \{1, 2, \ldots, 6\}$ (les 6 inversibles modulo 7), puis $\text{ord}_{12}(a)$ pour chaque inversible modulo 12.
Vérifier le petit théorème de Fermat : $a^{p-1} \equiv 1 \pmod{p}$ pour $p = 7$ et tout $a \in \{1, \ldots, 6\}$.

Rappel (section 10.6) : l’ordre de $a$ divise toujours $\varphi(n)$ (théorème d’Euler). Pour $p$ premier, $\varphi(p) = p-1$ et l’on retrouve le petit théorème de Fermat.

⭐ Ouverture L’ensemble des inversibles modulo $n$ se note $(\mathbb{Z}/n\mathbb{Z})^*$ et, lorsqu’il est engendré par un seul élément, on parle de groupe cyclique. C’est le cas de $(\mathbb{Z}/7\mathbb{Z})^*$ (cyclique d’ordre 6). Ces notions seront formalisées en classes préparatoires ou en licence de mathématiques (un aperçu est proposé en complément hors programme dans le chapitre 11 du site).

Voir la solution

Activité 8 — Vérification expérimentale du petit théorème de Fermat

Vérifier expérimentalement le petit théorème de Fermat : si $p$ est premier et $1 \leqslant a \leqslant p-1$, alors $a^{p-1} \equiv 1 \pmod{p}$.

Écrire une fonction est_premier(n) (test naif jusqu’a $\sqrt{n}$).
Pour chaque premier $p \in \{5, 7, 11, 13, 17, 23\}$, vérifier que $a^{p-1} \equiv 1$ pour tout $a$ de 1 a $p-1$.
Montrer un contre-exemple : prendre $n = 4$ (non premier) et afficher $a^{n-1} \bmod n$ pour $a = 1, 2, 3$.
Explorer les nombres de Carmichael : vérifier que 561 est composé mais satisfait le test de Fermat pour tout $a$ premier avec 561.

Rappel Python : pow(a, e, n) calcule $a^e \bmod n$ efficacement (exponentiation modulaire). math.gcd(a, n) pour le PGCD.

Voir la solution

def est_premier(n):
    if n < 2: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

# Vérification du petit théorème de Fermat
print("Petit théorème de Fermat (a^(p-1) ≡ 1 mod p) :")
for p in [5, 7, 11, 13, 17, 23]:
    ok = all(pow(a, p-1, p) == 1 for a in range(1, p))
    print(f"  p={p}: {'✓' if ok else '✗'}")

print()
# Contre-exemple : n=4 n'est pas premier
p = 4
print(f"n={p} (non premier) :")
for a in range(1, p):
    print(f"  {a}^{p-1} mod {p} = {pow(a, p-1, p)}", end="")
    if pow(a, p-1, p) != 1:
        print("  ← ≠ 1 !")
    else:
        print()

print()
# Nombres de Carmichael : composés vérifiant quand même a^(n-1)≡1 pour pgcd(a,n)=1
import math
n = 561  # premier nombre de Carmichael
print(f"n={n} = {n} (est_premier={est_premier(n)})")
ok = all(pow(a, n-1, n) == 1 for a in range(1, n) if math.gcd(a, n) == 1)
print(f"a^(n-1) ≡ 1 (mod n) pour tout a premier avec n : {ok}")
print("→ 561 est un nombre de Carmichael (pseudo-premier de Fermat)")

Notion	Définition / Formule	Piège à éviter
Nombre premier	\(p\) est premier ssi \(p \geq 2\) et ses seuls diviseurs positifs sont \(1\) et \(p\)	1 n’est pas premier
Décomposition en facteurs premiers	Tout entier \(n \geq 2\) s’écrit de manière unique comme produit de nombres premiers	L’unicité est à permutation près des facteurs
Petit théorème de Fermat	Si \(p\) premier et \(p \nmid a\), alors \(a^{p-1} \equiv 1 \pmod{p}\)	La réciproque est fausse (nombres de Carmichael)
Infinité des premiers	Il existe une infinité de nombres premiers (Euclide)	La preuve construit \(N = p_1 \cdots p_k + 1\) qui n’est pas forcément premier, mais a un diviseur premier nouveau
Crible d’Ératosthène	Pour tester si \(n\) est premier, il suffit de vérifier les diviseurs jusqu’à \(\sqrt{n}\)	Ne pas oublier de tester aussi 2 (seul premier pair)

Chapitre 10 — Nombres premiers

Sommaire

La sécurité de ton téléphone

Eratosthène, Euclide, Ibn al-Haytham et Al-Farisi

La preuve d’Euclide revisitée

10.1. Définitions et premiers résultats

10.2. Infinité des nombres premiers

10.3. Décomposition en facteurs premiers

10.4. Crible d’Ératosthène

10.5. Petit théorème de Fermat

10.6. Ordre multiplicatif et théorème d’Euler (complément)

10.7. Résultats remarquables (admis)

10.8. Activités Python

Visualisation pas a pas : test de primalite

Bilan — Formules essentielles

Pièges et contre-exemples

🗝️ Escape Game — Le Coffre de l'Archiviste