Combinaison linéaire de deux nombres : x, y pour ax+by=c

Une combinaison linéaire de deux entiers a et b est tout entier qui peut s’écrire comme a fois x plus b fois y pour certains entiers x et y. Toute cible n’est pas atteignable : le théorème de Bézout affirme que l’ensemble atteignable est exactement celui des multiples du plus grand commun diviseur de a et b. Ce calculateur de combinaison linéaire de deux nombres accepte les coefficients a et b plus une cible c, calcule ce pgcd avec l’algorithme d’Euclide étendu et renvoie une paire particulière de coefficients qui réalise la cible, ou signale qu’aucune solution entière n’existe. Les étudiants l’utilisent pour vérifier des exercices diophantiens ; les développeurs réutilisent le même contrat pur dans les concours, l’arithmétique d’horaires et les pipelines d’arithmétique modulaire.

Ce qu’est une combinaison linéaire et quand une cible est atteignable

Étant donnés des entiers a et b, l’ensemble de toutes les combinaisons linéaires entières a fois x plus b fois y est un objet fondamental de la théorie élémentaire des nombres. L’algorithme d’Euclide montre que cet ensemble coïncide avec celui des multiples de g, où g est le plus grand commun diviseur de a et b. De façon équivalente, l’équation diophantienne linéaire a fois x plus b fois y égale c admet des solutions entières si et seulement si g divise c.

Lorsqu’une solution existe, il en existe une infinité : si (x0, y0) est une solution particulière, la famille générale est x égal à x0 plus (b sur g) fois t et y égal à y0 moins (a sur g) fois t pour tout paramètre entier t. L’étape constructive qui produit une solution particulière est l’algorithme d’Euclide étendu : tout en calculant g, il suit comment chaque reste s’écrit comme combinaison des a et b d’origine et, à la terminaison, fournit des coefficients de Bézout pour g lui-même.

Multiplier ces coefficients par l’échelle entière c sur g produit une solution pour la cible c. Ce calculateur regroupe ce pipeline complet : il renvoie le pgcd, un indicateur booléen possible, une paire particulière (x, y) lorsque la cible est atteignable, une vérification numérique égale à a fois x plus b fois y, une chaîne d’équation lisible et des chaînes de forme générale pour la famille paramétrique.

Lorsque g ne divise pas c, la réponse reste un succès mais fixe possible à false et explique l’obstacle, dans le langage de classe selon lequel l’équation n’a pas de solution entière, plutôt que de prétendre que le client a envoyé des données invalides.

Contrat d’entrée, forme de la réponse et comportement d’erreur

La paire a égal à zéro et b égal à zéro est aussi rejetée, car une combinaison linéaire de deux zéros n’est pas un ensemble générateur significatif pour une cible. Sur une instance bien formée mais irrésoluble, possible est false, x et y sont omis, et reason indique que le pgcd ne divise pas la cible. Exemple : a égal à quinze, b égal à vingt-cinq, c égal à dix donne pgcd cinq, possible true et une paire valide x égal à quatre et y égal à moins deux.

Exemple d’impossibilité : a égal à quatre, b égal à six, c égal à cinq donne pgcd deux et possible false car deux ne divise pas cinq. Associez la réponse à votre propre générateur d’étapes si vous avez besoin de toutes les solutions entières ; ce point d’accès renvoie une solution particulière plus la forme générale, pas une énumération infinie.

Où un calculateur de combinaison linéaire apporte une vraie valeur

La programmation de concours et l’entraînement olympique demandent souvent des solutions entières de a fois x plus b fois y égale c ; un oracle déterministe qui certifie la résolubilité via le test du pgcd et renvoie des coefficients réduit le temps de débogage sur les erreurs d’échelle d’une unité. Les carnets d’ingénierie utilisent des combinaisons à deux coefficients pour concilier horaires périodiques, dénominations monétaires ou nombres de dents d’engrenage qui doivent atteindre un total exact.

Les démonstrations de cryptographie et d’arithmétique modulaire partent souvent de la même étape d’Euclide étendu avant de se spécialiser en inverses lorsque le pgcd vaut un. Une validation échouée ne consomme pas le solde.