# Algorithme d'Euclide étendu (ax + by = PGCD(a, b))

Résout l'identité de Bézout a·x + b·y = PGCD(a, b) pour des entiers de signe quelconque : table complète des étapes de division (chaque ligne vérifie r = a·s + b·t), PGCD et PPCM. Avec le membre droit optionnel c, l'outil devient un solveur d'équations diophantiennes : si PGCD | c, solution particulière et générale x = x₀ + (b/g)t ; sinon, absence de solution entière clairement signalée. Classique : 240 × (−9) + 46 × 47 = 2.

> Page canonique: https://elysiatools.com/fr/tools/extended-euclidean-algorithm

- **Catégorie:** Math & Numbers

- **Mots-clés:** euclide étendu, identité de bézout, coefficients de bézout, pgcd, équation diophantienne, diophantienne linéaire, théorie des nombres

## Présentation

Ce calculateur applique l'algorithme d'Euclide étendu pour déterminer le PGCD, le PPCM et les coefficients de l'identité de Bézout $a\cdot x + b\cdot y = \text{PGCD}(a, b)$ pour n'importe quelle paire d'entiers. En renseignant le paramètre optionnel $c$, il résout également les équations diophantiennes linéaires de la forme $ax + by = c$ en fournissant la solution particulière ainsi que l'ensemble des solutions générales dans $\mathbb{Z}$.

## Entrées

- **Valeur a** (text): First integer; negative values are supported.
- **Valeur b** (text): Second integer; negative values are supported.
- **Membre de droite c (facultatif, résout ax + by = c)** (text): Optional target: solves ax + by = c when gcd(a, b) divides c.
- **Style de sortie** (select)

## Quand l'utiliser

- Calculer les coefficients de Bézout et le PGCD de deux entiers avec le détail pas à pas des divisions.
- Résoudre une équation diophantienne linéaire $ax + by = c$ et vérifier l'existence de solutions entières.
- Déterminer un inverse modulaire dans le cadre d'exercices d'arithmétique ou d'algorithmes cryptographiques (RSA).

## Fonctionnement

- Saisissez les deux entiers $a$ et $b$ (positifs ou négatifs).
- Indiquez facultativement la valeur cible $c$ pour résoudre l'équation diophantienne $ax + by = c$.
- Sélectionnez le style d'affichage souhaité : résultat synthétique avec vérification ou tableau détaillé des étapes de division euclidienne.
- Consultez instantanément le PGCD, le PPCM, l'identité de Bézout et, si $c$ est fourni, les formules de la solution particulière et de la solution générale.

## Cas d'usage

- Étudiants et enseignants vérifiant les étapes manuelles de division euclidienne et les combinaisons linéaires.
- Développeurs et cryptographes calculant l'inverse modulaire $a^{-1} \pmod m$ via les coefficients de Bézout.
- Résolution rapide de problèmes de congruence et d'arithmétique modulaire en mathématiques discrètes.

## Questions fréquentes

### Que calcule l'algorithme d'Euclide étendu ?

Il calcule le PGCD de deux entiers $a$ et $b$ ainsi que deux entiers $x$ et $y$ satisfaisant l'identité de Bézout $ax + by = \text{PGCD}(a, b)$.

### À quelle condition l'équation $ax + by = c$ admet-elle des solutions entières ?

Une solution entière existe si et seulement si le PGCD de $a$ et $b$ divise exactement l'entier $c$.

### L'outil gère-t-il les nombres entiers négatifs ?

Oui, les entiers négatifs sont acceptés pour $a$, $b$ et $c$ ; les signes sont correctement pris en compte dans les étapes et les coefficients.

### Comment le PPCM est-il obtenu ?

Le PPCM est déduit directement de la relation $\text{PPCM}(a, b) = |a \times b| / \text{PGCD}(a, b)$.

### Quelle est la différence entre le mode « étapes » et le mode « résultat » ?

Le mode étapes liste chaque division successive et la combinaison linéaire $r = a\cdot s + b\cdot t$, tandis que le mode résultat donne directement la réponse finale et sa vérification.

## Outils associés

