Calculatrice de l'Algorithme Euclidien Étendu

La Calculatrice de l'algorithme euclidien étendu calcule le plus grand commun diviseur (PGCD) de deux entiers et trouve les coefficients de Bézout — les entiers s et t satisfaisant pgcd(a, b) = s·a + t·b. Au-delà du calcul du PGCD, cet outil fournit un tableau de division par étapes entièrement animé, la remontée par substitution et le calcul de l'inverse modulaire, ce qui le rend idéal pour les cours de théorie des nombres, l'étude de la cryptographie et la programmation compétitive.

Qu'est-ce que l'algorithme d'Euclide étendu ?

L'Algorithme d'Euclide étendu (AEE) est une extension de l'algorithme classique d'Euclide pour le PGCD. Alors que l'algorithme de base trouve le pgcd(a, b) par divisions successives, la version étendue suit simultanément deux séquences d'entiers qui enregistrent comment chaque reste peut être exprimé comme une combinaison linéaire des entrées d'origine.

Comment fonctionne l'algorithme

L'AEE maintient trois paires de valeurs — (r, s, t) — à travers chaque étape de division :

1. Initialisation : r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Chaque étape : calculer le quotient q = ⌊rₙ₋₁ / rₙ⌋, puis mettre à jour rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Arrêter quand le reste = 0 ; le reste précédent est le pgcd(a, b)
4. Les valeurs s et t correspondantes sont les coefficients de Bézout

Exemple étape par étape : pgcd(252, 105)

Résultat : pgcd(252, 105) = 21, avec l'identité de Bézout : 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Essayez par vous-même avec la calculatrice ci-dessus pour obtenir les coefficients exacts.

Applications de l'algorithme d'Euclide étendu

1. Inverse modulaire (Cryptographie)

L'application la plus importante est le calcul des inverses modulaires. Si pgcd(a, m) = 1, alors le coefficient de Bézout s satisfait :

Les inverses modulaires sont essentiels dans le chiffrement RSA (calcul de l'exposant de clé privée d), l'échange de clés Diffie-Hellman et la cryptographie sur courbes elliptiques.

2. Résolution d'équations diophantiennes linéaires

L'équation ax + by = c a des solutions entières si et seulement si pgcd(a, b) divise c. Si c'est le cas, une solution particulière est x₀ = s·(c/d), y₀ = t·(c/d) où d = pgcd(a, b) et s, t sont les coefficients de Bézout.

3. Théorème des restes chinois

L'AEE est utilisé dans la preuve constructive et le calcul du théorème des restes chinois — trouver x tel que x ≡ a₁ (mod m₁) et x ≡ a₂ (mod m₂) — en calculant les inverses modulaires des moduli.

4. Réduction de fractions et PPCM

pgcd(a, b) = 1 confirme que a/b est déjà sous sa forme irréductible. Le PPCM est ppcm(a, b) = |a·b| / pgcd(a, b).

Les coefficients de Bézout ne sont pas uniques

Les coefficients de Bézout s et t ne sont pas uniques. Si (s, t) est une solution, alors (s + k·(b/d), t − k·(a/d)) est également une solution pour tout entier k, où d = pgcd(a, b). L'AEE renvoie la solution où |s| ≤ |b/d| et |t| ≤ |a/d|.

Complexité temporelle

L'algorithme d'Euclide étendu s'exécute en O(log min(a, b)) itérations — la même chose que l'algorithme d'Euclide de base. Selon le théorème de Lamé, le nombre d'étapes ne dépasse jamais 5 fois le nombre de chiffres décimaux de la plus petite entrée. Cela le rend extrêmement efficace même pour les grands entiers utilisés dans les applications cryptographiques.

Foire aux questions

Qu'est-ce que l'algorithme d'Euclide étendu ?

L'algorithme d'Euclide étendu prolonge l'algorithme du PGCD d'Euclide pour calculer également les coefficients de Bézout s et t satisfaisant pgcd(a, b) = s·a + t·b. Il suit comment chaque reste peut être exprimé comme une combinaison linéaire de a et b tout au long du processus de division.

Que sont les coefficients de Bézout ?

Les coefficients de Bézout sont des entiers s et t dont l'existence est garantie par l'identité de Bézout (un théorème de la théorie des nombres). Ils satisfont pgcd(a, b) = s·a + t·b et sont calculés efficacement par l'algorithme d'Euclide étendu. Ils sont utilisés dans le calcul de l'inverse modulaire, la résolution d'équations diophantiennes et le théorème des restes chinois.

Comment trouver l'inverse modulaire avec l'algorithme d'Euclide étendu ?

Si pgcd(a, b) = 1 (a et b sont premiers entre eux), le coefficient de Bézout s satisfait s·a ≡ 1 (mod b). L'inverse modulaire de a mod b est s mod b (ajusté pour être positif). Cette calculatrice l'affiche directement dans les résultats.

Quand l'inverse modulaire n'existe-t-il pas ?

L'inverse modulaire de a modulo m existe si et seulement si pgcd(a, m) = 1. Si pgcd(a, m) > 1, aucun entier x ne satisfait a·x ≡ 1 (mod m).

Quelle est la complexité temporelle de l'algorithme d'Euclide étendu ?

O(log min(a, b)) divisions, comme l'algorithme d'Euclide de base. Selon le théorème de Lamé, le nombre d'étapes est borné par 5 fois le nombre de chiffres décimaux de la plus petite entrée, ce qui le rend très efficace.

Ressources supplémentaires

• Algorithme d'Euclide étendu - Wikipédia
• Identité de Bézout - Wikipédia
• Inverse multiplicatif modulaire - Wikipédia