Algorithmes d'arithmétique et de polynômes

Pour tous $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$, il existe un unique couple $(q, r) \in \mathbb{Z}^2$ tel que $a = bq + r$ et $0 \leq r < |b|$. L'entier $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$. Lu en français : on retranche $b$ à $a$ autant de fois qu'il le faut pour tomber dans l'intervalle $[0, |b|[$, et $r$ est ce qui reste. Ce résultat est établi dans le thème Divisibilité, PGCD et Bézout dans Z (bloc Algèbre 3) : on s'en sert ici sans le redémontrer. Tous les algorithmes de ce thème, sans exception, sont bâtis sur ce couple $(q, r)$.

Pour tous entiers a et b avec b non nul, Python garantit deux choses : l'identité a == b * (a // b) + a % b, et le fait que a % b a le signe du diviseur b (ou vaut zéro). L'opérateur // est le quotient par défaut : il arrondit vers $-\infty$, et non vers zéro. Conséquence pratique : quand b est strictement positif, a % b appartient à $\{0, \dots, b-1\}$ et coïncide avec le reste de la division euclidienne, même si a est négatif ; quand b est strictement négatif, ce n'est plus le reste au sens de la définition. Dans tout ce thème on travaille sur des entiers naturels ou l'on prend des valeurs absolues, ce qui place systématiquement dans le premier cas.

Ligne fautive : « -7 % 3 vaut -1, comme en C ou en Java. »
C'est faux : en Python, -7 % 3 vaut 2 et -7 // 3 vaut -3, ce qui est cohérent puisque $3 \times (-3) + 2 = -7$. Le quotient est arrondi vers $-\infty$, pas vers zéro, et le reste reste dans $\{0, 1, 2\}$. L'erreur symétrique existe aussi : 7 % -3 vaut -2 et non 1, parce que le reste prend le signe du diviseur.
Version correcte : sur des entiers naturels, a % b est le reste de la division euclidienne, sans précaution. Dès qu'un signe peut apparaître, on écrit la précondition dans la spécification et l'on ramène les données en valeur absolue avant la boucle, ou l'on teste sur un exemple chiffré avant de se fier à son intuition.

En Python, le type int est exact et de taille non bornée : 2 ** 1000 est calculé sans débordement ni arrondi, alors qu'un flottant perdrait toute précision. Ce confort a un prix : une addition ou une multiplication d'entiers n'est à coût constant que tant que les entiers tiennent sur quelques mots machine. Dans ce thème on adopte la convention usuelle des concours : on compte les opérations arithmétiques (addition, multiplication, division euclidienne, comparaison) comme élémentaires, et l'on annonce séparément le cas où les entiers grossissent, ce qui arrive avec l'exponentiation rapide non réduite. Rappel hors ligne, en une phrase : $f = O(g)$ signifie qu'il existe une constante $C > 0$ et un rang à partir duquel $|f| \leq C g$ (thème Négligeabilité, domination et équivalents, bloc Analyse 2). Le modèle de comptage lui-même est celui du thème Complexité des algorithmes.

Diviser : $b$ divise $a$, noté $b \mid a$, s'il existe $k \in \mathbb{Z}$ tel que $a = bk$. Quotient et reste : les deux entiers de la division euclidienne, a // b et a % b. PGCD : le plus grand des diviseurs communs. Premiers entre eux : deux entiers dont le PGCD vaut $1$ ; on dit aussi étrangers. Coefficients de Bézout : un couple $(u, v)$ d'entiers tel que $au + bv = \operatorname{pgcd}(a, b)$. Nombre premier : un entier supérieur ou égal à $2$ dont les seuls diviseurs positifs sont $1$ et lui-même. Composé : un entier supérieur ou égal à $2$ qui n'est pas premier. Valuation $p$-adique : l'exposant de $p$ dans la décomposition en facteurs premiers. Cribler : marquer d'avance les multiples pour ne plus avoir à les tester. Degré d'un polynôme non nul : l'indice du dernier coefficient non nul.

Soient $a, b \in \mathbb{Z}$ non tous deux nuls. L'ensemble des diviseurs communs de $a$ et $b$ est non vide (il contient $1$) et majoré (par $\max(|a|, |b|)$), donc il admet un plus grand élément : c'est le PGCD de $a$ et $b$, noté $\operatorname{pgcd}(a, b)$. On complète par la convention $\operatorname{pgcd}(0, 0) = 0$, qui rend les formules valables sans cas particulier. Deux propriétés servent en permanence dans les preuves de ce thème : $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(|a|, |b|)$, et $\operatorname{pgcd}(m, 0) = |m|$ pour tout entier $m$. Toutes deux se lisent sur la définition : un entier et son opposé ont les mêmes diviseurs, d'où la première ; et tout entier divise $0$, donc les diviseurs communs de $m$ et de $0$ sont exactement les diviseurs de $m$, dont le plus grand vaut $|m|$ dès que $m \neq 0$, le cas $m = 0$ étant réglé par la convention ci-dessus. C'est cette seconde égalité qui fournit la valeur renvoyée par l'algorithme d'Euclide au moment où il s'arrête.

