PGCD et théorème de Bézout

Le plus grand commun diviseur de deux entiers a et b non tous deux nuls est le plus grand entier positif qui les divise tous les deux. On le note PGCD(a ; b). Les signes n’interviennent pas : PGCD(a ; b) = PGCD(|a| ; |b|). Pour a non nul, PGCD(a ; 0) = |a|. Deux entiers sont premiers entre eux lorsque leur PGCD vaut 1. Cela ne signifie pas que chacun est premier : 8 et 15 sont premiers entre eux alors qu’ils sont composés.

Si a = bq + r, les diviseurs communs de a et b sont exactement ceux de b et r. Un diviseur commun de a et b divise r = a − bq. Réciproquement, un diviseur commun de b et r divise a = bq + r. Ainsi PGCD(a ; b) = PGCD(b ; r). En répétant les divisions euclidiennes, les restes positifs décroissent strictement ; l’algorithme s’arrête donc. Le dernier reste non nul est le PGCD.

L’algorithme d’Euclide donne une valeur ; la remontée des divisions donne une identité. Si d = PGCD(a ; b), il existe des entiers u et v tels que au + bv = d. Pour comprendre pourquoi, chaque reste se réécrit comme combinaison entière des deux précédents. En remontant jusqu’aux deux nombres de départ, le dernier reste non nul devient une combinaison de a et b. Cette démarche constructive est plus utile qu’une formule à mémoriser.

Le théorème de Bézout affirme en particulier que a et b sont premiers entre eux si et seulement s’il existe u et v entiers tels que au + bv = 1. Le sens réciproque est simple : tout diviseur commun de a et b divise 1 ; il ne peut donc avoir pour valeur positive que 1. Attention, une égalité au + bv = c avec c différent de 1 ne suffit pas à affirmer que le PGCD vaut c : il faut aussi prouver que c est un diviseur commun.

Le théorème de Gauss s’énonce ainsi : si a divise bc et si a et b sont premiers entre eux, alors a divise c. Pour le démontrer, Bézout fournit au + bv = 1. Multiplier par c donne c = auc + bvc. Le premier terme est multiple de a ; le second l’est aussi puisque a divise bc. Leur somme c est donc divisible par a. L’hypothèse de coprimalité est indispensable : 6 divise 2 × 3, mais ne divise ni 2 ni 3.

Un inverse de a modulo n est un entier u tel que au ≡ 1 [n]. Il existe exactement lorsque PGCD(a ; n) = 1. En effet, au ≡ 1 [n] signifie au + nv = 1 pour un entier v, ce qui est précisément une identité de Bézout. Lorsque l’inverse existe, tous ses représentants ont le même reste modulo n. On peut alors multiplier une congruence par cet inverse, ce qui permet de résoudre ax ≡ b [n].

Pour des nombres a et b premiers entre eux qui divisent tous deux c, leur produit ab divise c. Écrire c = ak puis appliquer Gauss à b | ak et PGCD(a ; b) = 1 donne b | k. Ainsi c = abℓ. Sans la coprimalité, ce résultat échoue : 4 et 6 divisent 12, tandis que 24 ne le divise pas. Chaque utilisation de Gauss doit faire apparaître les deux hypothèses, et non seulement une divisibilité.

L’équation ax + by = c possède une solution entière si et seulement si d = PGCD(a ; b) divise c, pour a et b non tous deux nuls. La nécessité vient du fait que d divise toute combinaison ax + by. Pour la suffisance, une identité au + bv = d, multipliée par l’entier c/d, fournit une solution particulière. Il reste ensuite à décrire toutes les solutions : l’existence d’un couple n’est que la première étape.

Supposons a et b non nuls. Après division par d, on obtient a′x + b′y = c′ avec a′ et b′ premiers entre eux. Si (x₀ ; y₀) est une solution, soustraire les deux égalités donne a′(x − x₀) = −b′(y − y₀). Par Gauss, b′ divise x − x₀. On pose donc x = x₀ + b′k, puis y = y₀ − a′k. Réciproquement, substituer ces expressions montre que chaque entier k donne une solution.

Erreurs fréquentes : croire que deux nombres premiers entre eux sont nécessairement premiers ; confondre le PGCD avec un reste intermédiaire ; oublier les signes lors de la remontée ; présenter seulement une solution particulière. Pour contrôler une identité de Bézout, calcule réellement la combinaison obtenue. Pour contrôler une famille de couples, remplace les deux inconnues dans l’équation initiale avant de restreindre le paramètre.

Pour réviser, refais une remontée d’Euclide sans regarder le modèle, puis vérifie ta combinaison avec les nombres de départ. Ouvre ensuite S’entraîner dans /exercices. Un bon prolongement consiste à traduire une contrainte concrète en une équation entière : l’algèbre décrit les solutions, mais les conditions de l’énoncé sélectionnent celles qui ont un sens.