Que calcule l'algorithme d'Euclide étendu ?

Il calcule pgcd(a, b) exactement comme l'algorithme d'Euclide standard, mais trouve en plus des entiers x et y (les coefficients de Bézout) satisfaisant a×x + b×y = pgcd(a, b).

Qu'est-ce que l'identité de Bézout ?

L'identité de Bézout affirme que pour deux entiers a et b quelconques, il existe des entiers x et y tels que a×x + b×y = pgcd(a, b) — l'algorithme d'Euclide étendu est la méthode standard pour les trouver.

Les coefficients de Bézout sont-ils uniques ?

Non — si (x, y) est une solution, alors (x + k×(b/pgcd), y − k×(a/pgcd)) est aussi une solution pour tout entier k. Cette calculatrice renvoie la paire spécifique produite par l'algorithme standard.

a ou b peuvent-ils être négatifs ?

Oui, l'algorithme gère correctement les entiers négatifs ; le pgcd rapporté est toujours renvoyé comme un nombre non négatif, avec x et y ajustés en conséquence.

Que se passe-t-il si a et b sont premiers entre eux ?

Si pgcd(a, b) = 1, l'équation devient a×x + b×y = 1, ce qui signifie que x est exactement l'inverse multiplicatif modulaire de a modulo b (et y est l'inverse de b modulo a).

Comment cela se rapporte-t-il à la Calculatrice d'Inverse Multiplicatif Modulaire ?

La Calculatrice d'Inverse Multiplicatif Modulaire exécute exactement cet algorithme en interne et extrait x, réduit modulo m, comme réponse — cette calculatrice expose directement le pgcd complet et les deux coefficients.

Quelle peut être la taille de a et b ?

Cette calculatrice prend en charge des entiers jusqu'à 100 chiffres chacun, calculés avec une arithmétique BigInt exacte afin qu'il n'y ait aucune erreur d'arrondi en virgule flottante même pour d'énormes entrées.

Où l'algorithme d'Euclide étendu est-il utilisé dans la vie réelle ?

Il est utilisé dans la génération de clés RSA, la résolution d'équations diophantiennes linéaires, le calcul d'inverses modulaires pour les protocoles cryptographiques, et tout algorithme nécessitant un certificat explicite pour un pgcd calculé.

Calculatrice de l'Algorithme d'Euclide Étendu — Trouver pgcd(a,b) et les Coefficients de Bézout

Notre Calculatrice de l'Algorithme d'Euclide Étendu trouve non seulement pgcd(a, b), mais aussi les entiers x et y — les coefficients de Bézout — satisfaisant l'identité a×x + b×y = pgcd(a, b), calculés avec une précision BigInt pour des entrées arbitrairement grandes. C'est le moteur direct derrière la Calculatrice d'Inverse Multiplicatif Modulaire du site et d'innombrables autres algorithmes de théorie des nombres.

Réponse rapide

Cette calculatrice trouve pgcd(a, b) ainsi que les entiers x et y satisfaisant a×x + b×y = pgcd(a, b), en utilisant l'algorithme d'Euclide étendu avec une précision BigInt exacte.

Saisissez a et b, puis cliquez sur Calculer.

Comment utiliser Calculatrice de l'Algorithme d'Euclide Étendu — pgcd + Coefficients de Bézout

1
Saisissez deux entiers, a et b.
2
Cliquez sur 'Calculer' pour trouver pgcd(a, b) et les coefficients de Bézout x et y.
3
Vérifiez le résultat : a × x + b × y est toujours égal au pgcd calculé.

Pourquoi utiliser Calculatrice de l'Algorithme d'Euclide Étendu — pgcd + Coefficients de Bézout ?

L'algorithme d'Euclide ordinaire trouve pgcd(a, b) par divisions successives, mais la version étendue suit une comptabilité supplémentaire à chaque étape afin qu'à la fin, elle ait aussi exprimé ce pgcd comme une combinaison linéaire des a et b d'origine — des entiers x et y avec a×x + b×y = pgcd(a, b), un résultat garanti par l'identité de Bézout. Ce n'est pas qu'une curiosité mathématique : ces coefficients sont exactement ce qui est nécessaire pour calculer des inverses multiplicatifs modulaires, résoudre des équations diophantiennes linéaires et implémenter la génération de clés RSA.

Questions fréquentes

Outils similaires

Calculatrice d'Inverse Multiplicatif Modulaire — Résoudre ax ≡ 1 (mod m)

Trouvez l'inverse multiplicatif modulaire de a modulo m en utilisant l'algorithme d'Euclide étendu. Calculatrice gratuite avec précision BigInt et vérification d'existence.

Calculatrice du Théorème des Restes Chinois — Résoudre des Systèmes Modulaires

Résolvez un système de congruences x ≡ aᵢ (mod mᵢ) pour des modules premiers entre eux deux à deux en utilisant le Théorème des Restes Chinois. Calculatrice gratuite avec précision BigInt.

Calculatrice d'Exponentiation Modulaire — bᵉ mod m Rapide en Ligne

Calculez bᵉ mod m pour des exposants arbitrairement grands en utilisant l'exponentiation rapide par élévation au carré et multiplication. Calculatrice gratuite avec précision BigInt, essentielle pour la cryptographie.

Calculatrice de Fractions Continues — Développer et Évaluer en Ligne

Développez n'importe quel nombre décimal ou fraction en ses termes de fraction continue [a₀; a₁, a₂, ...] et voyez chaque convergent. Calculatrice gratuite avec précision BigInt exacte.