Propriété : pour tous $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$, $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, a \bmod b)$.
Démonstration : posons $r = a \bmod b$ et $q = a \,\mathrm{div}\, b$, de sorte que $a = bq + r$. Si $d$ divise $b$ et $r$, alors $d$ divise $bq + r = a$, donc $d$ est un diviseur commun de $a$ et $b$. Réciproquement, si $d$ divise $a$ et $b$, alors $d$ divise $a - bq = r$, donc $d$ est un diviseur commun de $b$ et $r$. Les deux couples ont donc exactement les mêmes diviseurs communs, donc le même plus grand. L'hypothèse $b \neq 0$ est indispensable : sans elle, $a \bmod b$ n'est pas défini, et c'est précisément pourquoi la boucle d'Euclide s'arrête quand le second argument s'annule.
C'est cette égalité, et elle seule, qui fait de l'algorithme d'Euclide un algorithme correct : elle dit que le couple change à chaque tour, mais que la quantité cherchée, elle, ne bouge pas.

Quand l'utiliser : dès qu'un énoncé demande un PGCD, une fraction irréductible, un test « ces deux entiers sont-ils premiers entre eux », ou sert de brique à Bézout. Le signal dans l'énoncé : deux entiers et le mot « diviseur commun », « irréductible » ou « étrangers ».
1) Écrire la spécification avant le code : ce que la fonction reçoit, ce qu'elle renvoie, sa précondition (voir le thème Python : structures de contrôle et fonctions pour le format de la docstring). Ici : « Renvoie le PGCD des entiers a et b », précondition « a et b sont des entiers ».
2) Ramener les arguments en valeur absolue, puisque $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(|a|, |b|)$ et que le reste de Python suit le signe du diviseur.
3) Écrire la boucle avec une affectation simultanée, jamais deux affectations successives : a, b = b, a % b.
4) Pour la terminaison, exhiber le variant : la valeur de b, entier naturel, qui décroît strictement à chaque tour puisque a % b est inférieur à b.
5) Pour la correction, exhiber l'invariant : « le PGCD du couple courant est celui du couple initial ». La méthode générale, variant puis invariant puis sortie de boucle, est celle du thème Algorithmes élémentaires et preuve de programmes ; on l'applique ici sans la redire. L'initialisation est immédiate, l'hérédité est exactement la propriété $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, a \bmod b)$.
6) Conclure en sortie de boucle : b vaut $0$, l'invariant donne $\operatorname{pgcd}(a, 0) = \operatorname{pgcd}(a_0, b_0)$, et $\operatorname{pgcd}(a, 0) = a$. C'est la ligne que les copies oublient : sans elle, on a prouvé qu'une quantité se conserve, pas que le programme renvoie le bon nombre.

Écrire une fonction pgcd(a, b) qui renvoie le PGCD de deux entiers, puis démontrer qu'elle termine et qu'elle renvoie bien $\operatorname{pgcd}(a, b)$.
Programme.

def pgcd(a, b):
    """Renvoie le PGCD des entiers a et b (un entier naturel).
    Precondition : a et b sont des entiers."""
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

Notations. Notons $a_0$ et $b_0$ les valeurs de a et b juste après la ligne des valeurs absolues, et, pour $k \geq 1$, $a_k$ et $b_k$ leurs valeurs après le $k$-ième tour de boucle, lorsque celui-ci a lieu. Par construction $a_0 = |a|$ et $b_0 = |b|$ sont des entiers naturels.
Terminaison. Posons $V_k = b_k$. Chaque $b_k$ est un entier naturel, comme reste d'une division par un entier strictement positif ou comme valeur absolue de départ. Si le tour $k+1$ a lieu, c'est que $b_k \neq 0$, donc $b_k \geq 1$ ; alors $b_{k+1} = a_k \bmod b_k$ vérifie $0 \leq b_{k+1} < b_k$ d'après la division euclidienne, donc $V_{k+1} < V_k$. La suite $(V_k)$ est une suite d'entiers naturels strictement décroissante tant que la boucle tourne : elle ne peut donc prendre qu'un nombre fini de valeurs, et la boucle s'arrête.
Correction. Considérons, pour chaque tour effectué $k$, la propriété $I_k$ : « $\operatorname{pgcd}(a_k, b_k) = \operatorname{pgcd}(a_0, b_0)$ ».
$I_0$ est vraie, les deux membres étant le même nombre.
Supposons $I_k$ vraie et le tour $k+1$ effectué. Alors $b_k \neq 0$, et l'affectation simultanée donne $a_{k+1} = b_k$ et $b_{k+1} = a_k \bmod b_k$.
D'après l'invariant du PGCD, applicable puisque $b_k \neq 0$, on a $\operatorname{pgcd}(b_k, a_k \bmod b_k) = \operatorname{pgcd}(a_k, b_k)$, donc $\operatorname{pgcd}(a_{k+1}, b_{k+1}) = \operatorname{pgcd}(a_k, b_k)$, qui vaut $\operatorname{pgcd}(a_0, b_0)$ par hypothèse de récurrence.
Donc $I_{k+1}$ est vraie, et par récurrence $I_k$ est vraie pour tout tour effectué.
Conclusion. Notons $K$ le nombre de tours effectués, fini d'après la terminaison. En sortie de boucle, $b_K = 0$, et $I_K$ donne $\operatorname{pgcd}(a_K, 0) = \operatorname{pgcd}(a_0, b_0)$. Or $\operatorname{pgcd}(m, 0) = m$ pour tout entier naturel $m$, donc la valeur renvoyée $a_K$ vaut $\operatorname{pgcd}(a_0, b_0)$, c'est-à-dire $\operatorname{pgcd}(|a|, |b|)$, c'est-à-dire $\operatorname{pgcd}(a, b)$.
Trace sur $a = 1071$ et $b = 462$ : les valeurs successives de b sont $462$, puis $147$, puis $21$, puis $0$, et la fonction renvoie $21$ après trois tours.
À retenir : une preuve de boucle se rédige en quatre blocs nommés, variant, initialisation, hérédité, sortie de boucle, et c'est la sortie de boucle qui transforme un invariant en valeur renvoyée.

