Algorithme d’Euclide étendu en Python : PGCD, Bézout et inverse modulaire

Euclide étendu calcule le PGCD de deux entiers et les coefficients qui permettent de l’écrire comme une combinaison de ces entiers. La fonction ci-dessous renvoie (d, x, y) avec a * x + b * y == d et un PGCD non négatif. Elle traite aussi les nombres négatifs et les zéros.

Cette identité de Bézout permet notamment de calculer un inverse modulaire lorsqu’il existe. Si vous cherchez uniquement le PGCD, la fonction math.gcd de Python suffit.

Code exécuté le 18 septembre 2026 avec Python 3.12.14. Aucune bibliothèque externe n’est nécessaire.

Le résultat sur un exemple

Pour a = 240 et b = 46, une réponse est d = 2, x = -9, y = 47 :

240 × (-9) + 46 × 47 = -2160 + 2162 = 2

Les coefficients ne sont pas uniques. Une autre implémentation peut fournir un autre couple tout en respectant la même identité. Pour vérifier une réponse, contrôlez le PGCD et l’égalité, plutôt qu’un couple de coefficients choisi arbitrairement.

Une implémentation complète avec un contrat clair

Cette version accepte des entiers Python, en excluant explicitement les booléens. L’inverse modulaire utilise un module entier m ≥ 2. Ce choix évite les conventions particulières du module 1 et des modules négatifs.

Enregistrez le code dans exemple_euclide.py, puis lancez python exemple_euclide.py :

"""Euclide étendu : entiers signés, PGCD non négatif, inverse modulo m >= 2."""
import math


def euclide_etendu(a, b):
    if type(a) is not int or type(b) is not int:
        raise TypeError("a et b doivent être des entiers Python, hors booléens")
    r0, r1 = abs(a), abs(b)
    x0, x1, y0, y1 = 1, 0, 0, 1
    while r1:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    x = x0 if a >= 0 else -x0
    y = y0 if b >= 0 else -y0
    return r0, x, y


def inverse_modulaire(a, m):
    if type(m) is not int or m < 2:
        raise ValueError("m doit être un entier Python supérieur ou égal à 2")
    d, x, _ = euclide_etendu(a, m)
    if d != 1:
        raise ValueError("Pas d'inverse : a et m ne sont pas premiers entre eux")
    return x % m


if __name__ == "__main__":
    for a, b in [(240, 46), (-240, 46), (0, 7), (7, 0), (0, 0)]:
        d, x, y = euclide_etendu(a, b)
        assert d == math.gcd(a, b) and a * x + b * y == d
        print(f"({a}, {b}) : PGCD={d}, x={x}, y={y}")
    print("Inverse de 3 modulo 11 :", inverse_modulaire(3, 11))
    print("Même résultat avec pow :", pow(3, -1, 11))
    try:
        inverse_modulaire(6, 9)
    except ValueError:
        print("6 modulo 9 : aucun inverse")

Sortie observée :

(240, 46) : PGCD=2, x=-9, y=47
(-240, 46) : PGCD=2, x=9, y=47
(0, 7) : PGCD=7, x=0, y=1
(7, 0) : PGCD=7, x=1, y=0
(0, 0) : PGCD=0, x=1, y=0
Inverse de 3 modulo 11 : 4
Même résultat avec pow : 4
6 modulo 9 : aucun inverse

Pourquoi les mises à jour sont correctes

Sur les valeurs absolues, chaque reste peut s’écrire comme une combinaison des deux nombres de départ. Au début, les coefficients sont (1, 0) pour le premier reste et (0, 1) pour le second.

La division donne r0 = q * r1 + reste. Pour obtenir les coefficients du reste suivant, on soustrait donc q fois les coefficients de r1 à ceux de r0. Les affectations simultanées de Python évitent d’utiliser une valeur déjà remplacée.

Le dernier reste non nul est le PGCD. À la fin, les signes des coefficients sont réajustés pour retrouver les entiers originaux. Cette normalisation fait partie de la fonction ; l’appelant n’a pas besoin d’ajouter une seconde fonction pour corriger un PGCD négatif.

Les cas nuls et négatifs

Pour (0, 7), l’identité devient 0 × 0 + 7 × 1 = 7. Pour (7, 0), elle devient 7 × 1 + 0 × 0 = 7. Pour (0, 0), le script adopte la convention de math.gcd et renvoie un PGCD nul. Le couple de coefficients (1, 0) satisfait alors l’égalité, comme de nombreux autres couples.

Avec (-240, 46), le coefficient devant le premier nombre change de signe : -240 × 9 + 46 × 47 = 2. Travailler sur les valeurs absolues puis rétablir les signes rend cette convention explicite.

Quand l’inverse modulaire existe-t-il ?

On cherche un entier x tel que (a * x) % m == 1. Avec notre convention m ≥ 2, cet inverse existe exactement lorsque gcd(a, m) == 1. Bézout donne alors a * x + m * y = 1, donc le terme m * y disparaît modulo m.

La fonction renvoie x % m, un représentant entre 0 et m - 1. Pour 3 modulo 11, l’inverse vaut 4. Pour 6 modulo 9, il n’existe pas : le PGCD vaut 3, et la fonction lève ValueError.

Python propose aussi pow(a, -1, m) pour un inverse modulaire, sous ses propres conditions d’entrée. Notre exemple le compare au calcul explicite. Pour revoir les divisions et les restes, consultez modulo, division entière et divmod en Python.

Vérifier davantage qu’un seul exemple

Les contrôles de cette version comparent les résultats à math.gcd et vérifient l’identité de Bézout sur les 1 681 couples d’entiers de -20 à 20. Les inverses existants sont comparés à pow sur une grille de petits nombres. Les cas sans inverse, les modules refusés, les types invalides et des entiers de plusieurs centaines de chiffres sont aussi testés.

Ces contrôles ne remplacent pas le raisonnement sur l’invariant ; ils permettent de repérer les erreurs de signe, de permutation des coefficients et de convention sur zéro. Une implémentation pédagogique ne constitue pas à elle seule une bibliothèque de cryptographie adaptée aux contraintes de sécurité d’un système réel.

Complexité et choix de la version itérative

Pour des entrées positives non nulles, le nombre de divisions est logarithmique en la plus petite entrée. Les opérations portent toutefois sur des entiers dont la taille peut être grande : compter les divisions et compter les opérations sur les bits sont deux analyses différentes.

La version itérative garde un nombre constant de variables et évite une pile d’appels récursifs. La place occupée par ces variables dépend de la taille des entiers. Elle ne rend donc pas gratuit le calcul sur des nombres de millions de chiffres.

Trois exercices avec vérification

1. Calculez les coefficients pour 35 et 15, puis vérifiez l’égalité de Bézout.
2. Trouvez l’inverse de 7 modulo 26 et vérifiez le produit modulo 26.
3. Expliquez pourquoi 10 n’a pas d’inverse modulo 20 avant de lancer le programme.

Continuer les exercices Python

Le guide de complexité algorithmique aide à distinguer nombre d’étapes et coût des opérations. Notre page de ressources Python et d’exercices propose la suite du parcours.