Cours et exercices corrigés de terminale : Théorèmes de Bézout et de Gauss, nombres premiers et chiffrement RSA

1. Théorèmes de Bézout et de Gauss

• Théorème de Bézout : Deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe $(u, v) \in \mathbb{Z}^2$ tel que $au + bv = 1$.
• Théorème de Gauss : Soient $a, b, c \in \mathbb{Z}$. Si $a \mid bc$ et si $\text{PGCD}(a, b) = 1$, alors $a \mid c$.

2. Petit théorème de Fermat et cryptographie RSA

• Petit théorème de Fermat : Si $p$ est premier et si $p \nmid a$, alors $a^{p-1} \equiv 1 \pmod{p}$. Conséquence : pour tout entier $a$, $a^p \equiv a \pmod{p}$.
• Chiffrement RSA (problème d'approfondissement) : repose sur la difficulté algorithmique de factoriser un très grand entier $N = pq$ (produit de deux nombres premiers géants).

3. PGCD et algorithme d'Euclide

• Le PGCD de deux entiers $a$ et $b$ non tous deux nuls est le plus grand diviseur commun à $a$ et $b$. $a$ et $b$ sont premiers entre eux si $\text{PGCD}(a, b) = 1$.
• Propriété clé : si $a = bq + r$, alors $\text{PGCD}(a, b) = \text{PGCD}(b, r)$. L'algorithme d'Euclide enchaîne les divisions euclidiennes ; le PGCD est le dernier reste non nul.
• Les diviseurs communs à $a$ et $b$ sont exactement les diviseurs de leur PGCD, et il existe des entiers $u$, $v$ tels que $au + bv = \text{PGCD}(a, b)$.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

4. Conséquences du théorème de Gauss

• Si $a \mid n$, $b \mid n$ et $\text{PGCD}(a, b) = 1$, alors $ab \mid n$. Exemple : un entier divisible par $4$ et par $9$ est divisible par $36$.
• Si un nombre premier $p$ divise un produit $ab$, alors $p \mid a$ ou $p \mid b$.
• Solutions de $ax + by = c$ (avec $\text{PGCD}(a, b) = 1$) : si $(x_0, y_0)$ est une solution particulière, toutes les solutions sont $x = x_0 - bk$, $y = y_0 + ak$, $k \in \mathbb{Z}$.

5. Nombres premiers

• Un entier $p \ge 2$ est premier s'il admet exactement deux diviseurs positifs : $1$ et $p$. ($1$ n'est pas premier.)
• Test : si $n \ge 2$ n'est divisible par aucun nombre premier $p$ tel que $p^2 \le n$, alors $n$ est premier.
• Il existe une infinité de nombres premiers (démonstration rédigée ci-dessous).
• Décomposition : tout entier $n \ge 2$ s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers. Exemple : $360 = 2^3 \times 3^2 \times 5$.
• RSA miniature : $p = 5$, $q = 11$, $n = 55$, $(p - 1)(q - 1) = 40$ ; clé publique $e = 3$, clé privée $d = 27$ car $3 \times 27 = 81 \equiv 1 \pmod{40}$. Le message $m = 2$ est chiffré en $2^3 = 8$, et $8^{27} \equiv 2 \pmod{55}$ le déchiffre.

6. Démonstration : le PGCD s'écrit $au + bv$ (théorème de Bézout)

Soient $a$ et $b$ deux entiers non tous deux nuls, et $E$ l'ensemble des entiers strictement positifs de la forme $au + bv$ avec $u, v \in \mathbb{Z}$.

• $E$ est non vide (il contient $a^2 + b^2 = a \times a + b \times b > 0$) : il admet donc un plus petit élément $d = au_0 + bv_0$.
• $d$ divise $a$ : on écrit $a = dq + r$ avec $0 \le r < d$. Alors $r = a - dq = a(1 - qu_0) + b(-qv_0)$ est de la forme $au + bv$. Si l'on avait $r > 0$, $r$ serait un élément de $E$ plus petit que $d$ : impossible. Donc $r = 0$ et $d \mid a$. De même, $d \mid b$.
• $d$ est le plus grand des diviseurs communs : tout diviseur commun $c$ de $a$ et $b$ divise $au_0 + bv_0 = d$, donc $c \le d$.