Propriété : notons $r_0 = a$, $r_1 = b$ et $r_{k+2} = r_k \bmod r_{k+1}$ tant que $r_{k+1} \neq 0$, avec $a$ et $b$ entiers naturels et $b \geq 1$. Alors, pour tout $k \geq 1$ tel que $r_{k+2}$ soit défini, $r_{k+2} < \dfrac{r_k}{2}$. Il en résulte que le nombre de divisions euclidiennes effectuées est majoré par $2 \log_2(b) + 2$, donc que l'algorithme d'Euclide fait $O(\log(\min(|a|, |b|)))$ divisions.
La condition $k \geq 1$ n'est pas une coquetterie : si $a < b$, le tout premier tour se contente d'échanger les deux arguments, et l'on a $r_2 = a = r_0$. C'est à partir du rang $1$ que la suite des restes décroît strictement.
Théorème de Lamé (admis, hors programme du raisonnement demandé) : le pire cas est atteint par deux termes consécutifs de la suite de Fibonacci, et le nombre de divisions est alors majoré par cinq fois le nombre de chiffres décimaux du plus petit argument. Pour le couple $(610, 377)$, l'algorithme fait $13$ divisions, quand la majoration $2 \log_2(377) + 2$ en annonce au plus $19$.

Soient $a$ et $b$ deux entiers naturels avec $b \geq 1$. On pose $r_0 = a$, $r_1 = b$ et, tant que $r_{k+1} \neq 0$, $r_{k+2} = r_k \bmod r_{k+1}$. Montrer que pour tout $k \geq 1$ tel que $r_{k+2}$ soit défini, $r_{k+2} < \frac{r_k}{2}$, puis majorer le nombre de divisions effectuées par l'algorithme d'Euclide.
Soit $k \geq 1$ tel que $r_{k+2}$ soit défini ; en particulier $r_{k+1} \neq 0$ et $r_k \neq 0$.
Comme $k \geq 1$, l'entier $r_{k+1}$ est le reste de la division de $r_{k-1}$ par $r_k$, donc $r_{k+1} < r_k$.
Distinguons deux cas selon la position de $r_{k+1}$ par rapport à $\frac{r_k}{2}$.
Premier cas : $r_{k+1} \leq \frac{r_k}{2}$. Comme $r_{k+2}$ est le reste de la division de $r_k$ par $r_{k+1}$, on a $r_{k+2} < r_{k+1}$, donc $r_{k+2} < \frac{r_k}{2}$.
Second cas : $r_{k+1} > \frac{r_k}{2}$. Comme $r_{k+1} < r_k$, le quotient de $r_k$ par $r_{k+1}$ vaut exactement $1$, donc $r_{k+2} = r_k - r_{k+1}$. Or $r_{k+1} > \frac{r_k}{2}$, donc $r_k - r_{k+1} < r_k - \frac{r_k}{2} = \frac{r_k}{2}$, donc $r_{k+2} < \frac{r_k}{2}$.
Dans les deux cas $r_{k+2} < \frac{r_k}{2}$, ce qui établit la propriété annoncée.
Majoration du nombre de divisions. Notons $K$ le premier indice tel que $r_K = 0$ : la suite des restes est $r_0, r_1, \dots, r_K$, et le nombre de divisions effectuées est $K - 1$.
Montrons par récurrence sur $j \geq 1$ que $r_{1+2j} < \dfrac{b}{2^j}$ lorsque cet indice est défini. Pour $j = 1$, la propriété établie au rang $k = 1$ donne $r_3 < \frac{r_1}{2} = \frac{b}{2}$. Si $r_{1+2j} < \frac{b}{2^j}$, alors la propriété au rang $k = 1 + 2j$, qui est bien supérieur ou égal à $1$, donne $r_{3+2j} < \frac{r_{1+2j}}{2} < \frac{b}{2^{j+1}}$.
Si $K \leq 3$, il y a au plus deux divisions, et la majoration annoncée est vraie puisque $b \geq 1$.
Supposons $K \geq 4$ et posons $j = \left\lfloor \frac{K-2}{2} \right\rfloor$, de sorte que $j \geq 1$ et $1 + 2j \leq K - 1$.
L'indice $1 + 2j$ étant inférieur ou égal à $K - 1$, le reste $r_{1+2j}$ est non nul, donc $r_{1+2j} \geq 1$.
De $1 \leq r_{1+2j} < \frac{b}{2^j}$ on tire $2^j < b$, donc $j < \log_2(b)$.
Or $j \geq \frac{K-3}{2}$, donc $K - 3 \leq 2j < 2 \log_2(b)$, donc $K - 1 < 2 \log_2(b) + 2$ : l'algorithme d'Euclide effectue $O(\log b)$ divisions.
Vérification numérique : pour $a = 1071$ et $b = 462$, la majoration annonce au plus $19$ divisions, et l'algorithme en fait $3$ ; pour le pire cas $(610, 377)$, il en fait $13$.
À retenir : pour majorer le coût d'une boucle arithmétique, on cherche une quantité qui est divisée par un facteur fixe en un nombre borné de tours, et l'on passe au logarithme.

