Le PGCD par soustractions successives — exercice corrigé de sciences numériques et technologie (seconde) (chapitre 4)

Le PGCD par soustractions successives

Les boucles · La boucle non bornée : while · niveau 3 (difficile)

Énoncé

L'algorithme d'Euclide repose sur ce fait : si $a > b$ , alors $a$ et $b$ ont les mêmes diviseurs communs que $a - b$ et $b$ .

Écrire une fonction pgcd(a, b) qui applique ce principe avec une boucle while, en retranchant à chaque tour le plus petit du plus grand jusqu'à ce qu'ils soient égaux.
La tester sur $(48, 18)$ et $(35, 14)$ .
Pourquoi la boucle se termine-t-elle toujours ?

Corrigé

def pgcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

print(pgcd(48, 18))   # 6
print(pgcd(35, 14))   # 7

Déroulé sur $(48, 18)$ : $(30, 18) \to (12, 18) \to (12, 6) \to (6, 6)$ , d'où $6$ .

3. La terminaison. À chaque tour, l'un des deux nombres diminue strictement et tous deux restent des entiers strictement positifs. Une suite d'entiers positifs strictement décroissante ne peut être infinie : la boucle s'arrête donc nécessairement.

C'est exactement le raisonnement à tenir devant tout while : identifier une quantité entière positive qui décroît strictement. Sans lui, rien ne garantit que le programme s'arrête. Ici, si l'on écrivait a = a + b par étourderie, la boucle tournerait indéfiniment.

Remarque. La version rapide remplace les soustractions par un reste : while b != 0: a, b = b, a % b.