Uitgebreid Euclidisch algoritme

Het uitgebreide Euclidische algoritme is een algoritme om gehele getallen xxx en yyy te berekenen zodat

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

gegeven aaa en bbb.

Het bestaan van zulke gehele getallen wordt gegarandeerd door het lemma van Bézout.

Het uitgebreide algoritme van Euclides kan worden gezien als het reciproke van modulair exponentiëren.

Door de stappen in het algoritme van Euclides om te keren, is het mogelijk deze gehele getallen xxx en yyy te vinden. Het idee is om te beginnen met de GCD en recursief naar achteren te werken. Dit kan worden gedaan door de getallen als variabelen te behandelen tot we uiteindelijk een uitdrukking hebben die een lineaire combinatie is van onze begingetallen. We zullen dit doen met het voorbeeld dat we hierboven gebruikten.

We beginnen met onze GCD. We herschrijven het in termen van de vorige twee termen:

2=26-2×12.2 = 26 – 2 maal 12 .2=26-2×12.

Wij vervangen voor 121212 door onze vorige regel (38=1×26+12)(38 = 1 maal 26 + 12)(38=1×26+12) te nemen en te schrijven in termen van 12:

2=26-2×(38-1×26).2 = 26 – 2 maal (38 – 1 maal 26). 2=26-2×(38-1×26).

Volg de gelijke termen, de 262626’s, en we hebben

2=3×26-2×38.2 = 3 maal 26 – 2 maal 38. 2=3×26-2×38.

Herhaal het proces:

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

Het eindresultaat is ons antwoord:

2=3×102-8×38.

2=3×102-8×38.2 = 3 maal 102 – 8 maal 38.2=3×102-8×38.

Dus xxx en yyy zijn 333 en -8-8-8.

Vind twee gehele getallen aaa en bbb zo dat 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Gebruik eerst het algoritme van Euclides om de GCD te vinden:

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

Hieruit volgt dat de laatste niet nul rest (GCD) 292929 is.Nu gebruiken we het uitgebreide algoritme:

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

Substituerend voor 878787 in de eerste vergelijking, hebben we

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)maal (899 + (-7)maal 116) \\

Omdat we nu de GCD hebben geschreven als een lineaire combinatie van twee gehele getallen, beëindigen we het algoritme en concluderen

a=8,b=-17. □ a = 8, b =-17. \ □area=8,b=-17. □