Kiterjesztett euklideszi algoritmus

A kiterjesztett euklideszi algoritmus egy olyan algoritmus xxx és yyy egész számok kiszámítására, hogy

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

adva aaa és bbb.

Az ilyen egész számok létezését Bézout lemma garantálja.

A kiterjesztett euklideszi algoritmus a moduláris exponenciálás reciprokának tekinthető.

Az euklideszi algoritmus lépéseinek megfordításával meg lehet találni ezeket az xxx és yyy egész számokat. Az egésznek az a lényege, hogy a GCD-vel kezdjük, és rekurzív módon visszafelé haladunk. Ezt úgy tehetjük meg, hogy a számokat változóként kezeljük, amíg végül egy olyan kifejezéshez jutunk, amely a kezdeti számok lineáris kombinációja. Ezt a fentebb használt példával fogjuk megtenni.

A GCD-vel kezdjük. Átírjuk az előző két kifejezésre:

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

Megváltjuk 121212-re úgy, hogy az előző sorunkat (38=1×26+12)(38 = 1 \szor 26 + 12)(38=1×26+12)(38=1×26+12) fogjuk, és 12-vel írjuk fel:

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

Vegyük össze a hasonló kifejezéseket, a 262626-okat, és megkapjuk

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

Ismételjük meg a folyamatot:

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

A végeredmény a válaszunk:

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

Az xxx és yyy tehát 333 és -8-8-8.

Keresünk két olyan egész számot aaa és bbb, hogy 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Először használjuk Euklidész algoritmusát a GCD megtalálásához:

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.

Ebből az utolsó nem nulla maradék (GCD) 29292929.Most használjuk a kiterjesztett algoritmust:

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.

A 878787-et az első egyenletbe behelyettesítve megkapjuk

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)\szor (899 + (-7)\szor 116) \\&= (-1)\idők 899 + 8\idők 116 \\\&= (-1)\idők 899 + 8\idők ( 1914 + (-2)\idők 899 )\\\&= 8\idők 1914 + (-17) \idők 899 \\\&= 8\idők 1914 – 17 \idők 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.

Mivel most a GCD-t két egész szám lineáris kombinációjaként írtuk fel, befejezzük az algoritmust, és megállapítjuk, hogy

a=8,b=-17. □ a = 8, b =-17. \ _\négyzeta=8,b=-17. □