Rozšířený euklidovský algoritmus

Rozšířený euklidovský algoritmus je algoritmus pro výpočet celých čísel xxx a yyy takových, že

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

dáno aaa a bbb.

Existenci takových celých čísel zaručuje Bézoutovo lemma.

Rozšířený euklidovský algoritmus lze považovat za reciproký modulární exponentizaci.

Obrácením kroků euklidovského algoritmu lze nalézt tato celá čísla xxx a yyy. Celá myšlenka spočívá v tom, že začneme s GCD a rekurzivně se propracujeme zpět. To lze provést tak, že s čísly budeme zacházet jako s proměnnými, dokud neskončíme s výrazem, který je lineární kombinací našich počátečních čísel. Uděláme to na příkladu, který jsme použili výše.

Začneme naším GCD. Přepíšeme jej v termínech předchozích dvou výrazů:

2=26-2×12.2 = 26 – 2 \krát 12 .2=26-2×12 .

Zaměníme za 121212 tak, že vezmeme náš předchozí řádek (38=1×26+12)(38 = 1 \krát 26 + 12)(38=1×26+12) a zapíšeme ho ve smyslu 12:

2=26-2×(38-1×26).2 = 26 – 2 \krát (38 – 1\krát 26). 2=26-2×(38-1×26).

Sbíráme podobné členy, 262626, a máme

2=3×26-2×38.2 = 3 \krát 26 – 2 \krát 38. 2=3×26-2×38.

Zopakujte postup:

2=3×(102-2×38)-2×38.2 = 3 \krát (102 – 2\krát 38) – 2\krát 38.2=3×(102-2×38)-2×38.

Konečný výsledek je naše odpověď:

2=3×102-8×38.2 = 3 \krát 102 – 8 \krát 38,2=3×102-8×38.

Takže xxx a yyy jsou 333 a -8-8-8.

Najděte dvě celá čísla aaa a bbb taková, že 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Nejprve použijte Euklidův algoritmus k nalezení GCD:

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

Z toho vyplývá, že poslední nenulový zbytek (GCD) je 292929.Nyní použijeme rozšířený algoritmus:

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.

Při dosazení 878787 do první rovnice máme

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{zarovnáno}29&= 116 + (-1)\krát (899 + (-7)\krát 116) \\&= (-1)\čas 899 + 8\čas 116 \\&= (-1)\čas 899 + 8\čas ( 1914 + (-2)\čas 899 )\\&= 8\čas 1914 + (-17) \čas 899 \\&= 8\čas 1914 – 17 \čas 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.

Protože jsme nyní zapsali GCD jako lineární kombinaci dvou celých čísel, ukončíme algoritmus a dojdeme k závěru

a=8,b=-17. □ a = 8, b =-17. \ _\kvadrátarea=8,b=-17. □