Trouver [formule] tels que [formule].
Algorithme d'Euclide étendu.
L'algorithme d'Euclide étendu se pratique en deux temps : la descente, qui calcule le pgcd, puis la remontée, qui exprime ce pgcd. La remontée est la partie où l'on se trompe, parce qu'elle demande de substituer sans jamais calculer les produits — c'est le point sur lequel cette correction insiste. Pourquoi une solution existe. L'identité de Bézout affirme que pour [formule] non tous deux nuls, il existe [formule] entiers avec [formule]. Ici [formule] et [formule] sont premiers, distincts, donc [formule] : l'équation [formule] a bien des solutions, et l'algorithme va en produire une. La descente (Euclide). [formule] Le dernier reste non nul est [formule] : le pgcd vaut bien [formule]. La remontée. On repart de l'avant-dernière ligne et l'on substitue les restes en remontant, sans jamais effectuer les produits — c'est la règle qui évite l'erreur : [formule] D'où [formule] et [formule]. Contrôle : [formule]. ✓ Il y a une infinité de solutions. Si [formule] en est une, l'ensemble des solutions est [formule] puisque [formule]. Avec [formule] on obtient [formule], tout aussi valable. Dans le cas général [formule], le pas est [formule] et [formule]. L'usage principal : inverser modulo [formule]. Réduire [formule] modulo [formule] donne [formule], donc [formule] est l'inverse de [formule] dans [formule]. Contrôle : [formule]. ✓ C'est de cette façon qu'on inverse en pratique dans [formule] — bien plus vite que par le théorème d'Euler, qui demanderait de calculer [formule]. ⚠️ L'erreur classique est de calculer les produits pendant la remontée. Écrire [formule] puis remplacer [formule] par [formule] ne mène nulle part : on retombe sur des nombres, et la structure en combinaison de [formule] et [formule] est perdue. Il faut garder les expressions symboliques à chaque étape, c'est-à-dire écrire [formule] et non [formule]. Second point : le pgcd doit diviser le second membre, sinon il n'y a aucune solution — [formule] est insoluble puisque [formule] divise le membre de gauche. 💡 À retenir. Trois usages de Bézout. L'inversion modulaire, ci-dessus. Le lemme de Gauss : si [formule] et [formule], alors [formule] — démontré en multipliant [formule] par [formule]. Et la résolution des équations diophantiennes [formule], possibles si et seulement si [formule]. Le même algorithme fonctionne à l'identique dans [formule], qui est euclidien pour le degré.