Utökad euklidisk algoritm

Den utökade euklidiska algoritmen är en algoritm för att beräkna heltal xxx och yyy så att

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

givet aaa och bbb.

Existensen av sådana heltal garanteras av Bézouts lemma.

Den utvidgade euklidiska algoritmen kan ses som den modulära exponentieringens reciprok.

Genom att vända på stegen i den euklidiska algoritmen är det möjligt att hitta dessa heltal xxx och yyy. Hela idén är att börja med GCD och rekursivt arbeta sig bakåt. Detta kan göras genom att behandla talen som variabler tills vi får ett uttryck som är en linjär kombination av våra ursprungliga tal. Vi ska göra detta med det exempel vi använde ovan.

Vi börjar med vårt GCD. Vi skriver om det i termer av de två föregående termerna:

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

Vi ersätter för 12121212 genom att ta vår föregående rad (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12)(38=1×26+12) och skriva den i termer av 12:

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

Samla ihop likadana termer, 262626, och vi får

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

Upprepa processen:

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 slutliga resultatet är vårt svar:

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

Därmed är xxx och yyy 333 och -8-8-8-8.

Finn två heltal aaa och bbb så att 1914a+899b=gcd(1914,899).1914a+899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Använd först Euklids algoritm för att hitta GCD:

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.

Därav är den sista icke-noll återstoden (GCD) 292929.Nu använder vi den utökade algoritmen:

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.

Substituerar vi 878787 i den första ekvationen får 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)\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.

Då vi nu skrivit GCD som en linjär kombination av två heltal, avslutar vi algoritmen och drar slutsatsen

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