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

Algorithme d'Euclide étendu (ax + by = PGCD(a, b)) | Outil en ligne gratuit | Elysia Tools

Guide d'utilisation de l'outil

Découvrez quand utiliser cet outil, ce qu'il prend en charge et comment les utilisateurs l'appliquent.

Points clés

Catégorie: Math & Numbers
Types d’entrée: text, select
Type de sortie: text
Exemples associés: 4
API disponible: Oui

Aperçu

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}$.

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

1Saisissez les deux entiers $a$ et $b$ (positifs ou négatifs).
2Indiquez facultativement la valeur cible $c$ pour résoudre l'équation diophantienne $ax + by = c$.
3Sélectionnez le style d'affichage souhaité : résultat synthétique avec vérification ou tableau détaillé des étapes de division euclidienne.
4Consultez 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.

Exemples

1. Calcul de l'identité de Bézout avec étapes détaillées

Étudiant en mathématiques

Contexte

L'étudiant doit résoudre un exercice d'arithmétique demandant de trouver le PGCD de 240 et 46 et d'écrire la relation de Bézout pas à pas.

Problème

Vérifier chaque ligne de reste $r = a\cdot s + b\cdot t$ pour s'assurer de ne pas faire d'erreur de signe lors des substitutions.

Utilisation

Entrer a = 240, b = 46 et choisir le style de sortie « Afficher les étapes de division ».

a = 240, b = 46, style = steps

Résultat

Obtient le PGCD 2, le PPCM 5520, la suite des 5 divisions avec quotients et la relation finale 240 × (−9) + 46 × 47 = 2.

2. Résolution d'une équation diophantienne linéaire

Enseignant en informatique théorique

Contexte

L'enseignant prépare un corrigé pour une équation diophantienne $240x + 46y = 4$.

Problème

Vérifier la divisibilité par le PGCD, calculer la solution particulière et formaliser la solution générale.

Utilisation

Saisir a = 240, b = 46, renseigner le membre de droite c = 4 et sélectionner « Résultat et vérification ».

FAQ

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.

a = 240, b = 46, c = 4, style = result

Exécuter cet outil

Exemples adaptés à cet outil

Continuer avec des outils et dossiers associés

Découvrez quand utiliser cet outil, ce qu'il prend en charge et comment les utilisateurs l'appliquent.

Points clés

Aperçu

Quand l’utiliser

Fonctionnement

Cas d’usage

Exemples

1. Calcul de l'identité de Bézout avec étapes détaillées

2. Résolution d'une équation diophantienne linéaire

FAQ

Exemples de Traitement d'Images Web Python

Exemples de Traitement d'Images Android Java

Exemples de Traitement d'Images Android Kotlin

Exemples de Traitement d'Images Web Rust

Simplificateur d'expressions booléennes (table de Karnaugh)

Convertisseur de Ratio de Dilution (1:X ↔ 1/X ↔ %)

Calculateur d'inverse modulaire (Euclide étendu)

Calculateur d'arithmétique modulaire (addition / soustraction / produit / inverse / puissance)