Ainsi $\text{PGCD}(a, b) = au_0 + bv_0$.
Théorème de Bézout : si $\text{PGCD}(a, b) = 1$, on obtient $au + bv = 1$. Réciproquement, si $au + bv = 1$, tout diviseur commun positif de $a$ et $b$ divise $1$, donc $\text{PGCD}(a, b) = 1$.

7. Démonstration : théorème de Gauss

Hypothèses : $a \mid bc$ et $\text{PGCD}(a, b) = 1$.

• D'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + bv = 1$.
• En multipliant par $c$ : $acu + bcv = c$.
• $a$ divise $acu$, et $a$ divise $bcv$ car $a \mid bc$. Donc $a$ divise la somme $acu + bcv$, c'est-à-dire $c$.

8. Démonstration : l'ensemble des nombres premiers est infini

• Lemme : tout entier $N \ge 2$ admet au moins un diviseur premier. En effet, le plus petit diviseur $p \ge 2$ de $N$ est premier : s'il avait un diviseur $d$ avec $1 < d < p$, ce $d$ diviserait aussi $N$ et serait plus petit que $p$.
• Raisonnement par l'absurde : supposons qu'il n'y ait qu'un nombre fini de nombres premiers $p_1, p_2, \dots, p_k$, et posons $N = p_1 \times p_2 \times \dots \times p_k + 1 \ge 3$.
• D'après le lemme, $N$ admet un diviseur premier, qui est donc l'un des $p_i$. Ce $p_i$ divise $N$ et le produit $p_1 \times \dots \times p_k$, donc il divise leur différence $1$ : c'est impossible car $p_i \ge 2$.
• Conclusion : il existe une infinité de nombres premiers.

9. Pour aller plus loin : une démonstration du petit théorème de Fermat

Soit $p$ premier et $a$ un entier non divisible par $p$ (donc premier avec $p$).

• Les $p - 1$ entiers $a, 2a, \dots, (p-1)a$ ont des restes modulo $p$ non nuls (si $p \mid ka$, Gauss donne $p \mid k$, impossible pour $1 \le k \le p - 1$) et deux à deux distincts : si $ka \equiv k'a \pmod{p}$, alors $p \mid (k - k')a$, donc $p \mid k - k'$, d'où $k = k'$ puisque $|k - k'| < p$.
• Leurs restes sont donc exactement $1, 2, \dots, p - 1$, dans un certain ordre. En multipliant : $a \times 2a \times \dots \times (p-1)a \equiv 1 \times 2 \times \dots \times (p-1) \pmod{p}$, soit $(p-1)!\,a^{p-1} \equiv (p-1)! \pmod{p}$.
• $p$ divise donc $(p-1)!\,(a^{p-1} - 1)$ et $p$ est premier avec $(p-1)!$ (aucun facteur n'est divisible par $p$) : d'après Gauss, $p \mid a^{p-1} - 1$, c'est-à-dire $a^{p-1} \equiv 1 \pmod{p}$.

10. Algorithmes : couple de Bézout, crible d'Ératosthène, décomposition en facteurs premiers

def bezout(a, b):
    # renvoie (d, u, v) avec d = PGCD(a, b) = a*u + b*v
    u0, v0, u1, v1 = 1, 0, 0, 1
    while b != 0:
        q = a // b
        a, b = b, a - q * b
        u0, u1 = u1, u0 - q * u1
        v0, v1 = v1, v0 - q * v1
    return a, u0, v0

def crible(n):
    est_premier = [True] * (n + 1)
    est_premier[0] = False
    est_premier[1] = False
    for p in range(2, n + 1):
        if p * p > n:
            break
        if est_premier[p]:
            for m in range(p * p, n + 1, p):
                est_premier[m] = False
    return [k for k in range(n + 1) if est_premier[k]]

def decomposition(n):
    facteurs = []
    p = 2
    while n > 1:
        while n % p == 0:
            facteurs.append(p)
            n = n // p
        p = p + 1
    return facteurs

bezout(37, 13) renvoie (1, 6, -17), crible(30) renvoie [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] et decomposition(360) renvoie [2, 2, 2, 3, 3, 5].