Écrire une version récursive de l'algorithme d'Euclide et démontrer sa correction.
Programme.

def pgcd_recursif(a, b):
    """Renvoie le PGCD des entiers naturels a et b.
    Precondition : a >= 0 et b >= 0."""
    if b == 0:
        return a
    return pgcd_recursif(b, a % b)

Terminaison. Le second argument est un entier naturel qui décroît strictement à chaque appel : si $b \neq 0$, l'appel suivant reçoit $a \bmod b$, qui vérifie $0 \leq a \bmod b < b$. Une suite strictement décroissante d'entiers naturels étant finie, la suite des appels s'arrête, nécessairement sur le cas de base $b = 0$.
Correction. Montrons par récurrence forte sur $b \in \mathbb{N}$ la propriété $P(b)$ : « pour tout $a \in \mathbb{N}$, l'appel pgcd_recursif(a, b) termine et renvoie $\operatorname{pgcd}(a, b)$ ».
Initialisation. Pour $b = 0$, le test b == 0 est vrai et la fonction renvoie $a$ ; or $\operatorname{pgcd}(a, 0) = a$ pour tout entier naturel $a$. Donc $P(0)$ est vraie.
Hérédité. Soit $b \geq 1$ ; supposons $P(c)$ vraie pour tout entier naturel $c < b$. Soit $a \in \mathbb{N}$. Comme $b \neq 0$, la fonction renvoie la valeur de pgcd_recursif(b, a % b). Or $a \bmod b$ est un entier naturel strictement inférieur à $b$, donc l'hypothèse de récurrence forte appliquée à $c = a \bmod b$ garantit que cet appel renvoie $\operatorname{pgcd}(b, a \bmod b)$.
D'après l'invariant du PGCD, $\operatorname{pgcd}(b, a \bmod b) = \operatorname{pgcd}(a, b)$, donc l'appel initial renvoie $\operatorname{pgcd}(a, b)$, et $P(b)$ est vraie.
Par récurrence forte, $P(b)$ est vraie pour tout $b \in \mathbb{N}$.
Profondeur de la pile. Le nombre d'appels emboîtés est le nombre de divisions, majoré par $2 \log_2(b) + 2$, et plus finement, par le théorème de Lamé, par cinq fois le nombre de chiffres décimaux de $b$. Pour $b$ de moins de $150$ chiffres, la profondeur reste donc sous $750$, en deçà de la limite de récursion par défaut de Python, qui vaut $1\,000$ et compte tous les appels déjà empilés (voir le thème Récursivité et diviser pour régner). Au-delà, la version récursive échoue là où la version itérative continue de tourner : pour deux termes consécutifs de la suite de Fibonacci dont le plus petit a trois cents chiffres, qui est le pire cas, l'algorithme demande jusqu'à $1\,436$ divisions et l'appel lève RecursionError. C'est un argument de plus en faveur de la boucle dès que les entiers sont de taille cryptographique.
À retenir : une fonction récursive se prouve par récurrence sur la quantité qui décroît, ici le second argument, et l'hypothèse de récurrence doit être forte parce que l'appel ne porte pas sur $b - 1$ mais sur un entier quelconque plus petit que $b$.

Ligne fautive :

def pgcd_faux(a, b):
    while b != 0:
        a = b
        b = a % b
    return a

La première ligne écrase a, si bien que la seconde calcule b % b, qui vaut toujours 0 : la boucle s'arrête après un unique tour et renvoie l'ancien b. Contre-exemple chiffré : cette version renvoie 8 pour pgcd(12, 8) au lieu de 4, et 462 pour pgcd(1071, 462) au lieu de 21. Le programme ne plante pas, il ne boucle pas non plus : il renvoie tranquillement un faux résultat, ce qui est le pire des trois.
Version correcte : a, b = b, a % b. En Python, le membre de droite est intégralement évalué avant toute affectation : le a utilisé dans a % b est bien l'ancien. Réflexe de relecture : dans une boucle qui fait tourner deux variables, l'échange s'écrit sur une seule ligne, ou bien il faut une variable temporaire.

Ligne fautive : une fonction pgcd sans la ligne a, b = abs(a), abs(b), au motif que « le reste est toujours positif ».
Il ne l'est pas : le reste de Python suit le signe du diviseur. Contre-exemple chiffré : avec a = 12 et b = -18, on a 12 % -18 qui vaut -6, puis -18 % -6 qui vaut 0, et la fonction renvoie -6 alors que le PGCD vaut 6. Avec a = -12 et b = 18, en revanche, elle renvoie 6 : le bogue ne se déclenche que si le diviseur devient négatif, donc il passe à travers un jeu de tests trop pauvre.
Version correcte : a, b = abs(a), abs(b) en première ligne, justifiée par $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(|a|, |b|)$, et une précondition explicite dans la docstring. Le jeu de tests doit contenir les quatre combinaisons de signes, et pas seulement deux entiers naturels (voir le thème Python : modules, fichiers et tests).

