PGCD, théorèmes de Bézout et de Gauss, nombres premiers

Comment simplifier une fraction à coup sûr ? Comment savoir si l’équation $5x + 7y = 4$ a des solutions entières — et toutes les trouver ? Pourquoi les nombres premiers sont-ils au cœur du chiffrement de tes données ? Ce chapitre rassemble les grands théorèmes de l’arithmétique : trois noms à retenir — Euclide, Bézout, Gauss — et un invité de marque, Fermat.

Le PGCD et l’algorithme d’Euclide

Le PGCD de deux entiers $a$ et $b$ (non tous deux nuls) est le plus grand diviseur commun à $a$ et $b$. Le calculer par la liste des diviseurs est vite pénible : l’algorithme d’Euclide fait mieux, grâce à la propriété clé — si $a = bq + r$ est la division euclidienne de $a$ par $b$, alors :

$\operatorname{pgcd}(a\,;\,b) = \operatorname{pgcd}(b\,;\,r)$

On divise, on remplace, on recommence : le PGCD est le dernier reste non nul. Exemple avec $252$ et $198$ :

$252 = 198 \times 1 + 54 \qquad 198 = 54 \times 3 + 36 \qquad 54 = 36 \times 1 + 18 \qquad 36 = 18 \times 2 + 0$

donc $\operatorname{pgcd}(252\,;\,198) = 18$. Application immédiate : $\dfrac{252}{198} = \dfrac{14}{11}$ après division par $18$ — la fraction est devenue irréductible.

Entiers premiers entre eux et théorème de Bézout

Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$ : leurs seuls diviseurs communs sont $1$ et $-1$. (Attention : premiers entre eux ne veut pas dire premiers ! $15$ et $28$ ne sont pas premiers, mais ils sont premiers entre eux.)

Pour trouver un couple $(u\,;\,v)$, on « remonte » l’algorithme d’Euclide (algorithme d’Euclide étendu). Exemple avec $17$ et $5$ : $17 = 5 \times 3 + 2$ puis $5 = 2 \times 2 + 1$. En partant de la fin :

$1 = 5 - 2 \times 2 = 5 - 2 \times (17 - 3 \times 5) = 7 \times 5 - 2 \times 17$

Vérification : $35 - 34 = 1$ ✓. Application majeure : si $\operatorname{pgcd}(a\,;\,n) = 1$, l’égalité $au + nv = 1$ donne $au \equiv 1 \pmod n$ — le nombre $u$ est un inverse de $a$ modulo $n$, l’outil qui résout les congruences $ax \equiv b \pmod n$ en multipliant les deux membres par $u$.

Le théorème de Gauss

Deux conséquences à connaître : si $a$ et $b$ sont premiers entre eux et divisent tous deux $c$, alors $ab \mid c$ ; et si un nombre premier $p$ divise un produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$.

Résoudre une équation diophantienne ax + by = c

Une équation diophantienne est une équation dont on cherche les solutions entières. Pour $ax + by = c$ :

• Existence : il y a des solutions si, et seulement si, $\operatorname{pgcd}(a\,;\,b)$ divise $c$. Ainsi $6x + 4y = 5$ n’a aucune solution entière ($2 \nmid 5$).
• Méthode complète sur $5x + 7y = 4$ : Bézout donne $5 \times 3 + 7 \times (-2) = 1$, donc en multipliant par $4$ : $(x_0\,;\,y_0) = (12\,;\,-8)$ est une solution particulière. Si $(x\,;\,y)$ est une autre solution, la soustraction des deux égalités donne $5(x - 12) = -7(y + 8)$. Comme $7$ divise $5(x - 12)$ et est premier avec $5$, le théorème de Gauss donne $7 \mid x - 12$, d’où $x = 12 + 7k$ puis $y = -8 - 5k$. Réciproquement, tous ces couples conviennent :

$\mathcal{S} = \{(12 + 7k\,;\,-8 - 5k),\ k \in \mathbb{Z}\}$

Les nombres premiers

Un entier $p \geq 2$ est premier s’il n’a que deux diviseurs positifs : $1$ et lui-même. Les premiers : $2, 3, 5, 7, 11, 13, \ldots$ — et la liste ne s’arrête jamais : l’ensemble des nombres premiers est infini. (Démonstration éclair : si $p_1, \ldots, p_n$ étaient les seuls, le nombre $N = p_1 p_2 \cdots p_n + 1$ aurait un diviseur premier, nécessairement différent de tous les $p_i$ — puisque la division de $N$ par chaque $p_i$ laisse le reste $1$. Contradiction.)

• Tester la primalité de $n$ : il suffit d’essayer les diviseurs premiers jusqu’à $\sqrt{n}$. Exemple : $223$ n’est divisible ni par $2$, ni par $3$, ni par $5$, ni par $7$, ni par $11$, ni par $13$, et $15^2 = 225 > 223$ : donc $223$ est premier. (Le crible d’Ératosthène industrialise l’idée pour lister tous les premiers jusqu’à un seuil.)
• Décomposition en facteurs premiers : tout entier $n \geq 2$ s’écrit comme produit de facteurs premiers, et cette écriture est unique à l’ordre près. Exemple : $360 = 2^3 \times 3^2 \times 5$. On y lit les diviseurs, et le PGCD de deux nombres s’obtient en prenant les facteurs communs avec le plus petit exposant.

Le petit théorème de Fermat

Exemple : $11$ est premier et ne divise pas $2$, donc $2^{10} \equiv 1 \pmod{11}$ — sans calculer $1\,024$. Pour un exposant énorme, on fait la division euclidienne de l’exposant par $p - 1$ et on conclut comme au chapitre des congruences.

Application : déchiffrer un message

Le chiffrement affine code chaque lettre (numérotée $x$ de $0$ à $25$) par le reste de $ax + b$ modulo $26$. Pour déchiffrer, il faut « diviser par $a$ » modulo $26$, c’est-à-dire multiplier par un inverse de $a$ modulo $26$ — il existe exactement quand $\text{pgcd}(a\,;\,26) = 1$, et c’est la remontée de l’algorithme d’Euclide (Bézout) qui le fournit. Exemple : l’inverse de $3$ modulo $26$ est $9$, car $3 \times 9 = 27 \equiv 1 \pmod{26}$. C’est le principe de base des problèmes de chiffrement du programme.

Les pièges classiques