Euclide étendu : pgcd et coefficients de Bézout x, y
Pour 240 et 46, le plus grand commun diviseur vaut 2, et 240 × (−9) + 46 × 47 = 2. Saisissez deux entiers pour obtenir leur PGCD, les deux coefficients de Bézout et l'égalité qui le prouve. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- Premier entier
- 240
- Deuxième entier
- 46
- PGCD
- 2
- X
- -9
- Y
- 47
- Vérification
- 2
L'algorithme d'Euclide étendu fait plus que rapporter le plus grand commun diviseur de deux entiers : il produit aussi des coefficients de Bézout x et y tels que a fois x plus b fois y égale ce pgcd. Ces coefficients apparaissent dans les inverses modulaires lorsque le pgcd vaut un, dans les preuves constructives d'équations diophantiennes linéaires et dans les devoirs de cryptographie qui ont besoin d'une combinaison explicite plutôt que d'un reste nu.
Des restes aux coefficients de Bézout
La division euclidienne ordinaire remplace répétitivement une paire (a, b) par (b, a mod b) jusqu'à ce que le reste soit nul ; le dernier reste non nul est pgcd(a, b). La forme étendue suit comment chaque reste s'écrit comme combinaison linéaire entière des entrées d'origine. À chaque étape le reste courant égale a fois un coefficient plus b fois un autre, et lorsque l'algorithme s'arrête ces coefficients sont exactement les nombres de Bézout du pgcd.
Les présentations en classe utilisent souvent la substitution arrière à partir de la suite des quotients ; le code de production met à jour de façon itérative deux paires de coefficients sans stocker une pile de restes. Les deux approches calculent le même objet mathématique : des entiers x et y satisfaisant a*x + b*y = pgcd(a, b). Ce point d'accès implémente le chemin itératif sur les valeurs absolues, puis réintroduit les signes pour que les entrées négatives satisfassent encore l'identité.
Le pgcd est toujours renvoyé comme entier non négatif, selon la convention standard des bibliothèques et des énoncés de concours.
Ce que vous envoyez et ce que vous recevez
La paire zéro et zéro est aussi rejetée, car pgcd(0, 0) est indéfini et aucun coefficient ne produit d'équation significative. En cas de succès la réponse inclut a et b normalisés, pgcd, x, y, un objet bezout imbriqué avec les mêmes coefficients, une vérification numérique égale à a*x + b*y, et une chaîne d'équation telle que 240*(-9) + 46*(47) = 2.
Contrôles typiques : pour 240 et 46 le pgcd est 2 et une solution valide est x égal à moins neuf avec y égal à quarante-sept ; pour une paire première avec pgcd un les coefficients donnent un inverse modulaire de a modulo b après réduction de x. Les cas limites 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 de coefficients trivial.
Où les coefficients de Bézout apparaissent en pratique
Les programmeurs de concours résolvent ax + by = c en calculant d'abord le pgcd et les coefficients 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 récupèrent des inverses modulaires pour des exemples RSA jouets et des chiffres affines lorsque pgcd(a, m) vaut un en lisant le coefficient de a après réduction modulo m.
Les enseignants assignent des preuves constructives que deux entiers sont premiers entre eux et ont besoin d'un oracle déterministe qui montre la combinaison, pas seulement un bit de coprimalité. Les ingénieurs de données et de systèmes ont parfois besoin de combinaisons linéaires explicites pour réconcilier des plannings périodiques ou une arithmétique de pas. Utilisez l'outil navigateur pour vérifier rapidement les 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 plus fort.
Cas d’usage
Équations diophantiennes linéaires
Obtenez une solution particulière (x, y) pour a*x + b*y = pgcd, puis mettez à l'échelle et paramétrez pour résoudre a*x + b*y = c en concours ou devoirs.
Brique de base de l'inverse modulaire
Lorsque pgcd(a, m) = 1, réduisez le coefficient de Bézout de a modulo m pour récupérer un inverse modulaire pour la crypto et les exercices de théorie des nombres.
Questions fréquentes
Qu'est-ce que l'algorithme d'Euclide étendu ?
Il calcule pgcd(a, b) et des entiers x, y (coefficients de Bézout) tels que a*x + b*y égale ce pgcd, en suivant les combinaisons linéaires à travers les restes euclidiens.
Les coefficients sont-ils uniques ?
Non. Si (x, y) fonctionne, (x + k*(b/g), y − k*(a/g)) aussi pour tout entier k. Cet outil renvoie une solution particulière de l'algorithme itératif.
Quelle plage d'entiers est prise en charge ?
Chacun de a et b doit être un entier de valeur absolue au plus 9007199254740991 (Number.MAX_SAFE_INTEGER).
Comment trouver les coefficients de Bézout de 240 et 46 ?
Saisissez les deux nombres. Le PGCD vaut 2 et les coefficients sont −9 et 47, car 240 × (−9) + 46 × 47 = 2. Le résultat inclut cette égalité pour que vous puissiez la vérifier.
Comment obtenir un inverse modulaire à partir du résultat ?
Lorsque le PGCD vaut 1, le coefficient du premier nombre, ramené modulo le second, est l'inverse du premier modulo le second. C'est la méthode habituelle pour les exemples de RSA et les chiffrements affines.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre stack
curl -X POST https://api.kit.forhosting.com/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemple de requête
{
"a": 240,
"b": 46
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Limites
max_abs | 9007199254740991 |
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Cette capacité prend deux entiers, rejette le cas indéfini où les deux sont nuls, et renvoie un JSON stable avec pgcd, x, y, une vérification et une chaîne d'équation lisible que vous pouvez coller dans des notes ou des tests.
Ce que vous envoyez et ce que vous recevez
Fournissez des entiers a et b (les alias first ou m pour a, et second ou n pour b sont acceptés). Les non-entiers, champs vides et valeurs hors du maximum absolu d'entiers sûrs de la plateforme sont rejetés avec invalid_input et ne sont pas facturés.
Où les coefficients de Bézout apparaissent en pratique
Comme la capacité est un moteur de parse pur, il n'y a ni dérive de modèle, ni dépendance réseau, ni état stocké : la même paire produit toujours le même JSON pour une convention fixe de coefficients. Le tarif API est la base publiée de $0.002 par élément réussi ; l'échec de validation ne consomme pas le solde.
Cas d'intégration
Enseignement et contrôles automatisés
Montrez aux étudiants l'identité a*x + b*y = pgcd avec un champ d'équation JSON stable, et branchez le même contrat dans des correcteurs ou fixtures CI.
Questions techniques
Pourquoi a et b tous deux nuls sont-ils rejetés ?
pgcd(0, 0) est indéfini. Il n'y a pas de plus grand commun diviseur positif, donc l'API renvoie invalid_input et ne facture pas.
Combien cela coûte-t-il ?
L'outil navigateur est gratuit et s'exécute localement. Les requêtes API utilisent le solde KIT prépayé à $0.002 par élément réussi ; l'entrée invalide n'est pas facturée.