Théorème : pour tous $a, b \in \mathbb{Z}$, il existe $(u, v) \in \mathbb{Z}^2$ tel que $au + bv = \operatorname{pgcd}(a, b)$. Un tel couple $(u, v)$ s'appelle un couple de coefficients de Bézout de $a$ et $b$.
Corollaire : $a$ et $b$ sont premiers entre eux si et seulement s'il existe $(u, v) \in \mathbb{Z}^2$ tel que $au + bv = 1$. Le sens direct est le théorème ; la réciproque tient à ce que tout diviseur commun de $a$ et $b$ divise alors $1$.
Rappel hors ligne, en une phrase : ce théorème et ses conséquences (lemme de Gauss, caractérisation des entiers premiers entre eux) sont démontrés dans le thème Divisibilité, PGCD et Bézout dans Z, bloc Algèbre 3. Ce qui nous occupe ici est différent et strictement informatique : l'existence du couple ne dit pas comment le calculer, et c'est l'algorithme d'Euclide étendu qui le construit, en $O(\log(\min(|a|, |b|)))$ divisions.

Quand l'utiliser : quand l'énoncé demande non seulement le PGCD, mais aussi une écriture $au + bv = d$ : coefficients de Bézout, inverse modulaire, résolution d'une équation diophantienne, restes chinois. Le signal dans l'énoncé : les mots « déterminer un couple $(u, v)$ tel que », « inverse modulo », « résoudre dans $\mathbb{Z}^2$ ».
1) Écrire la spécification : « Renvoie un triplet (d, u, v) tel que d soit le PGCD de a et b et que a * u + b * v == d », précondition « a et b sont des entiers naturels non tous deux nuls ».
2) Faire porter la boucle non plus sur deux nombres, mais sur deux triplets $(r, u, v)$ et $(r', u', v')$, chacun accompagné de son écriture en fonction de $a$ et $b$.
3) Initialiser avec les deux écritures évidentes : $a = a \times 1 + b \times 0$ et $b = a \times 0 + b \times 1$, soit (r, u, v) = (a, 1, 0) et (r_suivant, u_suivant, v_suivant) = (b, 0, 1).
4) À chaque tour, calculer une seule fois le quotient q = r // r_suivant, puis appliquer la même combinaison aux trois composantes : le nouveau triplet est l'ancien second, et le second devient l'ancien premier moins q fois l'ancien second.
5) Énoncer l'invariant à deux volets : « $r = au + bv$ et $r' = au' + bv'$ », et « $\operatorname{pgcd}(r, r') = \operatorname{pgcd}(a, b)$ ». Le premier volet justifie l'égalité de Bézout, le second justifie que la valeur renvoyée est bien le PGCD.
6) Conclure en sortie de boucle : $r' = 0$, donc $r = \operatorname{pgcd}(r, 0) = \operatorname{pgcd}(a, b)$, et le premier volet donne $au + bv = r$.
7) Vérifier le résultat par le calcul a * u + b * v == d sur deux ou trois exemples : ce test coûte une ligne et attrape toutes les erreurs de recopie de la combinaison.

Écrire une fonction qui, pour deux entiers naturels a et b non tous deux nuls, renvoie un triplet (d, u, v) avec d le PGCD de a et b et a * u + b * v == d. Démontrer sa correction.
Programme.

def euclide_etendu(a, b):
    """Renvoie un triplet (d, u, v) tel que d = pgcd(a, b) et a * u + b * v = d.
    Precondition : a >= 0, b >= 0, a et b non tous deux nuls."""
    r, u, v = a, 1, 0
    r_suivant, u_suivant, v_suivant = b, 0, 1
    while r_suivant != 0:
        q = r // r_suivant
        r, r_suivant = r_suivant, r - q * r_suivant
        u, u_suivant = u_suivant, u - q * u_suivant
        v, v_suivant = v_suivant, v - q * v_suivant
    return r, u, v

