Théorème de Bézout et Gauss : PGCD, équations diophantiennes et algorithme d'Euclide

Théorèmes de Bézout et Gauss

Théorème de Bézout

• Identité de Bézout : si $pgcd(a; b) = d$, alors il existe des entiers $u$ et $v$ tels que $au + bv = d$.
• Théorème de Bézout : $a$ et $b$ sont premiers entre eux ($a \wedge b = 1$) si et seulement si $au + bv = 1$.

Théorème de Gauss

• Énoncé : si $a$ divise le produit $bc$ et que $a \wedge b = 1$, alors $a$ divise $c$.
• Conséquence : si $a \wedge b = 1$, $a$ divise $n$ et $b$ divise $n$, alors le produit $ab$ divise $n$.

💡 Astuce : Pour utiliser Gauss, n'oublie jamais de vérifier d'abord que les nombres sont premiers entre eux.

Équations diophantiennes

Méthode de résolution

Résoudre $ax + by = c$ avec $a \wedge b = 1$ :

• Solution particulière : trouver un couple $(x_0; y_0)$ par tâtonnement ou avec l'algorithme d'Euclide.
• Soustraction : soustraire $ax_0 + by_0 = c$ à l'équation pour obtenir $a(x-x_0) = -b(y-y_0)$.
• Gauss : en déduire les solutions générales de la forme $x = -bk + x_0$ et $y = ak + y_0$ ($k \in \mathbb{Z}$).

Exemple appliqué

Exemple : $4x + 7y = 1$.

• Solution particulière : $4(2) + 7(-1) = 1$, donc $(2; -1)$ convient.
• Gauss : $4(x-2) = -7(y+1)$ donne $x = -7k + 2$ et $y = 4k - 1$.

💡 Attention : Si $pgcd(a; b) = d$ ne divise pas $c$, l'équation n'a aucune solution.