Coefficients de Bézout : entiers x, y avec a·x + b·y = pgcd

L'identité de Bézout affirme que, pour tous entiers a et b non tous deux nuls, il existe des entiers x et y tels que a fois x plus b fois y égale le plus grand commun diviseur de a et b. Ces coefficients sont le cœur constructif des équations diophantiennes linéaires, des inverses modulaires lorsque le pgcd vaut un, et des preuves scolaires que deux nombres sont premiers entre eux.

Ce qu'affirme l'identité de Bézout et pourquoi les coefficients comptent

Toute paire d'entiers non tous deux nuls possède un plus grand commun diviseur non négatif bien défini g. L'identité de Bézout va plus loin : elle garantit des entiers x et y pour lesquels a fois x plus b fois y égale ce g. La preuve d'existence est constructive et suit le processus des restes euclidiens.

La division ordinaire remplace répétitivement une paire par le reste suivant jusqu'à l'apparition de zéro ; le dernier reste non nul est le pgcd. En suivant comment chaque reste s'écrit comme combinaison linéaire entière des entrées d'origine, on obtient les coefficients à la terminaison. Les manuels scolaires rétro-substituent souvent les quotients de la table de divisions ; le code de production met généralement à jour deux paires de coefficients dans une seule boucle sans empiler les restes.

Les deux approches calculent le même objet mathématique. Les coefficients ne sont pas uniques : si une paire convient, toute paire décalée par des multiples entiers de b sur g et de a sur g avec signes opposés convient aussi. Cet outil renvoie une solution particulière de l'algorithme itératif, toujours avec un pgcd non négatif, afin que scripts et correcteurs comparent une convention fixe sans redériver l'ensemble général des solutions.

Comment appeler le calculateur et lire la réponse

Envoyez les entiers a et b. La paire zéro et zéro est aussi rejetée, car le pgcd de zéro et zéro est indéfini et aucun coefficient ne produit d'équation de Bézout pertinente.

En cas de succès, la réponse inclut a et b normalisés, le pgcd, x, y, un objet bezout imbriqué avec les mêmes coefficients, un check numérique égal à a fois x plus b fois y, une chaîne d'équation du type deux cent quarante fois moins neuf plus quarante-six fois quarante-sept égale deux, et un champ identity énonçant la relation générale.

Contrôles typiques : pour deux cent quarante et quarante-six le pgcd vaut deux avec une solution valide x égale moins neuf et y égale quarante-sept ; pour une paire de premiers de pgcd un, les coefficients donnent l'inverse modulaire de a modulo b après réduction de x. Les cas avec un zéro et un partenaire non nul donnent un pgcd égal à la valeur absolue de l'entrée non nulle et un motif trivial de coefficients.

Où les coefficients de Bézout interviennent en pratique

Les programmeurs de concours résolvent a fois x plus b fois y égale c en calculant d'abord le pgcd et une paire de Bézout de base, puis en mettant à l'échelle et en paramétrant la solution générale lorsque le pgcd divise c. Les étudiants en cryptographie retrouvent des inverses modulaires pour des exemples pédagogiques RSA et des chiffres affines lorsque le pgcd de a et m vaut un, en lisant le coefficient de a après réduction modulo m.

Les enseignants demandent des preuves constructives que deux entiers sont premiers entre eux et ont besoin d'un oracle déterministe qui montre la combinaison linéaire, pas seulement un bit de coprimalité. Les ingénieurs données et systèmes ont parfois besoin de combinaisons linéaires explicites pour concilier des calendriers périodiques ou une arithmétique de pas. Utilisez l'outil navigateur pour vérifier rapidement des devoirs, puis automatisez le même contrat lorsque votre service a besoin de contrôles diophantiens en masse.

Si vous n'avez besoin que du pgcd sans coefficients, cette page répond encore à ce besoin tout en enseignant le résultat constructif de Bézout qui sous-tend les programmes de théorie des nombres et les questions d'entretien sur le raisonnement d'Euclide étendu.