- [Simplificateur d'expressions booléennes (table de Karnaugh)](https://elysiatools.com/fr/tools/boolean-algebra-simplifier): Simplifie les fonctions booléennes en SOM minimale : entrez une expression (A–D, + OU, · ET, ' NON, ≤ 4 variables) ou la liste des minterms Σm ; l'algorithme de Quine-McCluskey extrait les impliquants premiers, retient les essentiels et complète une couverture minimale exacte ; affiche la SOM minimale, la table de Karnaugh en code Gray (2–4 variables), la forme canonique Σm et une vérification sur toutes les affectations. Classiques : AB + A'B → B ; Σm(0,1,2,4,5,6) (3 variables) → B' + C'.
- [Convertisseur de Ratio de Dilution (1:X ↔ 1/X ↔ %)](https://elysiatools.com/fr/tools/dilution-ratio-converter): Convertit entre les notations de dilution de laboratoire : proportion 1:X, fraction 1/X et pourcentage, avec le facteur de dilution et les parties soluté/diluant. Gère les deux conventions de 1:X (X = parties totales, ou 1 partie de soluté + X de diluant) ; avec le volume final, calcule les volumes à mélanger. Exemple classique : 1:5 = 1/5 = 20 % ; pour 100 mL, mélanger 20 mL de concentré + 80 mL de diluant.
- [Calculateur d'inverse modulaire (Euclide étendu)](https://elysiatools.com/fr/tools/modular-inverse-calculator): Calcule a⁻¹ mod m par l'algorithme d'Euclide étendu : fournit les coefficients de Bézout a·x + m·y = gcd(a, m), la table complète des coefficients progressifs (chaque ligne vérifie r = a·s + m·t) et la vérification a × a⁻¹ ≡ 1 (mod m). Accepte des nombres de taille RSA (jusqu'à 10⁵¹²) et signale clairement quand gcd(a, m) ≠ 1 rend l'inverse inexistant. Classique : en RSA, 17⁻¹ mod 3120 = 2753.
- [Calculateur d'arithmétique modulaire (addition / soustraction / produit / inverse / puissance)](https://elysiatools.com/fr/tools/modulo-arithmetic-converter): Effectue addition, soustraction, produit, inverse et exponentiation rapide modulo m en BigInt exact (jusqu'à 10¹⁸). Les opérations de base détaillent la réduction et renvoient le représentant canonique dans \[0, m−1\] ; l'inverse passe par l'algorithme d'Euclide étendu et signale explicitement gcd(a, m) ≠ 1 ; la puissance rapide affiche la table élever-au-carré-et-multiplier bit par bit de l'exposant. Exemples : 17⁵ mod 13 = 10 ; 5⁻¹ mod 18 = 11.
- [Générateur de tables de vérité](https://elysiatools.com/fr/tools/truth-table-generator): Génère la table de vérité complète d'une expression booléenne (jusqu'à 6 variables, 64 lignes) : prend en charge + OU, ^ XOR, ·/*/& ou juxtaposition ET, !/~/' NON et parenthèses ; les variables sont listées alphabétiquement, chaque ligne donne l'affectation et la valeur F, avec les formes canoniques Σm (minterms) et ΠM (maxterms). Classiques : AB + A'C a pour Σm(1,3,6,7) ; A ^ B ^ C est la fonction de parité impaire Σm(1,2,4,7).
- [Convertisseur de Vitesse Angulaire (rad/s / rpm / deg/s / Hz)](https://elysiatools.com/fr/tools/angular-velocity-converter): Conversion de vitesse angulaire : rad/s (base SI) ↔ tr/min (1=2π/60 rad/s) ↔ deg/s (1=π/180 rad/s) ↔ Hz (1 tour/s=2π rad/s). Ici Hz = tour par seconde. Conversion via rad/s avec les quatre équivalents. Réf. : vinyle 33⅓ tr/min≈3,49 rad/s, ralenti moteur ~800 tr/min≈83,8 rad/s.
- [Calculateur de Dimensionnement de Conduit (débit et vitesse)](https://elysiatools.com/fr/tools/duct-size-calculator): Dimensionne un conduit à partir du débit Q et de la vitesse de projet v : section A=Q/v. Circulaire : diamètre D=√(4A/π). Rectangulaire de rapport r=a/b : b=√(A/r), a=r·b, diamètre équivalent ASHRAE D_éq=1,30·(a·b)^0,625/(a+b)^0,25. Débit en m³/s/m³/h/CFM ; résultats en mm et pouces.
- [Calculateur de Limite de Fatigue (Goodman/Gerber/Soderberg)](https://elysiatools.com/fr/tools/fatigue-limit-calculator): Coefficient de sécurité en fatigue avec correction de contrainte moyenne. À partir de σ_a, σ_m et σ_uts, σ_-1, σ_y : trois critères classiques — Goodman modifié (linéaire, conservateur), Gerber (parabolique, meilleur pour les ductiles), Soderberg (via σ_y, le plus conservateur). Le minimum est le valeur gouvernante ; indique si le point est à l'intérieur de la ligne de Goodman.

## Exemples

- [Exemples de Traitement d'Images Web Python](https://elysiatools.com/fr/samples/web-image-processing-python): Exemples de traitement d'images Web Python utilisant PIL/Pillow incluant la lecture, l'enregistrement, le redimensionnement et la conversion de format
- [Exemples de Traitement d'Images Android Java](https://elysiatools.com/fr/samples/android-image-processing-java): Exemples de traitement d'images Android Java incluant lecture/écriture, mise à l'échelle et conversion de format
- [Exemples de Traitement d'Images Android Kotlin](https://elysiatools.com/fr/samples/android-image-processing-kotlin): Exemples de traitement d'images Android Kotlin incluant lecture/écriture, mise à l'échelle et conversion de format
- [Exemples de Traitement d'Images Web Rust](https://elysiatools.com/fr/samples/web-image-processing-rust): Exemples de traitement d'images Web Rust incluant lecture/écriture, redimensionnement et conversion de format