Algorithme euclidien étendu

L’algorithme euclidien étendu est un algorithme permettant de calculer des entiers xxx et yyy tels que

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

donné aaa et bbb.

L’existence de tels entiers est garantie par le lemme de Bézout.

L’algorithme euclidien étendu peut être vu comme l’inverse de l’exponentiation modulaire.

En inversant les étapes de l’algorithme euclidien, il est possible de trouver ces entiers xxx et yyy. L’idée est de commencer par le PGCD et de revenir en arrière de manière récursive. Pour ce faire, on peut traiter les nombres comme des variables jusqu’à ce que l’on obtienne une expression qui soit une combinaison linéaire de nos nombres initiaux. Nous allons le faire avec l’exemple que nous avons utilisé ci-dessus.

Nous commençons avec notre PGCD. Nous le réécrivons en fonction des deux termes précédents :

2=26-2×12.2 = 26 – 2 \times 12 .2=26-2×12.

Nous remplaçons pour 121212 en prenant notre ligne précédente (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12) et en l’écrivant en termes de 12 :

2=26-2×(38-1×26).2 = 26 – 2 \times (38 – 1 \times 26). 2=26-2×(38-1×26).

Recueillir les termes semblables, les 262626, et nous avons

2=3×26-2×38.2 = 3 \times 26 – 2 \times 38. 2=3×26-2×38.

Répétez le processus :

2=3×(102-2×38)-2×38.2 = 3 \times (102 – 2\times 38) – 2\times 38.2=3×(102-2×38)-2×38.

Le résultat final est notre réponse :

2=3×102-8×38.2 = 3 \times 102 – 8 \times 38.2=3×102-8×38.

Donc xxx et yyy sont 333 et -8-8-8.

Trouve deux entiers aaa et bbb tels que 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Premièrement, utilisez l’algorithme d’Euclide pour trouver le PGCD :

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\begin{aligned}1914 &= 2 \times 899 + 116 \899 &= 7 \times 116 + 87 \116 &= 1 \times 87 + 29 \87 &= 3 \times 29 + 0.\end{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

De ce fait, le dernier reste non nul (GCD) est 292929.Maintenant nous utilisons l’algorithme étendu :

29=116+(-1)×8787=899+(-7)×116.\begin{aligned} 29 &= 116 + (-1)\times 87\87 &= 899 + (-7)\times 116.\end{aligned}2987=116+(-1)×87=899+(-7)×116.

En remplaçant 878787 dans la première équation, on a

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\begin{aligned}29&= 116 + (-1)\times (899 + (-7)\times 116) \&= (-1)\times 899 + 8\times 116 \&= (-1)\times 899 + 8\times ( 1914 + (-2)\times 899 )\&= 8\times 1914 + (-17) \times 899 \\\&= 8\times 1914 – 17 \times 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Puisque nous avons maintenant écrit le PGCD comme une combinaison linéaire de deux entiers, nous terminons l’algorithme et concluons

a=8,b=-17. □ a = 8, b = 17. \N- ________ carréa=8, b=-17. □