Notations. Notons $(r_k, u_k, v_k)$ et $(r'_k, u'_k, v'_k)$ les valeurs des six variables après $k$ tours de boucle, avec $k = 0$ pour les valeurs initiales.
Terminaison. La suite $(r'_k)$ est une suite d'entiers naturels, et si le tour $k+1$ a lieu, $r'_{k+1} = r_k \bmod r'_k$ vérifie $0 \leq r'_{k+1} < r'_k$. C'est donc un variant, et la boucle s'arrête ; le nombre de tours est celui de l'algorithme d'Euclide ordinaire, majoré par $2 \log_2(b) + 2$.
Correction. Considérons la propriété $I_k$ : « $r_k = a u_k + b v_k$, $r'_k = a u'_k + b v'_k$ et $\operatorname{pgcd}(r_k, r'_k) = \operatorname{pgcd}(a, b)$ ».
Initialisation. On a $r_0 = a = a \times 1 + b \times 0$ et $r'_0 = b = a \times 0 + b \times 1$, et $\operatorname{pgcd}(r_0, r'_0) = \operatorname{pgcd}(a, b)$ : $I_0$ est vraie.
Hérédité. Supposons $I_k$ vraie et le tour $k+1$ effectué, donc $r'_k \neq 0$. Posons $q = r_k \,\mathrm{div}\, r'_k$. Les affectations donnent $r_{k+1} = r'_k$, $u_{k+1} = u'_k$, $v_{k+1} = v'_k$, ainsi que $r'_{k+1} = r_k - q r'_k$, $u'_{k+1} = u_k - q u'_k$ et $v'_{k+1} = v_k - q v'_k$.
La première écriture est acquise par hypothèse de récurrence, puisque $r_{k+1} = r'_k = a u'_k + b v'_k = a u_{k+1} + b v_{k+1}$.
Pour la seconde, on calcule $a u'_{k+1} + b v'_{k+1} = a(u_k - q u'_k) + b(v_k - q v'_k) = (a u_k + b v_k) - q (a u'_k + b v'_k) = r_k - q r'_k = r'_{k+1}$.
Enfin $r'_{k+1} = r_k \bmod r'_k$, donc l'invariant du PGCD donne $\operatorname{pgcd}(r_{k+1}, r'_{k+1}) = \operatorname{pgcd}(r'_k, r_k \bmod r'_k) = \operatorname{pgcd}(r_k, r'_k) = \operatorname{pgcd}(a, b)$.
Donc $I_{k+1}$ est vraie, et par récurrence $I_k$ l'est pour tout tour effectué.
Conclusion. Notons $K$ le nombre de tours. En sortie, $r'_K = 0$, donc $\operatorname{pgcd}(r_K, 0) = \operatorname{pgcd}(a, b)$, c'est-à-dire $r_K = \operatorname{pgcd}(a, b)$ puisque $r_K$ est un entier naturel. Le premier volet de $I_K$ donne alors $a u_K + b v_K = r_K = \operatorname{pgcd}(a, b)$ : le triplet renvoyé convient.
Trace sur $a = 240$ et $b = 46$. Les triplets successifs sont $(240, 1, 0)$ et $(46, 0, 1)$, puis, pour les quotients $5$, $4$, $1$, $1$ et $2$ : $(46, 0, 1)$ et $(10, 1, -5)$ ; $(10, 1, -5)$ et $(6, -4, 21)$ ; $(6, -4, 21)$ et $(4, 5, -26)$ ; $(4, 5, -26)$ et $(2, -9, 47)$ ; enfin $(2, -9, 47)$ et $(0, 23, -120)$. La fonction renvoie $(2, -9, 47)$, et l'on vérifie $240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2$.
À retenir : on ne calcule pas les coefficients de Bézout « à la remontée » sur une copie, on les transporte dans la boucle avec le reste, et l'invariant s'écrit comme deux égalités que le quotient $q$ combine à l'identique.

Écrire une version récursive de l'algorithme d'Euclide étendu et démontrer sa correction.
Programme.

def euclide_etendu_recursif(a, b):
    """Renvoie un triplet (d, u, v) tel que d = pgcd(a, b) et a * u + b * v = d.
    Precondition : a >= 0, b >= 0, a et b non tous deux nuls."""
    if b == 0:
        return a, 1, 0
    d, u, v = euclide_etendu_recursif(b, a % b)
    return d, v, u - (a // b) * v

D'où vient la dernière ligne. L'appel récursif fournit $d$, $u$ et $v$ tels que $b u + (a \bmod b) v = d$. Or $a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor b$, donc
$d = b u + \left(a - \left\lfloor \frac{a}{b} \right\rfloor b\right) v = a v + b \left(u - \left\lfloor \frac{a}{b} \right\rfloor v\right)$.
Les coefficients cherchés pour le couple $(a, b)$ sont donc $v$ et $u - \left\lfloor \frac{a}{b} \right\rfloor v$, dans cet ordre : ils s'obtiennent par échange puis correction, ce qui explique le return d, v, u - (a // b) * v.
Correction. Montrons par récurrence forte sur $b \in \mathbb{N}$ la propriété $P(b)$ : « pour tout $a \in \mathbb{N}$ avec $(a, b) \neq (0, 0)$, l'appel renvoie un triplet $(d, u, v)$ tel que $d = \operatorname{pgcd}(a, b)$ et $au + bv = d$ ».
Initialisation. Pour $b = 0$, la fonction renvoie $(a, 1, 0)$ ; or $\operatorname{pgcd}(a, 0) = a$ et $a \times 1 + 0 \times 0 = a$. Donc $P(0)$ est vraie.
Hérédité. Soit $b \geq 1$, et supposons $P(c)$ vraie pour tout entier naturel $c < b$. Soit $a \in \mathbb{N}$. Comme $a \bmod b$ est un entier naturel strictement inférieur à $b$, l'hypothèse de récurrence forte s'applique au couple $(b, a \bmod b)$ : l'appel récursif renvoie $(d, u, v)$ avec $d = \operatorname{pgcd}(b, a \bmod b)$ et $bu + (a \bmod b)v = d$.
D'une part, l'invariant du PGCD donne $d = \operatorname{pgcd}(b, a \bmod b) = \operatorname{pgcd}(a, b)$.
D'autre part, le calcul ci-dessus donne $a v + b\left(u - \left\lfloor \frac{a}{b} \right\rfloor v\right) = d$, qui est exactement l'égalité de Bézout pour le triplet renvoyé.
Donc $P(b)$ est vraie, et par récurrence forte elle l'est pour tout $b \in \mathbb{N}$.
Vérification numérique : euclide_etendu_recursif(240, 46) renvoie $(2, -9, 47)$, le même triplet que la version itérative.
À retenir : dans une version récursive, l'assemblage du résultat se démontre en réécrivant l'égalité rendue par l'appel plus petit en fonction des données de l'appel courant ; c'est ce calcul, et non l'intuition, qui dicte l'ordre des composantes du return.

Ligne fautive : « L'algorithme d'Euclide étendu renvoie le couple $(u, v)$ tel que $au + bv = d$, donc mon résultat doit être celui du corrigé. »
Il n'y a pas unicité. Si $(u_0, v_0)$ convient, alors pour tout $k \in \mathbb{Z}$ le couple $\left(u_0 + \frac{b}{d}k,\ v_0 - \frac{a}{d}k\right)$ convient aussi, car les deux termes ajoutés se compensent. Contre-exemple chiffré avec $a = 240$ et $b = 46$, dont le PGCD vaut $2$ : l'algorithme renvoie $(u, v) = (-9, 47)$, et l'on vérifie $240 \times (-9) + 46 \times 47 = 2$ ; mais $(14, -73)$ convient tout autant, puisque $240 \times 14 + 46 \times (-73) = 3360 - 3358 = 2$. Un jeu de tests qui compare le triplet renvoyé à une valeur écrite en dur rejettera donc une implémentation correcte.
Version correcte : tester la propriété, pas la valeur. On écrit d, u, v = euclide_etendu(a, b) puis on vérifie d == math.gcd(a, b) and a * u + b * v == d. Sur une copie, on écrit « un couple de coefficients de Bézout » et non « le couple », et l'on précise, si l'énoncé le demande, la contrainte supplémentaire qui rend le couple unique (par exemple $0 \leq u < \frac{b}{d}$).

Quand l'utiliser : l'énoncé demande de résoudre dans $\mathbb{Z}^2$ une équation du premier degré à deux inconnues entières, ou de décider si un montant est atteignable avec deux pas donnés. Le signal : « résoudre dans $\mathbb{Z}^2$ », « déterminer tous les couples d'entiers tels que ».
1) Calculer $d = \operatorname{pgcd}(a, b)$ et un couple $(u_0, v_0)$ tel que $a u_0 + b v_0 = d$, avec euclide_etendu(a, b).
2) Tester la condition d'existence : l'équation a des solutions si et seulement si $d$ divise $c$. Écrire la phrase sur la copie : « Comme $d \mid c$, l'équation admet des solutions » ou « Comme $d \nmid c$, elle n'en admet aucune », en justifiant par le fait que $d$ divise $au + bv$ pour tous entiers $u$ et $v$.
3) Construire une solution particulière en multipliant par $\frac{c}{d}$ : $\left(\frac{c}{d} u_0,\ \frac{c}{d} v_0\right)$.
4) Écrire l'ensemble des solutions : ce sont les couples $\left(\frac{c}{d}u_0 + \frac{b}{d}k,\ \frac{c}{d}v_0 - \frac{a}{d}k\right)$ pour $k \in \mathbb{Z}$. Ne pas oublier de diviser $a$ et $b$ par $d$ : sans cela on n'obtient qu'une partie des solutions.
5) En Python, renvoyer la solution particulière et le pas, pas une liste infinie : une fonction qui renvoie (c // d * u0, c // d * v0, b // d, a // d) décrit toute la famille. Le couple (u0, v0) rendu par euclide_etendu résout $au + bv = d$ et non $au + bv = c$ : c'est sa mise à l'échelle par $\frac{c}{d}$, celle de l'étape 3, qui est la solution particulière.
6) Vérifier sur deux valeurs de $k$ que l'égalité tient : le contrôle coûte une ligne et attrape l'oubli de la division par $d$.

