Algorithme d'Euclide — exercice corrigé de Python (école d'ingénieur) (chapitre 2)

Algorithme d'Euclide

Structures de contrôle : conditions et boucles

Énoncé

Écrire une fonction pgcd(a, b) calculant le Plus Grand Commun Diviseur par l'algorithme d'Euclide. Prouver sa correction par invariant.

Corrigé

def pgcd(a, b):
    """
    Algorithme d'Euclide : pgcd(a, b) = pgcd(b, a mod b)
    Invariant : pgcd(a, b) = pgcd(a_initial, b_initial) à chaque étape
    """
    a, b = abs(a), abs(b)
    while b != 0:
        # Invariant : pgcd(a, b) = pgcd(original_a, original_b)
        a, b = b, a % b
    return a

Preuve par invariant : Soit $d = pgcd (a_{0}, b_{0})$ la valeur recherchée. Invariant : À chaque entrée de la boucle, $pgcd (a, b) = d$ .

Initialisation : Avant la boucle, $(a, b) = (a_{0}, b_{0})$ , donc $pgcd (a, b) = d$ .
Conservation : Si $pgcd (a, b) = d$ , alors $pgcd (b, a (mod b)) = d$ car $a = q b + (a (mod b))$ et tout diviseur commun de $a$ et $b$ divise aussi $a (mod b)$ , et réciproquement.
Terminaison : $b$ diminue strictement à chaque itération (car $0 \leq a (mod b) < b$ ) et reste positif ou nul. Le variant est $b$ , qui est une suite décroissante d'entiers naturels, donc finie.

Quand $b = 0$ , $pgcd (a, 0) = a$ , donc $a = d$ .