PGCD, théorèmes de bézout et de Gauss (Terminale)

Q: Comment trouver l'inverse d'un entier modulo n ?

Si a et n sont premiers entre eux, l'algorithme d'Euclide étendu donne au+nv=1, donc au \equiv 1\ [n] : u est un inverse de a modulo n. Par exemple, 7\times 15=105 \equiv 1\ [26].

Ce chapitre d'arithmétique de Terminale maths expertes est consacré au PGCD de deux entiers, calculé par l'algorithme d'Euclide. Tu y découvres l'identité de Bézout, le théorème de Gauss et leurs applications : inverse modulo $n$ , congruences $ax \equiv b\ [n]$ et équations diophantiennes $ax+by=c$ .

Définitions

Le PGCD de deux entiers $a$ et $b$ non tous deux nuls est le plus grand entier qui divise à la fois $a$ et $b$ , noté $\mathrm{PGCD}(a\,;\,b)$ .
Deux entiers $a$ et $b$ sont premiers entre eux lorsque $\mathrm{PGCD}(a\,;\,b)=1$ .
Un inverse de $a$ modulo $n$ est un entier $a'$ tel que $aa' \equiv 1\ [n]$ .
Une équation diophantienne est une équation dont on cherche les solutions entières, comme $ax+by=c$ avec $(x\,;\,y) \in \mathbb{Z}^2$ .

Propriétés

Lemme d'Euclide : si $a=bq+r$ est la division euclidienne de $a$ par $b$ , alors $\mathrm{PGCD}(a\,;\,b)=\mathrm{PGCD}(b\,;\,r)$ ; le PGCD est le dernier reste non nul de l'algorithme d'Euclide.
Théorème de Bézout : $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que $au+bv=1$ .
Théorème de Gauss : si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$ .
$a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.
L'équation $ax+by=c$ admet des solutions entières si et seulement si $\mathrm{PGCD}(a\,;\,b)$ divise $c$ .

Formules à retenir

Identité de Bézout : $au+bv=\mathrm{PGCD}(a\,;\,b)$ pour un couple $(u\,;\,v) \in \mathbb{Z}^2$ .
Si $a$ et $n$ sont premiers entre eux : $ax \equiv b\ [n] \iff x \equiv a'b\ [n]$ , où $a'$ est un inverse de $a$ modulo $n$ .
Si $\mathrm{PGCD}(a\,;\,b)=1$ et $(x_0\,;\,y_0)$ est solution de $ax+by=c$ , les solutions sont $(x_0+bk\,;\,y_0-ak)$ , $k \in \mathbb{Z}$ .
Si $a$ et $b$ sont premiers entre eux et divisent $n$ , alors $ab$ divise $n$ .

Exemple corrigé

Résoudre dans $\mathbb{Z}^2$ l'équation $15x+42y=9$ .

Par l'algorithme d'Euclide, $\mathrm{PGCD}(15\,;\,42)=3$ , et $3$ divise $9$ : il y a des solutions.
On divise par $3$ : $5x+14y=3$ , avec $5$ et $14$ premiers entre eux.
Euclide étendu : $1=3\times 5-14$ , donc $5\times 9+14\times(-3)=3$ : $(9\,;\,-3)$ est une solution particulière.
Par soustraction, $5(x-9)=14(-3-y)$ ; $14$ divise $5(x-9)$ et $\mathrm{PGCD}(14\,;\,5)=1$ , donc par Gauss $x=9+14k$ , puis $y=-3-5k$ .
Réciproquement, $5(9+14k)+14(-3-5k)=3$ : les solutions sont les couples $(9+14k\,;\,-3-5k)$ , $k \in \mathbb{Z}$ .

Ce que tu sauras faire

Savoir calculer le PGCD de deux entiers avec l'algorithme d'Euclide
Savoir démontrer que deux entiers sont premiers entre eux avec le théorème de Bézout
Savoir déterminer un couple de Bézout avec l'algorithme d'Euclide étendu
Savoir appliquer le théorème de Gauss en vérifiant ses hypothèses
Savoir déterminer un inverse de $a$ modulo $n$ et résoudre $ax \equiv b\ [n]$
Savoir résoudre une équation diophantienne $ax+by=c$ dans $\mathbb{Z}^2$

Questions fréquentes

Comment calculer un PGCD rapidement ?

Utilise l'algorithme d'Euclide : tu enchaînes les divisions euclidiennes en remplaçant $(a\,;\,b)$ par $(b\,;\,r)$ . Le PGCD est le dernier reste non nul. Par exemple, $\mathrm{PGCD}(1386\,;\,588)=42$ .

Quelle différence entre le théorème de Bézout et celui de Gauss ?

Le théorème de Bézout caractérise les entiers premiers entre eux : $\mathrm{PGCD}(a\,;\,b)=1$ équivaut à l'existence de $u$ , $v$ avec $au+bv=1$ . Le théorème de Gauss en est une conséquence : si $a$ divise $bc$ et $\mathrm{PGCD}(a\,;\,b)=1$ , alors $a$ divise $c$ .

Comment trouver l'inverse d'un entier modulo $n$ ?

Si $a$ et $n$ sont premiers entre eux, l'algorithme d'Euclide étendu donne $au+nv=1$ , donc $au \equiv 1\ [n]$ : $u$ est un inverse de $a$ modulo $n$ . Par exemple, $7\times 15=105 \equiv 1\ [26]$ .