Résoudre dans $\mathbb{Z}^2$ l'équation $240 u + 46 v = 6$.
Calcul du PGCD et d'un couple de Bézout. L'appel euclide_etendu(240, 46) renvoie $(2, -9, 47)$ : on a $\operatorname{pgcd}(240, 46) = 2$ et $240 \times (-9) + 46 \times 47 = 2$.
Existence. Tout entier de la forme $240u + 46v$ est divisible par $2$, puisque $2$ divise $240$ et $46$. Comme $2$ divise $6$, l'équation admet des solutions.
Solution particulière. En multipliant l'égalité de Bézout par $\frac{6}{2} = 3$, on obtient $240 \times (-27) + 46 \times 141 = 6$. Le couple $(u_0, v_0) = (-27, 141)$ est donc solution.
Analyse. Soit $(u, v) \in \mathbb{Z}^2$ une solution. En retranchant membre à membre les deux égalités, $240(u + 27) + 46(v - 141) = 0$, donc $120(u + 27) = -23(v - 141)$ après division par $2$.
Ainsi $23$ divise $120(u + 27)$. Or $\operatorname{pgcd}(23, 120) = 1$, donc, d'après le lemme de Gauss, $23$ divise $u + 27$ : il existe $k \in \mathbb{Z}$ tel que $u + 27 = 23k$, c'est-à-dire $u = -27 + 23k$.
En reportant, $120 \times 23 k = -23(v - 141)$, donc $v - 141 = -120k$, c'est-à-dire $v = 141 - 120k$.
Synthèse. Réciproquement, pour tout $k \in \mathbb{Z}$, $240(-27 + 23k) + 46(141 - 120k) = 6 + (240 \times 23 - 46 \times 120)k = 6 + (5520 - 5520)k = 6$, donc tous ces couples sont solutions.
Conclusion. L'ensemble des solutions est $\{(-27 + 23k,\ 141 - 120k) : k \in \mathbb{Z}\}$. Par exemple $k = 1$ donne $(-4, 21)$, et l'on vérifie $240 \times (-4) + 46 \times 21 = -960 + 966 = 6$.
À retenir : on écrit toujours les trois temps, existence par divisibilité du second membre, solution particulière par mise à l'échelle du couple de Bézout, puis analyse et synthèse pour la famille complète, dont le pas est $\frac{b}{d}$ et $-\frac{a}{d}$, jamais $b$ et $-a$.

