PGCD, théorèmes de Bézout et de Gauss
Cours
1. PGCD
Le PGCD (plus grand commun diviseur) de deux entiers $a$ et $b$ non tous deux nuls est le plus grand entier qui divise à la fois $a$ et $b$, noté $\text{pgcd}(a,b)$.
2. Algorithme d'Euclide
Il repose sur la propriété $\text{pgcd}(a,b) = \text{pgcd}(b, r)$ où $r$ est le reste de la division euclidienne de $a$ par $b$. On répète jusqu'à obtenir un reste nul : le PGCD est le dernier reste non nul.
Exemple
$\text{pgcd}(48,18)$ : $48 = 18\times2+12$, $18=12\times1+6$, $12=6\times2+0$. Donc $\text{pgcd}(48,18)=6$.
3. Nombres premiers entre eux
Deux entiers $a$ et $b$ sont premiers entre eux si $\text{pgcd}(a,b) = 1$.
4. Théorème de Bézout
$a$ et $b$ sont premiers entre eux si et seulement s'il existe $u, v \in \mathbb{Z}$ tels que :
$$au + bv = 1$$
Plus généralement, il existe toujours $u,v$ tels que $au+bv = \text{pgcd}(a,b)$ (on les trouve en remontant l'algorithme d'Euclide).
5. Théorème de Gauss
Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.
6. Équations diophantiennes
Une équation de la forme $ax+by=c$ (inconnues entières) admet des solutions si et seulement si $\text{pgcd}(a,b)$ divise $c$. On trouve une solution particulière avec Bézout, puis toutes les solutions.