L’algorithme d’Euclide étendu permet de calculer le PGCD de deux entiers, mais aussi deux coefficients x et y tels que :
a * x + b * y = pgcd(a, b)
Cette relation s’appelle l’identité de Bézout. Elle est très utile en arithmétique, en cryptographie, en calcul modulaire et dans plusieurs algorithmes sur les entiers.
En Python, une version itérative claire tient en quelques lignes.
def euclide_etendu(a, b):
ancien_r, r = a, b
ancien_x, x = 1, 0
ancien_y, y = 0, 1
while r != 0:
quotient = ancien_r // r
ancien_r, r = r, ancien_r - quotient * r
ancien_x, x = x, ancien_x - quotient * x
ancien_y, y = y, ancien_y - quotient * y
return ancien_r, ancien_x, ancien_y
pgcd, x, y = euclide_etendu(240, 46)
print(pgcd) # 2
print(x, y) # -9 47
print(240 * x + 46 * y) # 2
Le résultat signifie :
240 * (-9) + 46 * 47 = 2
La réponse courte
L’algorithme d’Euclide classique calcule seulement le PGCD :
def pgcd(a, b):
while b:
a, b = b, a % b
return abs(a)
L’algorithme d’Euclide étendu calcule en plus les coefficients de Bézout :
pgcd, x, y = euclide_etendu(a, b)
avec :
a * x + b * y = pgcd
Si le PGCD vaut 1, alors x est l’inverse modulaire de a modulo b.
Pourquoi l’algorithme d’Euclide fonctionne
Le PGCD de deux nombres ne change pas si l’on remplace le plus grand par son reste dans la division euclidienne.
Exemple :
240 = 46 * 5 + 10
46 = 10 * 4 + 6
10 = 6 * 1 + 4
6 = 4 * 1 + 2
4 = 2 * 2 + 0
Le dernier reste non nul est 2, donc :
pgcd(240, 46) = 2
L’algorithme étendu garde en plus la trace de la manière dont chaque reste peut s’écrire comme combinaison de a et b.
Version récursive
La version récursive est courte et proche de la définition mathématique.
def euclide_etendu_rec(a, b):
if b == 0:
return a, 1, 0
pgcd, x1, y1 = euclide_etendu_rec(b, a % b)
x = y1
y = x1 - (a // b) * y1
return pgcd, x, y
Test :
pgcd, x, y = euclide_etendu_rec(240, 46)
print(pgcd, x, y)
print(240 * x + 46 * y)
La version récursive est élégante, mais la version itérative évite les limites de récursion sur de très grands entiers.
Version itérative expliquée
La version itérative garde trois couples de valeurs :
- les restes ;
- les coefficients devant
a; - les coefficients devant
b.
ancien_r, r = a, b
ancien_x, x = 1, 0
ancien_y, y = 0, 1
Au départ :
a = 1 * a + 0 * b
b = 0 * a + 1 * b
À chaque étape, on applique la division euclidienne :
quotient = ancien_r // r
puis on met à jour les restes et les coefficients.
Le dernier ancien_r non nul est le PGCD. Les derniers ancien_x et ancien_y sont les coefficients de Bézout.
Gérer les nombres négatifs
Pour un usage robuste, on peut normaliser le signe du PGCD.
def euclide_etendu_normalise(a, b):
pgcd, x, y = euclide_etendu(a, b)
if pgcd < 0:
pgcd, x, y = -pgcd, -x, -y
return pgcd, x, y
Test :
pgcd, x, y = euclide_etendu_normalise(-240, 46)
print(pgcd)
print((-240) * x + 46 * y)
La relation de Bézout reste vraie.
Calculer un inverse modulaire
L’inverse modulaire de a modulo m est un nombre x tel que :
a * x % m == 1
Cet inverse existe seulement si a et m sont premiers entre eux, donc si :
pgcd(a, m) = 1
Avec Euclide étendu :
def inverse_modulaire(a, m):
pgcd, x, _ = euclide_etendu_normalise(a, m)
if pgcd != 1:
raise ValueError("L'inverse modulaire n'existe pas")
return x % m
Exemple :
inv = inverse_modulaire(3, 11)
print(inv) # 4
print((3 * inv) % 11) # 1
L’inverse de 3 modulo 11 est 4, car 3 * 4 = 12, et 12 % 11 = 1.
Pour un complément, voir aussi Modulo en Python : comprendre %, // et divmod.
Depuis Python 3.8 : pow peut aussi inverser modulo
Python sait calculer un inverse modulaire avec pow :
print(pow(3, -1, 11)) # 4
Si l’inverse n’existe pas, Python lève une erreur.
pow(6, -1, 9) # ValueError
pow(a, -1, m) est pratique. Mais l’algorithme d’Euclide étendu reste important pour comprendre pourquoi l’inverse existe et comment il est calculé.
Comparer avec math.gcd
Le module standard math fournit déjà gcd.
import math
print(math.gcd(240, 46)) # 2
Utilisez math.gcd si vous avez seulement besoin du PGCD. Utilisez Euclide étendu si vous avez besoin des coefficients de Bézout ou d’un inverse modulaire.
Complexité
L’algorithme d’Euclide est très efficace. Le nombre d’étapes grandit en gros avec le nombre de chiffres des entiers, pas avec leur valeur brute.
On note souvent sa complexité :
O(log min(a, b))
L’algorithme d’Euclide étendu garde la même logique, avec un peu plus de calcul à chaque étape pour suivre les coefficients.
Erreurs fréquentes
Retourner seulement le PGCD
Si votre fonction renvoie seulement pgcd, ce n’est pas l’algorithme d’Euclide étendu. Il faut aussi renvoyer x et y.
Oublier de vérifier l’inverse modulaire
L’inverse modulaire n’existe pas toujours.
inverse_modulaire(6, 9)
doit échouer, car pgcd(6, 9) = 3.
Mélanger quotient et reste
La mise à jour correcte repose sur :
ancien_r, r = r, ancien_r - quotient * r
et pas seulement sur le reste isolé. Les coefficients doivent suivre exactement la même transformation.
Ne pas tester l’identité de Bézout
Après chaque implémentation, vérifiez :
pgcd, x, y = euclide_etendu(a, b)
assert a * x + b * y == pgcd
C’est le test le plus simple et le plus utile.
Exercices rapides
Exercice 1
Calculez :
pgcd, x, y = euclide_etendu(99, 78)
Vérifiez ensuite :
99 * x + 78 * y == pgcd
Exercice 2
Trouvez l’inverse modulaire de 17 modulo 43.
Correction :
print(inverse_modulaire(17, 43))
print((17 * inverse_modulaire(17, 43)) % 43)
Exercice 3
Écrivez une fonction qui renvoie seulement les coefficients de Bézout.
Correction possible :
def bezout(a, b):
_, x, y = euclide_etendu_normalise(a, b)
return x, y
Pour aller plus loin
Euclide étendu est un petit algorithme, mais il revient partout dès que l’on travaille avec des entiers : PGCD, congruences, inverse modulaire, théorème de Bézout, RSA pédagogique, équations diophantiennes.
À lire ensuite :
- Modulo en Python : comprendre %, // et divmod avec exemples
- Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
- XOR en Python : opérateur ^, table de vérité et exemples bitwise
La règle à retenir : Euclide calcule le PGCD ; Euclide étendu calcule aussi comment écrire ce PGCD comme combinaison des deux entiers de départ.
Références
- Documentation Python officielle :
math.gcd - Documentation Python officielle :
pow - Wikipedia : Extended Euclidean algorithm
