Udvidet euklidisk algoritme

Den udvidede euklidiske algoritme er en algoritme til beregning af hele tal xxx og yyyyy, således at

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

givet aaa og bbb.

Eksistensen af sådanne heltal er garanteret af Bézout’s lemma.

Den udvidede euklidiske algoritme kan ses som det omvendte af modulær eksponering.

Gennem at vende trinene i den euklidiske algoritme om, er det muligt at finde disse heltal xxx og yyy. Hele idéen er at starte med GCD og rekursivt arbejde sig baglæns. Dette kan gøres ved at behandle tallene som variabler, indtil vi ender med et udtryk, der er en lineær kombination af vores udgangstal. Vi vil gøre dette med det eksempel, vi brugte ovenfor.

Vi starter med vores GCD. Vi omskriver det i form af de to foregående udtryk:

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

Vi erstatter for 12121212 ved at tage vores foregående linje (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12)(38=1×26+12) og skrive det i termer af 12:

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

Saml ens termer, 262626’erne, og vi får

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

Gentag processen igen:

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

Det endelige resultat er vores svar:

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

Så xxx og yyy er 333 og -8-8-8-8.

Find to hele tal aaa og bbb, således at 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Først skal du bruge Euklids algoritme til at finde GCD:

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

Deraf er den sidste rest, der ikke er nul (GCD), 29292929.Nu bruger vi den udvidede algoritme:

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.

Substituerer vi for 878787 i den første ligning, har vi

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)\ gange (899 + (-7)\ gange 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.

Da vi nu har skrevet GCD’en som en lineær kombination af to hele tal, afslutter vi algoritmen og konkluderer

a=8,b=-17. □ a = 8, b =-17. \ _\squarea=8,b=-17. □