Quand l'utiliser : l'énoncé demande « l'inverse de $a$ modulo $n$ », « résoudre $ax \equiv 1 \pmod{n}$ », ou fait apparaître une division dans $\mathbb{Z}/n\mathbb{Z}$, notamment en cryptographie. Le signal : une congruence à inverser, ou un exposant de déchiffrement à calculer.
1) Poser la question d'existence : $a$ est inversible modulo $n$ si et seulement si $\operatorname{pgcd}(a, n) = 1$. Le sens direct vient de ce que $ax - 1$ multiple de $n$ force tout diviseur commun de $a$ et $n$ à diviser $1$ ; la réciproque est le théorème de Bézout.
2) Appliquer euclide_etendu(a % n, n) pour obtenir $(d, u, v)$ avec $(a \bmod n)\, u + n v = d$. C'est bien $a \bmod n$, et non $a$, qui figure dans cette égalité : l'algorithme ne voit jamais $a$ lui-même, et l'écrire avec $a$ donne une égalité fausse dès que $a \geq n$.
3) Contrôler que $d$ vaut $1$, par une assertion qui fait échouer bruyamment le programme plutôt que de renvoyer un faux inverse.
4) Réduire : la relation $(a \bmod n)\, u + n v = 1$ donne $(a \bmod n)\, u \equiv 1 \pmod{n}$ ; comme $a$ et $a \bmod n$ sont congrus modulo $n$, on en tire $au \equiv 1 \pmod{n}$, donc u % n est l'inverse cherché dans $\{0, \dots, n-1\}$. La réduction finale n'est pas cosmétique : $u$ est souvent négatif.
5) Vérifier par a * x % n == 1, en une ligne, avant de se servir du résultat.

def inverse_modulaire(a, n):
    """Renvoie l'unique entier x de {0, ..., n - 1} tel que a * x % n == 1.
    Precondition : n >= 2 et pgcd(a % n, n) == 1."""
    d, u, _ = euclide_etendu(a % n, n)
    assert d == 1, "a n'est pas inversible modulo n"
    return u % n

Déterminer l'inverse de $17$ modulo $43$, en justifiant son existence et son unicité dans $\{0, \dots, 42\}$.
Existence. L'algorithme d'Euclide donne successivement $43 = 2 \times 17 + 9$, puis $17 = 1 \times 9 + 8$, puis $9 = 1 \times 8 + 1$, puis $8 = 8 \times 1 + 0$. Le dernier reste non nul vaut $1$, donc $\operatorname{pgcd}(17, 43) = 1$ et $17$ est inversible modulo $43$.
Coefficients de Bézout, par remontée. De la troisième égalité, $1 = 9 - 8$.
En remplaçant $8$ par $17 - 9$ tiré de la deuxième égalité, $1 = 9 - (17 - 9) = 2 \times 9 - 17$.
En remplaçant $9$ par $43 - 2 \times 17$ tiré de la première égalité, $1 = 2(43 - 2 \times 17) - 17 = 2 \times 43 - 5 \times 17$.
On a donc $17 \times (-5) + 43 \times 2 = 1$.
Réduction. De $17 \times (-5) \equiv 1 \pmod{43}$ et $-5 \equiv 38 \pmod{43}$, on tire $17 \times 38 \equiv 1 \pmod{43}$.
Vérification : $17 \times 38 = 646 = 43 \times 15 + 1$, donc $646 \equiv 1 \pmod{43}$.
Unicité. Si $x$ et $y$ appartiennent à $\{0, \dots, 42\}$ et vérifient $17x \equiv 17y \equiv 1 \pmod{43}$, alors $17(x - y) \equiv 0 \pmod{43}$, donc $43$ divise $17(x-y)$ ; comme $\operatorname{pgcd}(17, 43) = 1$, le lemme de Gauss donne que $43$ divise $x - y$. Or $|x - y| \leq 42 < 43$, donc $x = y$.
Conclusion. L'inverse de $17$ modulo $43$ est $38$.
Contrôle par le programme : euclide_etendu(17, 43) renvoie $(1, -5, 2)$, et inverse_modulaire(17, 43) renvoie $38$.
À retenir : la remontée d'Euclide sur une copie et la boucle sur les triplets en machine font le même calcul ; on rédige la remontée à la main et l'on vérifie que le programme donne le même couple, au multiple de $\frac{n}{d}$ près.