PGCD, Bézout et Gauss : cours Terminale

Le PGCD mesure les facteurs communs de deux entiers. L'algorithme d'Euclide le calcule, l'identité de Bézout l'exprime comme combinaison linéaire et le théorème de Gauss transforme une divisibilité de produit.

Ces trois outils forment une chaîne logique. Les utiliser sans vérifier les hypothèses, notamment le caractère premier entre eux, est l'erreur centrale du chapitre.

Table des Matières

Calculer un PGCD par Euclide

Invariance du PGCD

Si $a=bq+r$ , alors $\gcd(a,b)=\gcd(b,r)$ . Les divisions successives se terminent ; le dernier reste non nul est le PGCD.

Les quotients ne sont pas le résultat. Il faut conserver les égalités de division si l'on souhaite remonter ensuite vers des coefficients de Bézout.

Reconnaître des entiers premiers entre eux

Coprimalité

Deux entiers sont premiers entre eux lorsque leur PGCD vaut 1.

Être premiers entre eux ne signifie pas que chacun est premier. Par exemple 8 et 15 sont composés mais n'ont aucun facteur premier commun.

Utiliser Bézout

Théorème de Bézout

Les entiers 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, le PGCD est une combinaison entière de a et b.

En remontant les divisions d'Euclide, on obtient un couple de coefficients. Il n'est pas unique. Cette identité fournit aussi un inverse de a modulo b lorsque les deux entiers sont premiers entre eux.

Appliquer le théorème de Gauss

Divisibilité d’un produit

Si a divise bc et si a est premier avec b, alors a divise c.

L'hypothèse de coprimalité est indispensable. Le théorème sert à simplifier des divisibilités, démontrer l'unicité de fractions réduites ou résoudre certaines équations.

Chaîne des outils arithmétiques — Euclide calcule, Bézout représente et Gauss exploite la coprimalité.

Résoudre une équation diophantienne

Condition d’existence

L'équation $ax+by=c$ admet des solutions entières si et seulement si $\gcd(a,b)$ divise c.

On trouve une solution particulière grâce à Bézout, puis on décrit toutes les solutions avec un paramètre entier. Les contraintes du problème, par exemple la positivité, sont appliquées seulement ensuite.

Si le PGCD vaut d et si $(x_0,y_0)$ est une solution, les autres s'obtiennent en ajoutant un multiple de $b/d$ à x et en retranchant le même multiple de $a/d$ à y. Cette écriture décrit la famille entière sans omission.

Remonter l’algorithme d’Euclide

Les divisions appliquées à 35 et 22 se terminent par $9=2\times4+1$ . En remontant, on obtient $1=8\times22-5\times35$ . Le couple $(-5,8)$ résout donc $35x+22y=1$ . Toutes les solutions sont $x=-5+22k$ et $y=8-35k$ , avec $k\in\mathbb Z$ . Remplacer ces expressions dans l'équation annule les termes en k et redonne 1.

Relire les hypothèses

Erreur fréquente : citer Gauss sans avoir établi que les deux entiers concernés sont premiers entre eux rend la preuve incomplète.

Contrôle utile : remplacer les paramètres trouvés dans l'équation initiale contrôle immédiatement la famille de solutions.

Les congruences préparent ces calculs. La décomposition en facteurs premiers prolonge le PGCD.

Les trois théorèmes et les capacités associées figurent dans le programme officiel de mathématiques expertes en Terminale.