Euklidovský algoritmus - Euclidean algorithm

Euklidova metoda pro nalezení největšího společného dělitele (GCD) dvou počátečních délek BA a DC, které jsou definovány jako násobky společné délky „jednotky“. Délka DC je kratší, používá se k „měření“ BA, ale pouze jednou, protože zbytek EA je menší než DC. EA nyní měří (dvakrát) kratší délku DC, se zbytkem FC kratším než EA. Poté FC měří (třikrát) délku EA. Protože zde není žádný zbytek, proces končí tím, že FC je GCD. Napravo Nicomachus Příklad s čísly 49 a 21, jehož výsledkem je jejich GCD 7 (odvozeno od Heatha 1908: 300).

v matematika, Euklidovský algoritmus,^{[poznámka 1]} nebo Euklidův algoritmus, je efektivní metoda pro výpočet největší společný dělitel (GCD) dvou celých čísel (čísel), což je největší číslo, které je rozděluje bez a zbytek. Je pojmenován podle starořečtiny matematik Euklid, který to poprvé popsal v jeho Elementy (c. 300 př. n. l.). Je to příklad algoritmus, podrobný postup provádění výpočtu podle dobře definovaných pravidel a je jedním z nejstarších běžně používaných algoritmů. Lze jej použít ke snížení zlomky jejich nejjednodušší forma, a je součástí mnoha dalších číselně teoretických a kryptografických výpočtů.

Euklidovský algoritmus je založen na principu, že největší společný dělitel dvou čísel se nezmění, pokud je větší číslo nahrazeno jeho rozdílem s menším číslem. Například 21 je GCD 252 a 105 (jako 252 = 21 × 12 a 105 = 21 × 5) a stejné číslo 21 je také GCD 105 a 252 - 105 = 147. Protože tato náhrada snižuje větší opakování tohoto procesu dává postupně menší dvojice čísel, dokud se obě čísla nestanou stejnými. Když k tomu dojde, jsou to GCD původních dvou čísel. Podle obrácení kroků nebo pomocí rozšířený euklidovský algoritmus, GCD lze vyjádřit jako a lineární kombinace ze dvou původních čísel, to je součet dvou čísel, každé vynásobené znakem celé číslo (například, 21 = 5 × 105 + (−2) × 252). Skutečnost, že GCD lze vždy vyjádřit tímto způsobem, je známá jako Bézoutova identita.

Verze výše popsaného euklidovského algoritmu (a Euklidova) může trvat mnoho kroků odčítání k nalezení GCD, když je jedno z daných čísel mnohem větší než druhé. Efektivnější verze algoritmu zkratky tyto kroky, místo toho nahradí větší ze dvou čísel jeho zbytkem při dělení menší ze dvou (s touto verzí se algoritmus zastaví při dosažení nulového zbytku). S tímto vylepšením algoritmus nikdy nevyžaduje více kroků než pětinásobek počtu číslic (základ 10) menšího celého čísla. To bylo prokázáno Gabriel Lamé v roce 1844 a znamená začátek roku teorie výpočetní složitosti. Další metody pro zlepšení účinnosti algoritmu byly vyvinuty ve 20. století.

Euklidovský algoritmus má mnoho teoretických i praktických aplikací. Používá se pro redukci zlomky jejich nejjednodušší forma a za provedení divize v modulární aritmetika. Výpočty využívající tento algoritmus jsou součástí kryptografické protokoly které se používají k zabezpečení Internet komunikace a způsoby rozbití těchto kryptosystémů pomocí factoring velkých složených čísel. K řešení lze použít euklidovský algoritmus Diophantine rovnice, jako je hledání čísel, která splňují více shody podle Čínská věta o zbytku, konstruovat pokračující zlomky a najít přesné racionální aproximace na reálná čísla. Nakonec může být použit jako základní nástroj pro dokazování vět v teorie čísel jako Lagrangeova věta o čtyřech čtvercích a jedinečnost hlavních faktorizací. Původní algoritmus byl popsán pouze pro přirozená čísla a geometrické délky (reálná čísla), ale algoritmus byl v 19. století zobecněn na jiné typy čísel, například Gaussova celá čísla a polynomy jedné proměnné. To vedlo k modernímu abstraktní algebraický pojmy jako Euklidovské domény.

Pozadí: největší společný dělitel

Euklidovský algoritmus vypočítá největšího společného dělitele (GCD) ze dvou přirozená čísla A a b. Největší společný dělitel G je největší přirozené číslo, které rozděluje obě A a b aniž by zbyl zbytek. Synonyma pro GCD zahrnují největší společný faktor (GCF) nejvyšší společný faktor (HCF) nejvyšší společný dělitel (HCD) a největší společné opatření (GCM). Největší společný dělitel se často píše jako gcd (A, b) nebo jednodušeji jako (A, b),^[1] ačkoli druhá notace je nejednoznačná, používá se také pro pojmy jako ideál v kruh celých čísel, který úzce souvisí s GCD.

Pokud gcd (A, b) = 1, tedy A a b se říká, že jsou coprime (nebo relativně prime).^[2] Tato vlastnost to neznamená A nebo b jsou sami sebou prvočísla.^[3] Například ani 6 ani 35 není prvočíslo, protože oba mají dva prvočíselné faktory: 6 = 2 × 3 a 35 = 5 × 7. Přesto jsou 6 a 35 coprime. Žádné přirozené číslo kromě 1 nerozdělí 6 a 35, protože nemají společné hlavní faktory.

Obdélník 24 x 60 je pokryt deseti čtvercovými dlaždicemi 12 x 12, kde 12 je GCD 24 a 60. Obecněji A-podle-b obdélník lze zakrýt čtvercovými dlaždicemi o délce strany C jen když C je společným dělitelem A a b.

Nechat G = gcd (A, b). Od té doby A a b jsou oba násobky G, lze je psát A = mg a b = ng, a neexistuje větší počet G > G pro které to platí. Přirozená čísla m a n musí být coprime, protože z něho by mohl být vyloučen jakýkoli společný faktor m a n dělat G větší. Tedy jakékoli jiné číslo C který rozděluje obojí A a b musí také rozdělit G. Největší společný dělitel G z A a b je jedinečný (pozitivní) společný dělitel A a b to je dělitelné jakýmkoli jiným společným dělitelem C.^[4]

GCD lze vizualizovat následujícím způsobem.^[5] Zvažte obdélníkovou oblast A podle ba jakýkoli společný dělitel C který rozděluje obojí A a b přesně. Strany obdélníku lze rozdělit na segmenty délky C, který rozděluje obdélník na mřížku čtverců délky strany C. Největší společný dělitel G je největší hodnota C pro které je to možné. Pro ilustraci lze obdélníkovou oblast 24 x 60 rozdělit na mřížku: čtverce 1 x 1, 2 x 2 čtverce, 3 x 3 čtverce, 4 x 4 čtverce, 6 x -6 čtverců nebo 12 x 12 čtverců. Proto je 12 největším společným dělitelem 24 a 60. Obdélníková oblast 24 x 60 může být rozdělena do mřížky čtverců 12 x 12, se dvěma čtverci podél jednoho okraje (24/12 = 2) a pěti čtverce podél druhé (60/12 = 5).

GCD dvou čísel A a b je součin hlavních faktorů sdílených dvěma čísly, kde lze použít stejný primární faktor vícekrát, ale pouze za předpokladu, že součin těchto faktorů rozděluje oba A a b.^[6] Například protože 1386 lze započítat do 2 × 3 × 3 × 7 × 11 a 3213 lze započítat do 3 × 3 × 3 × 7 × 17, největší společný dělitel 1386 a 3213 se rovná 63 = 3 × 3 × 7, produkt jejich sdílených hlavních faktorů. Pokud dvě čísla nemají společné hlavní faktory, jejich největší společný dělitel je 1 (zde se získá jako instance prázdný produkt ), jinými slovy, jsou coprime. Klíčovou výhodou euklidovského algoritmu je, že dokáže efektivně najít GCD, aniž by bylo nutné počítat hlavní faktory.^[7][8] Faktorizace velkých celých čísel se považuje za výpočetně velmi obtížný problém a bezpečnost mnoha široce používaných kryptografické protokoly je založen na jeho neproveditelnosti.^[9]

Jiná definice GCD je užitečná zejména v pokročilé matematice teorie prstenů.^[10] Největší společný dělitel G dvou nenulových čísel A a b je také jejich nejmenší kladná integrální lineární kombinace, tj. nejmenší kladné číslo formuláře ua + vb kde u a proti jsou celá čísla. Sada všech integrálních lineárních kombinací A a b je ve skutečnosti stejný jako množina všech násobků G (mg, kde m je celé číslo). V moderním matematickém jazyce ideál generováno uživatelem A a b je ideál generovanýG sám (ideál generovaný jediným prvkem se nazývá a hlavní ideál a všechny ideály celých čísel jsou hlavními ideály). Některé vlastnosti GCD jsou ve skutečnosti snadněji vidět s tímto popisem, například skutečnost, že jakýkoli společný dělitel A a b také rozděluje GCD (rozděluje obě podmínky ua + vb). Ekvivalence této definice GCD s ostatními definicemi je popsána níže.

GCD tří nebo více čísel se rovná součinu hlavních faktorů společných všem číslům,^[11] ale lze jej také vypočítat opakovaným odebíráním GCD dvojic čísel.^[12] Například,

gcd (A, b, C) = gcd (A, gcd (b, C)) = gcd (gcd (A, b), C) = gcd (gcd (A, C), b).

Euclidův algoritmus, který počítá GCD dvou celých čísel, tedy stačí k výpočtu GCD libovolně mnoha celých čísel.

Popis

Postup

Euklidovský algoritmus probíhá v sérii kroků, takže výstup každého kroku je použit jako vstup pro další. Nechat k být celé číslo, které počítá kroky algoritmu, počínaje nulou. Počáteční krok tedy odpovídá k = 0, další krok odpovídá k = 1 atd.

Každý krok začíná dvěma nezápornými zbytky r_k−1 a r_k−2. Vzhledem k tomu, že algoritmus zajišťuje, že se zbytky neustále snižují s každým krokem, r_k−1 je menší než jeho předchůdce r_k−2. Cílem kth step step is to find a kvocient q_k a zbytek r_k které splňují rovnici

${displaystyle r_ {k-2} = q_ {k} r_ {k-1} + r_ {k}}$

a které mají 0 ≤ r_k < r_k−1. Jinými slovy, násobky menšího počtu r_k−1 jsou odečteny od většího počtu r_k−2 až do konce r_k je menší než r_k−1.

V počátečním kroku (k = 0), zbytek r₋₂ a r₋₁ rovnat se A a b, čísla, pro která je hledána GCD. V dalším kroku (k = 1), zbytek stejný b a zbytek r₀ počátečního kroku atd. Algoritmus lze tedy zapsat jako posloupnost rovnic

${displaystyle {egin {aligned} a & = q_ {0} b + r_ {0} b & = q_ {1} r_ {0} + r_ {1} r_ {0} & = q_ {2} r_ {1} + r_ {2} r_ {1} & = q_ {3} r_ {2} + r_ {3} & ,,, vdots end {zarovnáno}}}$

Li A je menší než b, první krok algoritmu zamění čísla. Například pokud A < b, počáteční kvocient q₀ se rovná nule a zbytek r₀ je A. Tím pádem, r_k je menší než jeho předchůdce r_k−1 pro všechny k ≥ 0.

Protože zbytky se snižují s každým krokem, ale nikdy nemohou být záporné, zbytek r_N musí se nakonec rovnat nule, kdy se algoritmus zastaví.^[13] Poslední nenulový zbytek r_N−1 je největším společným dělitelem A a b. Číslo N nemůže být nekonečný, protože mezi počátečním zbytkem existuje pouze konečný počet nezáporných celých čísel r₀ a nula.

Doklad o platnosti

Platnost euklidovského algoritmu lze prokázat dvoustupňovým argumentem.^[14] V prvním kroku konečný nenulový zbytek r_N−1 je zobrazen, aby rozdělil oba A a b. Jelikož se jedná o společného dělitele, musí být menší nebo roven největšímu společnému děliteli G. Ve druhém kroku se ukazuje, že jakýkoli společný dělitel A a b, počítaje v to G, musí rozdělit r_N−1; proto, G musí být menší nebo rovno r_N−1. Tyto dva závěry jsou rozporuplné, pokud r_N−1 = G.

To prokázat r_N−1 rozděluje obě A a b (první krok), r_N−1 rozděluje jeho předchůdce r_N−2

r_N−2 = q_N r_N−1

od posledního zbytku r_N je nula. r_N−1 také dělí svého dalšího předchůdce r_N−3

r_N−3 = q_N−1 r_N−2 + r_N−1

protože rozděluje oba termíny na pravé straně rovnice. Opakující se stejný argument, r_N−1 rozděluje všechny předchozí zbytky, včetně A a b. Žádný z předchozích zbytků r_N−2, r_N−3atd. rozdělit A a b, protože zanechávají zbytek. Od té doby r_N−1 je společným dělitelem A a b, r_N−1 ≤ G.

Ve druhém kroku jakékoli přirozené číslo C který rozděluje obojí A a b (jinými slovy, jakýkoli společný dělitel A a b) rozděluje zbytky r_k. Podle definice, A a b lze napsat jako násobky C : A = mc a b = nc, kde m a n jsou přirozená čísla. Proto, C rozděluje počáteční zbytek r₀, od té doby r₀ = A − q₀b = mc − q₀nc = (m − q₀n)C. Obdobný argument to ukazuje C také rozděluje následující zbytky r₁, r₂atd. Proto největší společný dělitel G musí se rozdělit r_N−1, což z toho vyplývá G ≤ r_N−1. Protože první část argumentu ukázala opak (r_N−1 ≤ G), z toho vyplývá, že G = r_N−1. Tím pádem, G je největším společným dělitelem ze všech následujících párů:^[15][16]

G = gcd (A, b) = gcd (b, r₀) = gcd (r₀, r₁) =… = Gcd (r_N−2, r_N−1) = r_N−1.

Pracoval příklad

Animace euklidovského algoritmu založená na odčítání. Počáteční obdélník má rozměry A = 1071 a b = 462. V něm jsou umístěny čtverce o velikosti 462 × 462 a ponechávají obdélník 462 × 147. Tento obdélník je obložen čtverci 147 × 147, dokud není ponechán obdélník 21 × 147, který je zase obložen čtverci 21 × 21, takže nezůstává žádná nekrytá oblast. Nejmenší čtvercová velikost, 21, je GCD 1071 a 462.

Pro ilustraci lze použít euklidovský algoritmus k nalezení největšího společného dělitele A = 1071 a b = 462. Pro začátek se násobky 462 odečtou od 1071, dokud zbytek nebude menší než 462. Lze odečíst dva takové násobky (q₀ = 2), zbývající část 147:

1071 = 2 × 462 + 147.

Poté se odečtou násobky 147 od 462, dokud zbytek nebude menší než 147. Lze odečíst tři násobky (q₁ = 3), zbývající 21:

462 = 3 × 147 + 21.

Poté se od 147 odečtou násobky 21, dokud zbytek nebude menší než 21. Lze odečíst sedm násobků (q₂ = 7), nezůstane žádný zbytek:

147 = 7 × 21 + 0.

Protože poslední zbytek je nula, algoritmus končí 21 jako největší společný dělitel 1071 a 462. To souhlasí s gcd (1071, 462) nalezeným primární faktorizací výše. V tabulkové formě jsou tyto kroky:

Vizualizace

Euklidovský algoritmus lze vizualizovat z hlediska analogie obkladů uvedené výše pro největšího společného dělitele.^[17] Předpokládejme, že chceme pokrýt A-podle-b obdélník se čtvercovými dlaždicemi přesně, kde A je větší ze dvou čísel. Nejprve se pokusíme obložit obdélník pomocí b-podle-b čtvercové dlaždice; toto však ponechává r₀-podle-b zbylý obdélník až do konce, kde r₀ < b. Poté se pokusíme obložit zbytkový obdélník pomocí r₀-podle-r₀ čtvercové dlaždice. Tím zbývá druhý zbytkový obdélník r₁-podle-r₀, které se pokoušíme pomocí dlaždice r₁-podle-r₁ čtvercové dlaždice atd. Sekvence končí, když není žádný zbytkový obdélník, tj. Když čtvercové dlaždice přesně pokrývají předchozí zbytkový obdélník. Délka stran nejmenší čtvercové dlaždice je GCD rozměrů původního obdélníku. Například nejmenší čtvercová dlaždice na sousedním obrázku je 21 x 21 (zobrazeno červeně) a 21 je GCD 1071 a 462, což je rozměry původního obdélníku (zobrazeno zeleně).

Euklidovské dělení

Na každém kroku k, euklidovský algoritmus vypočítá kvocient q_k a zbytek r_k ze dvou čísel r_k−1 a r_k−2

r_k−2 = q_k r_k−1 + r_k

Kde r_k je nezáporný a je přísně menší než absolutní hodnota z r_k−1. Věta, která je základem definice Euklidovské dělení zajišťuje, že takový podíl a zbytek vždy existují a jsou jedinečné.^[18]

V Euklidově původní verzi algoritmu jsou kvocient a zbytek nalezeny opakovaným odečtením; to je r_k−1 je odečteno od r_k−2 opakovaně až do konce r_k je menší než r_k−1. Potom r_k a r_k−1 jsou vyměněny a proces je iterován. Euklidovské dělení redukuje všechny kroky mezi dvěma burzami na jeden krok, což je tedy efektivnější. Kromě toho nejsou kvocienty nutné, lze tedy nahradit euklidovské dělení znakem modulo provoz, což dává pouze zbytek. Tak se iterace euklidovského algoritmu stává jednoduše

r_k = r_k−2 mod r_k−1.

Implementace

Implementace algoritmu mohou být vyjádřeny v pseudo kód. Například verze založená na rozdělení může být naprogramováno tak jako^[19]

funkce gcd (a, b) zatímco b ≠ 0 t: = b b: = a mod b a: = t vrátit se A

Na začátku kth iterace, proměnná b drží poslední zbytek r_k−1, zatímco proměnná A drží svého předchůdce, r_k−2. Krok b := A mod b je ekvivalentní výše uvedenému vzorci rekurze r_k ≡ r_k−2 mod r_k−1. The dočasná proměnná t drží hodnotu r_k−1 zatímco další zbytek r_k se počítá. Na konci iterace smyčky proměnná b drží zbytek r_k, zatímco proměnná A drží svého předchůdce, r_k−1.

Ve verzi založené na odčítání, která byla původní verzí Euklida, je výpočet zbytku (b: = a mod b) je nahrazeno opakovaným odečtením.^[20] Na rozdíl od verze založené na dělení, která pracuje s libovolnými celými čísly jako vstupem, verze založená na odčítání předpokládá, že vstup se skládá z kladných celých čísel a zastaví se, když A = b:

funkce gcd (a, b) zatímco a ≠ b -li a> b a: = a - b jiný            b: = b - a vrátit se A

Proměnné A a b alternativní držení předchozích zbytků r_k−1 a r_k−2. Předpokládat, že A je větší než b na začátku iterace; pak A rovná se r_k−2, od té doby r_k−2 > r_k−1. Během iterace smyčky, A je snížena o násobky předchozího zbytku b dokud A je menší než b. Pak A je další zbytek r_k. Pak b je snížena o násobky A dokud nebude opět menší než A, dává další zbytek r_k+1, a tak dále.

Rekurzivní verze^[21] je založen na rovnosti GCD po sobě následujících zbytků a zastavovací podmínce gcd (r_N−1, 0) = r_N−1.

funkce gcd (a, b) -li b = 0 vrátit se A jiný        vrátit se gcd (b, a mod b)

Pro ilustraci se gcd (1071, 462) počítá z ekvivalentu gcd (462, 1071 mod 462) = gcd (462, 147). Druhá GCD se počítá z gcd (147, 462 mod 147) = gcd (147, 21), což se zase počítá z gcd (21, 147 mod 21) = gcd (21, 0) = 21.

Metoda nejméně absolutních zbytků

V jiné verzi Euklidova algoritmu se kvocient v každém kroku zvýší o jeden, pokud je výsledný záporný zbytek menší velikosti než typický kladný zbytek.^[22][23] Dříve rovnice

r_k−2 = q_k r_k−1 + r_k

předpokládal to |r_k−1| > r_k > 0. Alternativní negativní zbytek E_k lze vypočítat:

r_k−2 = (q_k + 1) r_k−1 + E_k

-li r_k−1 > 0 nebo

r_k−2 = (q_k − 1) r_k−1 + E_k

-li r_k−1 < 0.

Li r_k je nahrazen E_k. když |E_k| < |r_k|, pak jeden dostane variantu euklidovského algoritmu takovou

|r_k| ≤ |r_k−1| / 2

na každém kroku.

Leopold Kronecker ukázal, že tato verze vyžaduje nejméně kroků jakékoli verze Euclidova algoritmu.^[22][23] Obecněji se ukázalo, že pro každé vstupní číslo A a b, počet kroků je minimální právě tehdy q_k je vybrán tak, aby ${displaystyle left | {frac {r_ {k + 1}} {r_ {k}}} ight | <{frac {1} {varphi}} sim 0,618,}$ kde ${displaystyle varphi}$ je Zlatý řez.^[24]

Historický vývoj

Euklidovský algoritmus byl pravděpodobně vynalezen dříve Euklid, zde zobrazeno a kompas na malbě z roku 1474.

Euklidovský algoritmus je jedním z nejstarších běžně používaných algoritmů.^[25] Objevuje se v Euklidova Elementy (kolem 300 př. n. l.), konkrétně v knize 7 (propozice 1–2) a knize 10 (propozice 2–3). V knize 7 je algoritmus formulován pro celá čísla, zatímco v knize 10 je formulován pro délky úseček. (V moderním použití by se dalo říci, že to tam bylo formulováno pro reálná čísla. Ale délky, oblasti a objemy, představované v moderním použití jako reálná čísla, se neměřují ve stejných jednotkách a neexistuje přirozená jednotka délky, plochy nebo objemu; koncept reálných čísel nebyl v té době znám.) Druhý algoritmus je geometrický. GCD dvou délek A a b odpovídá největší délce G to měří A a b rovnoměrně; jinými slovy délky A a b jsou oba celočíselné násobky délky G.

Algoritmus pravděpodobně nebyl objeven Euklid, který sestavil výsledky z dřívějších matematiků v jeho Elementy.^[26][27] Matematik a historik B. L. van der Waerden naznačuje, že kniha VII pochází z učebnice o teorie čísel napsaný matematiky ve škole Pythagoras.^[28] Algoritmus pravděpodobně znal Eudoxus z Cnidus (asi 375 př. nl).^[25][29] Algoritmus může dokonce předcházet datu Eudoxus,^[30][31] soudě podle použití technického výrazu ἀνθυφαίρεσις (anthyphairesis, reciproční odečítání) v pracích Euklida a Aristotela.^[32]

O staletí později byl Euklidův algoritmus objeven nezávisle jak v Indii, tak v Číně,^[33] primárně řešit Diophantine rovnice které vznikly v astronomii a vytváření přesných kalendářů. Na konci 5. století, indický matematik a astronom Aryabhata popsal algoritmus jako „rozmělňovač“,^[34] snad kvůli jeho účinnosti při řešení diofantických rovnic.^[35] Ačkoli zvláštní případ Čínská věta o zbytku byly již popsány v čínské knize Sunzi Suanjing,^[36] obecné řešení zveřejnil Qin Jiushao ve své knize z roku 1247 Shushu Jiuzhang (數 書 九章 Matematické pojednání v devíti sekcích ).^[37] Nejprve byl popsán euklidovský algoritmus numericky a popularizován v Evropě ve druhém vydání Bachet Problèmes plaisants et délectables (Příjemné a příjemné problémy, 1624).^[34] V Evropě se také používal k řešení diofantických rovnic a při vývoji pokračující zlomky. The rozšířený euklidovský algoritmus byl publikován anglickým matematikem Nicholas Saunderson,^[38] kdo to připsal Roger Cotes jako metoda pro efektivní výpočet pokračujících zlomků.^[39]

V 19. století vedl euklidovský algoritmus k vývoji nových číselných systémů, jako např Gaussova celá čísla a Eisensteinova celá čísla. V roce 1815 Carl Gauss použil euklidovský algoritmus k prokázání jedinečné faktorizace Gaussova celá čísla, ačkoli jeho práce byla poprvé publikována v roce 1832.^[40] Gauss zmínil algoritmus ve svém Disquisitiones Arithmeticae (publikováno 1801), ale pouze jako metoda pro pokračující zlomky.^[33] Peter Gustav Lejeune Dirichlet Zdá se, že byl první, kdo popsal euklidovský algoritmus jako základ pro většinu teorie čísel.^[41] Lejeune Dirichlet poznamenal, že mnoho výsledků teorie čísel, jako je jedinečná faktorizace, by platilo pro jakýkoli jiný systém čísel, na který by mohl být použit euklidovský algoritmus.^[42] Lejeune Dirichlet přednášky o teorii čísel byly editovány a rozšířeny o Richard Dedekind, který ke studiu použil Euklidův algoritmus algebraická celá čísla, nový obecný typ čísla. Například Dedekind byl první, kdo to dokázal Fermatova věta o dvou čtvercích pomocí jedinečné faktorizace gaussovských celých čísel.^[43] Dedekind také definoval koncept a Euklidovská doména, číselný systém, ve kterém lze definovat zobecněnou verzi euklidovského algoritmu (jak je popsáno níže ). V závěrečných desetiletích 19. století byl euklidovský algoritmus postupně zastíněn Dedekindovou obecnější teorií ideály.^[44]

Další aplikace Euklidova algoritmu byly vyvinuty v 19. století. V roce 1829 Charles Sturm ukázal, že algoritmus byl užitečný v Sturmův řetěz metoda počítání skutečných kořenů polynomů v libovolném daném intervalu.^[45]

Euklidovský algoritmus byl první algoritmus celočíselného vztahu, což je metoda pro hledání celočíselných vztahů mezi odpovídajícími reálnými čísly. Několik románů celočíselné relační algoritmy byly vyvinuty, například algoritmus Helaman Ferguson a R.W. Forcade (1979)^[46] a Algoritmus LLL.^[47][48]

V roce 1969 vyvinuli Cole a Davie hru pro dva hráče založenou na euklidovském algoritmu Euklidova hra,^[49] který má optimální strategii.^[50] Hráči začínají dvěma hromadami A a b kameny. Hráči se střídají střídavě m násobky menší hromady od větší. Pokud se tedy skládají dvě hromádky X a y kameny, kde X je větší než y, další hráč může zmenšit větší hromádku z X kameny X − můj kameny, pokud je nezáporné celé číslo. Vítězem se stává první hráč, který sníží jednu hromádku na nulu.^[51][52]

Matematické aplikace

Bézoutova identita

Bézoutova identita uvádí, že největší společný dělitel G dvou celých čísel A a b lze reprezentovat jako lineární součet původních dvou čísel A a b.^[53] Jinými slovy, vždy je možné najít celá čísla s a t takhle G = sa + tb.^[54][55]

Celá čísla s a t lze vypočítat z kvocientů q₀, q₁atd. obrácením pořadí rovnic v Euklidově algoritmu.^[56] Počínaje předposlední rovnicí, G lze vyjádřit pomocí kvocientu q_N−1 a dva předchozí zbytky, r_N−2 a r_N−3:

G = r_N−1 = r_N−3 − q_N−1 r_N−2 .

Tyto dva zbytky lze rovněž vyjádřit jako jejich podíly a předchozí zbytky,

r_N−2 = r_N−4 − q_N−2 r_N−3 a

r_N−3 = r_N−5 − q_N−3 r_N−4 .

Nahrazení těchto vzorců pro r_N−2 a r_N−3 do první rovnice výnosy G jako lineární součet zbytků r_N−4 a r_N−5. Proces nahrazování zbytků vzorci zahrnujícími jejich předchůdce může pokračovat až do původních čísel A a b jsou dosaženy:

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = A − q₀ b.

Po všech ostatních r₀, r₁, atd. byly nahrazeny, vyjadřuje se konečná rovnice G jako lineární součet A a b: G = sa + tb. Bézoutova identita, a tedy předchozí algoritmus, lze oba zobecnit na kontext Euklidovské domény.

Hlavní ideály a související problémy

Bézoutova identita poskytuje ještě další definici největšího společného dělitele G dvou čísel A a b.^[10] Zvažte množinu všech čísel ua + vb, kde u a proti jsou libovolná dvě celá čísla. Od té doby A a b jsou oba dělitelné G, každé číslo v sadě je dělitelné G. Jinými slovy, každé číslo množiny je celočíselným násobkem G. To platí pro každého společného dělitele A a b. Na rozdíl od jiných společných dělitelů je však největším společným dělitelem člen množiny; podle Bézoutovy identity, výběr u = s a proti = t dává G. Menší společný dělitel nemůže být členem množiny, protože každý člen množiny musí být dělitelný G. Naopak jakýkoli násobek m z G lze získat výběrem u = slečna a proti = mt, kde s a t jsou celá čísla Bézoutovy identity. To lze vidět vynásobením Bézoutovy identity číslem m,

mg = msa + mtb.

Proto množina všech čísel ua + vb je ekvivalentní množině násobků m z G. Jinými slovy, množina všech možných součtů celočíselných násobků dvou čísel (A a b) je ekvivalentní množině násobků gcd (A, b). O GCD se říká, že je generátorem ideál z A a b. Tato definice GCD vedla k moderním abstraktní algebraický koncepty a hlavní ideál (ideál generovaný jediným prvkem) a hlavní ideální doména (A doména ve kterém je každý ideál hlavním ideálem).

Pomocí tohoto výsledku lze vyřešit určité problémy.^[57] Zvažte například dvě odměrky objemu A a b. Sčítáním / odčítáním u násobky prvního šálku a proti násobky druhého šálku, libovolný objem ua + vb lze měřit. Všechny tyto objemy jsou násobky G = gcd (A, b).

Rozšířený euklidovský algoritmus

Celá čísla s a t Bézoutovy identity lze efektivně vypočítat pomocí rozšířený euklidovský algoritmus. Toto rozšíření přidává do Euklidova algoritmu dvě rekurzivní rovnice^[58]

s_k = s_k−2 − q_ks_k−1

t_k = t_k−2 − q_kt_k−1

s počátečními hodnotami

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1.

Pomocí této rekurze jsou Bézoutova celá čísla s a t jsou dány s = s_N a t = t_N, kde N + 1 je krok, kterým algoritmus končí r_{N + 1} = 0.

Platnost tohoto přístupu lze ukázat indukcí. Předpokládejme, že vzorec rekurze je správný až po krok k - 1 algoritmu; jinými slovy, předpokládejme to

r_j = s_j A + t_j b

pro všechny j méně než k. The kTřetím krokem algoritmu je rovnice

r_k = r_k−2 − q_kr_k−1.

Vzhledem k tomu, že se předpokládá, že vzorec rekurze je správný pro r_k−2 a r_k−1, mohou být vyjádřeny jako odpovídající s a t proměnné

r_k = (s_k−2 A + t_k−2 b) − q_k(s_k−1 A + t_k−1 b).

Přeskupením této rovnice se získá rekurzní vzorec pro krok k, podle potřeby

r_k = s_k A + t_k b = (s_k−2 − q_ks_k−1) A + (t_k−2 − q_kt_k−1) b.

Maticová metoda

Celá čísla s a t lze také najít pomocí ekvivalentu matice metoda.^[59] Posloupnost rovnic Euklidova algoritmu

${displaystyle {egin {aligned} a & = q_ {0} b + r_ {0} b & = q_ {1} r_ {0} + r_ {1} & ,,, vdots r_ {N-2} & = q_ {N} r_ {N-1} + 0end {zarovnáno}}}$

lze zapsat jako součin kvocientových matic 2 ku 2, které vynásobí dvourozměrný zbytek vektoru

${displaystyle {egin {pmatrix} a bend {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} b r_ {0} end {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} q_ {1} & 1 1 & 0end {pmatrix}} {egin {pmatrix} r_ {0} r_ {1} end {pmatrix}} = cdots = prod _ {i = 0} ^ {N} {egin {pmatrix} q_ {i} & 1 1 & 0end {pmatrix}} {egin {pmatrix} r_ {N-1} 0end {pmatrix}} ,.}$

Nechat M představují součin všech kvocientových matic

${displaystyle mathbf {M} = {egin {pmatrix} m_ {11} & m_ {12} m_ {21} & m_ {22} end {pmatrix}} = prod _ {i = 0} ^ {N} {egin {pmatrix } q_ {i} & 1 1 & 0end {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} q_ {1} & 1 1 & 0end {pmatrix}} cdots {egin {pmatrix } q_ {N} & 1 1 a 0end {pmatrix}} ,.}$

To zjednodušuje euklidovský algoritmus do formy

${displaystyle {egin {pmatrix} a bend {pmatrix}} = mathbf {M} {egin {pmatrix} r_ {N-1} 0end {pmatrix}} = mathbf {M} {egin {pmatrix} g 0end { pmatrix}} ,.}$

Vyjádřit G jako lineární součet A a b, obě strany této rovnice lze vynásobit inverzní matice M.^[59][60] The určující z M rovná se (-1)^N+1, protože se rovná součinu determinantů matice kvocientů, z nichž každá je záporná. Protože determinant M není nikdy nula, vektor konečných zbytků lze vyřešit pomocí inverzní funkce k M

${displaystyle {egin {pmatrix} g 0end {pmatrix}} = mathbf {M} ^ {- 1} {egin {pmatrix} a bend {pmatrix}} = (- 1) ^ {N + 1} {egin { pmatrix} m_ {22} & - m_ {12} - m_ {21} & m_ {11} end {pmatrix}} {egin {pmatrix} a bend {pmatrix}} ,.}$

Protože horní rovnice dává

G = (−1)^N+1 ( m₂₂ A − m₁₂ b),

dvě celá čísla Bézoutovy identity jsou s = (−1)^N+1m₂₂ a t = (−1)^Nm₁₂. Metoda matice je stejně účinná jako ekvivalentní rekurze, se dvěma násobeními a dvěma sčítáním na krok euklidovského algoritmu.

Euklidovo lemma a jedinečná faktorizace

Bézoutova identita je nezbytná pro mnoho aplikací Euklidova algoritmu, například pro demonstraci jedinečná faktorizace čísel do hlavních faktorů.^[61] Pro ilustraci předpokládejme, že číslo L lze napsat jako součin dvou faktorů u a proti, to znamená, L = uv. Pokud jiné číslo w také rozděluje L ale je coprime s u, pak w musí se rozdělit proti, následujícím argumentem: Pokud je největším společným dělitelem u a w je 1, pak celá čísla s a t lze najít takové, že

1 = su + tw .

podle Bézoutovy identity. Vynásobením obou stran proti dává vztah

proti = suv + twv = sL + twv .

Od té doby w rozdělí oba termíny na pravé straně, musí také rozdělit levou stranu, proti. Tento výsledek je znám jako Euklidovo lemma.^[62] Konkrétně, pokud se prvočíslo rozdělí L, pak musí rozdělit alespoň jeden faktor z L. Naopak, pokud číslo w je coprime na každé z řady čísel A₁, A₂, ..., A_n, pak w je také coprime k jejich produktu, A₁ × A₂ × ... × A_n.^[62]

Euklidovo lemma stačí k prokázání, že každé číslo má jedinečnou faktorizaci na prvočísla.^[63] Abychom to viděli, předpokládejme naopak, že existují dvě nezávislé faktorizace L do m a n hlavní faktory

L = p₁p₂…p_m = q₁q₂…q_n .

Protože každý prime p rozděluje L podle předpokladu musí také rozdělit jednu z q faktory; od každého q je také prime, musí to být tak p = q. Iterativně dělení p faktory ukazují, že každý p má stejný protějšek q; dvě hlavní faktorizace jsou identické kromě jejich pořadí. Jedinečná faktorizace čísel na prvočísla má mnoho aplikací v matematických důkazech, jak je uvedeno níže.

Lineární diofantické rovnice

Spiknutí lineárního Diophantine rovnice, 9X + 12y = 483. Řešení jsou zobrazena jako modré kruhy.

Diophantine rovnice jsou rovnice, ve kterých jsou řešení omezena na celá čísla; jsou pojmenovány podle alexandrijského matematika 3. století Diophantus.^[64] Typický lineární Diophantine rovnice hledá celá čísla X a y takhle^[65]

sekera + podle = C

kde A, b a C jsou uvedena celá čísla. To lze napsat jako rovnici pro X v modulární aritmetika:

sekera ≡ C mod b.

Nechat G být největším společným dělitelem A a b. Oba termíny v sekera + podle jsou dělitelné G; proto, C musí být také dělitelné Gnebo rovnice nemá řešení. Vydělením obou stran C/G, lze rovnici zredukovat na Bezoutovu identitu

sa + tb = G

kde s a t lze najít na rozšířený euklidovský algoritmus.^[66] To poskytuje jedno řešení diofantické rovnice, X₁ = s (C/G) a y₁ = t (C/G).

Obecně platí, že lineární diofantická rovnice nemá řešení nebo nekonečný počet řešení.^[67] Chcete-li najít to druhé, zvažte dvě řešení, (X₁, y₁) a (X₂, y₂), kde

sekera₁ + podle₁ = C = sekera₂ + podle₂

nebo ekvivalentně

A(X₁ − X₂) = b(y₂ − y₁).

Proto je nejmenší rozdíl mezi dvěma X řešení je b/G, zatímco nejmenší rozdíl mezi dvěma y řešení je A/G. Řešení tedy lze vyjádřit jako

X = X₁ − bu/G

y = y₁ + au/G.

Povolením u pro změnu ve všech možných celých číslech lze z jednoho řešení vygenerovat nekonečnou rodinu řešení (X₁, y₁). Je-li požadováno řešení pozitivní celá čísla (X > 0, y > 0), je možný pouze konečný počet řešení. Toto omezení přijatelných řešení umožňuje, aby některé systémy Diophantinových rovnic s více neznámými než rovnic měly konečný počet řešení;^[68] to je nemožné pro soustava lineárních rovnic když řešení mohou být jakákoli reálné číslo (vidět Podurčený systém ).

Multiplikativní inverze a algoritmus RSA

A konečné pole je sada čísel se čtyřmi zobecněnými operacemi. Operace se nazývají sčítání, odčítání, násobení a dělení a mají své obvyklé vlastnosti, například komutativita, asociativita a distribučnost. Příkladem konečného pole je sada 13 čísel {0, 1, 2, ..., 12} pomocí modulární aritmetika. V tomto poli jsou sníženy výsledky jakékoli matematické operace (sčítání, odčítání, násobení nebo dělení) modulo 13; to znamená, že se násobky 13 sčítají nebo odečítají, dokud se výsledek nedostane do rozsahu 0–12. Například výsledek 5 × 7 = 35 mod 13 = 9. Taková konečná pole lze definovat pro libovolné prvočíslo p; pomocí propracovanějších definic je lze definovat také pro jakoukoli moc m prvočísla p ^m. Konečná pole se často nazývají Galois pole a jsou zkrácena jako GF (p) nebo GF (p ^m).

V takové oblasti s m čísla, každý nenulový prvek A má jedinečný modulární multiplikativní inverzní, A⁻¹ takhle aa⁻¹ = A⁻¹A ≡ 1 modm. Tuto inverzi lze najít řešením rovnice kongruence sekera ≡ 1 modm,^[69] nebo ekvivalentní lineární diofantická rovnice^[70]

sekera + můj = 1.

Tuto rovnici lze vyřešit euklidovským algoritmem, jak je popsáno výše. Hledání multiplikativních inverzí je zásadním krokem v Algoritmus RSA, který je široce používán v elektronický obchod; konkrétně rovnice určuje celé číslo použité k dešifrování zprávy.^[71] Ačkoli používá algoritmus RSA prsteny spíše než pole lze euklidovský algoritmus stále použít k nalezení multiplikativní inverze tam, kde existuje. Algoritmus Euclidean má také další aplikace v kódy opravující chyby; například jej lze použít jako alternativu k Algoritmus Berlekamp – Massey pro dekódování BCH a Reed-Solomon kódy, které jsou založeny na polích Galois.^[72]

Čínská věta o zbytku

Euklidův algoritmus lze také použít k řešení více lineárních diofantických rovnic.^[73] Takové rovnice vznikají v Čínská věta o zbytku, který popisuje novou metodu reprezentující celé číslo X. Místo reprezentace celého čísla podle jeho číslic může být reprezentováno jeho zbytky X_i modulo soubor N coprime čísla m_i:^[74]

${displaystyle {egin {aligned} x_ {1} & equiv x {pmod {m_ {1}}} x_ {2} & equiv x {pmod {m_ {2}}} & ,,, vdots x_ {N} & equiv x {pmod {m_ {N}}} ,. konec {zarovnáno}}}$

Cílem je určit X od jeho N zbytky X_i. Řešením je kombinovat více rovnic do jedné lineární diofantické rovnice s mnohem větším modulem M to je produkt všech jednotlivých modulů m_ia definovat M_i tak jako

${displaystyle M_ {i} = {frac {M} {m_ {i}}}.}$

Tedy každý M_i je produktem všech modulů až na m_i. Řešení závisí na nalezení N nová čísla h_i takhle

${displaystyle M_ {i} h_ {i} ekvivalent 1 {pmod {m_ {i}}},}}$

S těmito čísly h_i, jakékoli celé číslo X lze ze zbytků rekonstruovat X_i podle rovnice

${displaystyle xequiv (x_ {1} M_ {1} h_ {1} + x_ {2} M_ {2} h_ {2} + cdots + x_ {N} M_ {N} h_ {N}) {pmod {M} } ,.}$

Protože tato čísla h_i jsou multiplikativní inverzní inverze M_i, they may be found using Euclid's algorithm as described in the previous subsection.

Stern – Brocotův strom

The Euclidean algorithm can be used to arrange the set of all positive racionální čísla into an infinite binární vyhledávací strom, nazvaný Stern – Brocotův strom.The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number A/b can be found by computing gcd(A,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether A/b is given in lowest terms, and forms a path from the root to a node containing the number A/b.^[75] This fact can be used to prove that each positive rational number appears exactly once in this tree.

For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:

The Stern–Brocot tree, and the Stern–Brocot sequences of order i pro i = 1, 2, 3, 4

${displaystyle { egin{aligned}&gcd(3,4)&leftarrow ={}&gcd(3,1)&ightarrow ={}&gcd(2,1)&ightarrow ={}&gcd(1,1).end{aligned}}}$

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the Calkin–Wilf tree. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.

Pokračující zlomky

The Euclidean algorithm has a close relationship with pokračující zlomky.^[76] The sequence of equations can be written in the form

${displaystyle { egin{aligned}{frac {a}{b}}&=q_{0}+{frac {r_{0}}{b}}{frac {b}{r_{0}}}&=q_{1}+{frac {r_{1}}{r_{0}}}{frac {r_{0}}{r_{1}}}&=q_{2}+{frac {r_{2}}{r_{1}}}&,,,vdots {frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{frac {r_{k}}{r_{k-1}}}&,,,vdots {frac {r_{N-2}}{r_{N-1}}}&=q_{N},.end{aligned}}}$

The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form

${displaystyle {frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {r_{1}}{r_{0}}}}},.}$

The third equation may be used to substitute the denominator term r₁/r₀, poddajný

${displaystyle {frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {r_{2}}{r_{1}}}}}}},.}$

The final ratio of remainders r_k/r_k−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction

${displaystyle {frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {1}{ddots +{cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},ldots ,q_{N}],.}$

In the worked example výše, the gcd(1071, 462) was calculated, and the quotients q_k were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written

${displaystyle {frac {1071}{462}}=2+{cfrac {1}{3+{cfrac {1}{7}}}}=[2;3,7]}$

as can be confirmed by calculation.

Factorization algorithms

Calculating a greatest common divisor is an essential step in several celočíselná faktorizace algorithms,^[77] jako Pollardův rho algoritmus,^[78] Shorův algoritmus,^[79] Dixonova faktorizační metoda^[80] a Faktorizace eliptické křivky Lenstra.^[81] The Euclidean algorithm may be used to find this GCD efficiently. Pokračující zlomková faktorizace uses continued fractions, which are determined using Euclid's algorithm.^[82]

Algoritmická účinnost

Number of steps in the Euclidean algorithm for gcd(X,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, kde Φ je Zlatý řez.

The computational efficiency of Euclid's algorithm has been studied thoroughly.^[83] This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to A. A. L. Reynaud in 1811,^[84] who showed that the number of division steps on input (u, proti) is bounded by proti; later he improved this to proti/2 + 2. Later, in 1841, P. J. E. Finck ukázal^[85] that the number of division steps is at most 2 log₂ proti + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input.^[86] Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacciho čísla.^[86] Finck's analysis was refined by Gabriel Lamé in 1844,^[87] who showed that the number of steps required for completion is never more than five times the number h of base-10 digits of the smaller number b.^[88][89]

V uniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes konstantní čas, and Lamé's analysis implies that the total running time is also Ó(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as Ó(h²).^[90] In this case the total time for all of the steps of the algorithm can be analyzed using a telescoping series, showing that it is also Ó(h²). Modern algorithmic techniques based on the Schönhage – Strassenův algoritmus for fast integer multiplication can be used to speed this up, leading to quasilinear algorithms for the GCD.^[91][92]

Number of steps

The number of steps to calculate the GCD of two natural numbers, A a b, may be denoted by T(A, b).^[93] Li G is the GCD of A a b, pak A = mg a b = ng for two coprime numbers m a n. Pak

T(A, b) = T(m, n)

as may be seen by dividing all the steps in the Euclidean algorithm by G.^[94] By the same argument, the number of steps remains the same if A a b are multiplied by a common factor w: T(A, b) = T(wa, wb). Therefore, the number of steps T may vary dramatically between neighboring pairs of numbers, such as T(A, b) and T(A, b + 1), depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

T(A, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

kde T(X, 0) = 0 by assumption.^[93]

Nejhorší případ

If the Euclidean algorithm requires N steps for a pair of natural numbers A > b > 0, the smallest values of A a b for which this is true are the Fibonacciho čísla F_N+2 a F_N+1, resp.^[95] More precisely, if the Euclidean algorithm requires N steps for the pair A > b, pak jeden má A ≥ F_N+2 a b ≥ F_N+1. This can be shown by indukce.^[96] Li N = 1, b rozděluje A with no remainder; the smallest natural numbers for which this is true is b = 1 a A = 2, which are F₂ a F₃, resp. Now assume that the result holds for all values of N až do M − 1. The first step of the M-step algorithm is A = q₀b + r₀, and the Euclidean algorithm requires M − 1 steps for the pair b > r₀. By induction hypothesis, one has b ≥ F_M+1 a r₀ ≥ F_M. Proto, A = q₀b + r₀ ≥ b + r₀ ≥ F_M+1 + F_M = F_M+2,which is the desired inequality.This proof, published by Gabriel Lamé in 1844, represents the beginning of teorie výpočetní složitosti,^[97] and also the first practical application of the Fibonacci numbers.^[95]

This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).^[98] For if the algorithm requires N steps, then b is greater than or equal to F_N+1 which in turn is greater than or equal to φ^N−1, kde φ je Zlatý řez. Od té doby b ≥ φ^N−1, pak N − 1 ≤ log_φb. Since log₁₀φ > 1/5, (N − 1)/5 < log₁₀φ log_φb = log₁₀b. Tím pádem, N ≤ 5 log₁₀b. Thus, the Euclidean algorithm always needs less than Ó(h) divisions, where h is the number of digits in the smaller number b.

Průměrný

The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T(A) required to calculate the GCD of a given number A and a smaller natural number b chosen with equal probability from the integers 0 to A − 1^[93]

${displaystyle T(a)={frac {1}{a}}sum _{0leq b$

Nicméně od té doby T(A, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(A) is likewise "noisy".^[99]

To reduce this noise, a second average τ(A) is taken over all numbers coprime with A

${displaystyle au (a)={frac {1}{varphi (a)}}sum _{ egin{smallmatrix}0leq b$

Existují φ(A) coprime integers less than A, kde φ je Eulerova totientová funkce. This tau average grows smoothly with A^[100][101]

${displaystyle au (a)={frac {12}{pi ^{2}}}ln 2ln a+C+O(a^{-1/6-varepsilon })}$

with the residual error being of order A^{−(1/6) + ε}, kde ε je infinitezimální. Konstanta C (Porter's Constant^[102]) in this formula equals

${displaystyle C=-{frac {1}{2}}+{frac {6ln 2}{pi ^{2}}}left(4gamma -{frac {24}{pi ^{2}}}zeta '(2)+3ln 2-2ight)approx 1.467}$

kde y je Euler – Mascheroniho konstanta and ζ' is the derivát z Funkce Riemann zeta.^[103][104] The leading coefficient (12/π²) ln 2 was determined by two independent methods.^[105][106]

Since the first average can be calculated from the tau average by summing over the divisors d zA^[107]

${displaystyle T(a)={frac {1}{a}}sum _{dmid a}varphi (d) au (d)}$

it can be approximated by the formula^[108]

${displaystyle T(a)approx C+{frac {12}{pi ^{2}}}ln 2left(ln a-sum _{dmid a}{frac {Lambda (d)}{d}}ight)}$

where Λ(d) je Mangoldt function.^[109]

A third average Y(n) is defined as the mean number of steps required when both A a b are chosen randomly (with uniform distribution) from 1 to n^[108]

${displaystyle Y(n)={frac {1}{n^{2}}}sum _{a=1}^{n}sum _{b=1}^{n}T(a,b)={frac {1}{n}}sum _{a=1}^{n}T(a).}$

Substituting the approximate formula for T(A) into this equation yields an estimate for Y(n)^[110]

${displaystyle Y(n)approx {frac {12}{pi ^{2}}}ln 2ln n+0.06.}$

Computational expense per step

In each step k of the Euclidean algorithm, the quotient q_k a zbytek r_k are computed for a given pair of integers r_k−2 a r_k−1

r_k−2 = q_k r_k−1 + r_k.

The computational expense per step is associated chiefly with finding q_k, since the remainder r_k can be calculated quickly from r_k−2, r_k−1, a q_k

r_k = r_k−2 − q_k r_k−1.

The computational expense of dividing h-bit numbers scales as Ó(h(ℓ+1)), where ℓ is the length of the quotient.^[90]

For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient q number of subtractions. If the ratio of A a b is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient q is approximately ln|u/(u − 1)| kde u = (q + 1)².^[111] For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers,^[112] the subtraction-based Euclid's algorithm is competitive with the division-based version.^[113] This is exploited in the binary version of Euclid's algorithm.^[114]

Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (h²) with the average number of digits h in the initial two numbers A a b. Nechat h₀, h₁, ..., h_N−1 represent the number of digits in the successive remainders r₀, r₁, ..., r_N−1. Since the number of steps N grows linearly with h, the running time is bounded by

${displaystyle O{Big (}sum _{i$

Alternativní metody

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.^[115] For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.

One inefficient approach to finding the GCD of two natural numbers A a b is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b. The number of steps of this approach grows linearly with b, or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted výše, the GCD equals the product of the prime factors shared by the two numbers A a b.^[6] Present methods for Prvočíselný rozklad are also inefficient; many modern cryptography systems even rely on that inefficiency.^[9]

The binární algoritmus GCD is an efficient alternative that substitutes division with faster operations by exploiting the binární representation used by computers.^[116][117] However, this alternative also scales like Ó(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.^[91] Additional efficiency can be gleaned by examining only the leading digits of the two numbers A a b.^[118][119] The binary algorithm can be extended to other bases (k-ary algorithms),^[120] with up to fivefold increases in speed.^[121] Lehmerův GCD algoritmus uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.

A recursive approach for very large integers (with more than 25,000 digits) leads to kvazilineární integer GCD algorithms,^[122] such as those of Schönhage,^[123][124] and Stehlé and Zimmermann.^[125] These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given výše. These quasilinear methods generally scale as Ó(h (log h)² (log log h)).^[91][92]

Zobecnění

Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as polynomy,^[126] kvadratická celá čísla^[127] a Hurwitz quaternions.^[128] In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into irreducible elements, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.

Rational and real numbers

Euclid's algorithm can be applied to reálná čísla, as described by Euclid in Book 10 of his Elementy. The goal of the algorithm is to identify a real number G such that two given real numbers, A a b, are integer multiples of it: A = mg a b = ng, kde m a n jsou celá čísla.^[26] This identification is equivalent to finding an integer relation among the real numbers A a b; that is, it determines integers s a t takhle sa + tb = 0. Euclid uses this algorithm to treat the question of incommensurable lengths.^[129][130]

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders r_k are real numbers, although the quotients q_k are integers as before. Second, the algorithm is not guaranteed to end in a finite number N of steps. If it does, the fraction A/b is a rational number, i.e., the ratio of two integers

${displaystyle {frac {a}{b}}={frac {mg}{ng}}={frac {m}{n}},}$

and can be written as a finite continued fraction [q₀; q₁, q₂, ..., q_N]. If the algorithm does not stop, the fraction A/b je iracionální číslo and can be described by an infinite continued fraction [q₀; q₁, q₂, …].^[131] Examples of infinite continued fractions are the Zlatý řez φ = [1; 1, 1, ...] a square root of two, √2 = [1; 2, 2, ...].^[132] The algorithm is unlikely to stop, since téměř všechny poměry A/b of two real numbers are irrational.^[133]

An infinite continued fraction may be truncated at a step k [q₀; q₁, q₂, ..., q_k] to yield an approximation to A/b that improves as k se zvyšuje. The approximation is described by konvergenty m_k/n_k; the numerator and denominators are coprime and obey the relace opakování

${displaystyle { egin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2} _{k}&=q_{k}n_{k-1}+n_{k-2},end{aligned}}}$

kde m₋₁ = n₋₂ = 1 a m₋₂ = n₋₁ = 0 are the initial values of the recursion. The convergent m_k/n_k is the best racionální číslo approximation to A/b with denominator n_k:^[134]

${displaystyle left|{frac {a}{b}}-{frac {m_{k}}{n_{k}}}ight|<{frac {1}{n_{k}^{2}}}.}$

Polynomials

Polynomials in a single variable X can be added, multiplied and factored into neredukovatelné polynomy, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial G(X) of two polynomials A(X) a b(X) is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.^[126] The basic procedure is similar to that for integers. At each step k, a quotient polynomial q_k(X) and a remainder polynomial r_k(X) are identified to satisfy the recursive equation

${displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}$

kde r₋₂(X) = A(X) a r₋₁(X) = b(X). Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: deg[r_k(X)] < deg[r_k−1(X)]. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, A(X) a b(X).^[135]

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials

${displaystyle { egin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)qquad { ext{and}}(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).end{aligned}}}$

Dělení A(X) podle b(X) yields a remainder r₀(X) = X³ + (2/3)X² + (5/3)X − (2/3). In the next step, b(X) is divided by r₀(X) yielding a remainder r₁(X) = X² + X + 2. Finally, dividing r₀(X) podle r₁(X) yields a zero remainder, indicating that r₁(X) is the greatest common divisor polynomial of A(X) a b(X), consistent with their factorization.

Many of the applications described above for integers carry over to polynomials.^[136] The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zeros of a polynomial that lie inside a given real interval.^[137] This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion v teorie řízení.^[138]

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields GF(p) described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.^[126]

Gaussova celá čísla

Distribution of Gaussian primes u + vi in the complex plane, with norms u² + proti² less than 500

The Gaussian integers are komplexní čísla formuláře α = u + vi, kde u a proti are ordinary celá čísla^{[poznámka 2]} a i je square root of negative one.^[139] By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument výše.^[40] This unique factorization is helpful in many applications, such as deriving all Pythagorean triples or proving Fermatova věta o součtech dvou čtverců.^[139] In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers α a β is nearly the same as that for ordinary integers,^[140] but differs in two respects. As before, the task at each step k is to identify a quotient q_k and a remainder r_k takhle

${displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}$

kde r_k−2 = α, kde r_k−1 = β, and where every remainder is strictly smaller than its predecessor: |r_k| < |r_k−1|. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are komplexní čísla. The quotients q_k are generally found by rounding the real and complex parts of the exact ratio (such as the complex number α/β) to the nearest integers.^[140] Druhý rozdíl spočívá v nutnosti definovat, jak může být jeden komplexní zbytek „menší“ než jiný. K tomu, a normální funkce F(u + vi) = u² + proti² je definováno, které převádí každé gaussovské celé číslo u + vi na obyčejné celé číslo. Po každém kroku k euklidovského algoritmu, norma zbytku F(r_k) je menší než norma předchozího zbytku, F(r_k−1). Protože normou je nezáporné celé číslo a klesá s každým krokem, euklidovský algoritmus pro Gaussova celá čísla končí konečným počtem kroků.^[141] Konečný nenulový zbytek je gcd (α, β), Gaussovo celé číslo největší normy, které rozděluje obojí α a β; je jedinečný až do násobení jednotkou, ±1 nebo ±i.^[142]

Mnoho dalších aplikací euklidovského algoritmu se přenáší do gaussovských celých čísel. Lze jej například použít k řešení lineárních diofantických rovnic a problémů čínského zbytku pro Gaussova celá čísla;^[143] lze definovat i další zlomky gaussovských celých čísel.^[140]

Euklidovské domény

Sada prvků do dvou binární operace, označovaný jako sčítání a násobení, se nazývá a Euklidovská doména pokud tvoří komutativní prsten R a zhruba řečeno, pokud na nich lze provést zobecněný euklidovský algoritmus.^[144][145] Dvě operace takového kruhu nemusí být sčítáním a násobením běžné aritmetiky; spíše mohou být obecnější, například operace a matematická skupina nebo monoidní. Tyto obecné operace by nicméně měly respektovat mnoho zákonů upravujících běžnou aritmetiku, například komutativita, asociativita a distribučnost.

Zobecněný euklidovský algoritmus vyžaduje a Euklidovská funkce, tj. mapování F z R do množiny nezáporných celých čísel tak, že pro libovolné dva nenulové prvky A a b v R, existují q a r v R takhle A = qb + r a F(r) < F(b).^[146] Příklady takových mapování jsou absolutní hodnota celých čísel, stupeň pro jednorozměrné polynomy a norma pro Gaussovy celá čísla výše.^[147][148] Základním principem je, že každý krok algoritmu se snižuje F neúprosně; tedy pokud F lze omezit pouze na konečný počet opakování, algoritmus se musí zastavit v konečném počtu kroků. Tento princip se opírá o dobře objednávající vlastnost nezáporných celých čísel, která tvrdí, že každá neprázdná sada nezáporných celých čísel má nejmenší člen.^[149]

The základní teorém aritmetiky platí pro jakoukoli euklidovskou doménu: Do libovolného čísla z euklidovské domény lze jednoznačně započítat neredukovatelné prvky. Jakákoli euklidovská doména je jedinečná faktorizační doména (UFD), ačkoli konverzace není pravdivá.^[149] Euklidovské domény a UFD jsou podtřídami GCD domény, domény, ve kterých vždy existuje největší společný dělitel dvou čísel.^[150] Jinými slovy, může existovat největší společný dělitel (pro všechny páry prvků v doméně), i když nemusí být možné jej najít pomocí euklidovského algoritmu. Euklidovská doména je vždy a hlavní ideální doména (PID), an integrální doména ve kterém každý ideál je hlavní ideál.^[151] Opět platí, že obrácení není pravda: ne každý PID je euklidovská doména.

Jedinečná faktorizace euklidovských domén je užitečná v mnoha aplikacích. Například jedinečná faktorizace gaussovských celých čísel je vhodná pro odvození vzorců pro všechny Pytagorejské trojnásobky a při dokazování Fermatova věta o součtech dvou čtverců.^[139] Jedinečná faktorizace byla také klíčovým prvkem při pokusu o důkaz Fermatova poslední věta publikoval v roce 1847 Gabriel Lamé, stejný matematik, který analyzoval účinnost Euklidova algoritmu na základě návrhu Joseph Liouville.^[152] Lamého přístup vyžadoval jedinečnou faktorizaci čísel formuláře X + ωy, kde X a y jsou celá čísla a ω = E^2iπ/n je nth root of 1, that is, ωⁿ = 1. I když je tento přístup úspěšný pro některé hodnoty n (jako n = 3, Eisensteinova celá čísla ), obecně taková čísla dělají ne faktor jedinečně. Toto selhání jedinečné faktorizace u některých cyklotomická pole vedený Ernst Kummer k pojmu ideální čísla a později, Richard Dedekind na ideály.^[153]

Unikátní faktorizace kvadratických celých čísel

Distribuce Eisensteinových prvočísel u + vω v komplexní rovině, s normami menšími než 500. Počet ω je krychle kořen 1.

The kvadratické celé číslo kroužky jsou užitečné pro ilustraci euklidovských domén. Kvadratická celá čísla jsou zevšeobecnění gaussovských celých čísel, ve kterých imaginární jednotka i se nahrazuje číslem ω. Mají tedy formu u + vω, kde u a proti jsou celá čísla a ω má jednu ze dvou forem, v závislosti na parametru D. Li D nerovná se tedy násobkem čtyř plus jedna

${displaystyle omega = {sqrt {D}}.}$

Pokud však D rovná se tedy násobek čtyř plus jedna

${displaystyle omega = {frac {1+ {sqrt {D}}} {2}}.}$

Pokud je funkce F odpovídá a norma funkce, která se používá k uspořádání Gaussových celých čísel výše, pak je doména známá jako norm-euklidovský. Normálně-euklidovské kruhy kvadratických celých čísel jsou přesně ty, kde D je jednou z hodnot −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, nebo 73.^[154][155] Případy D = −1 a D = −3 výtěžek Gaussova celá čísla a Eisensteinova celá čísla, resp.

Li F je povolena jakákoli euklidovská funkce, pak seznam možných hodnot D pro kterou je doména euklidovská, dosud není známa.^[156] První příklad euklidovské domény, která nebyla normou-euklidovská (s D = 69) byla zveřejněna v roce 1994.^[156] V roce 1973 Weinberger dokázal, že kvadratický celočíselný kruh s D > 0 je euklidovský tehdy a jen tehdy, když je hlavní ideální doména, za předpokladu, že zobecněná Riemannova hypotéza drží.^[127]

Nezávazné prsteny

Euklidovský algoritmus lze použít na některé nekomutativní prstence, jako je množina Hurwitzovy čtveřice.^{[je zapotřebí objasnění ][128]} Nechat α a β představují dva prvky z takového kruhu. Mají společného dělitele práv δ -li α = ξδ a β = ηδ pro nějakou volbu ξ a η v ringu. Podobně mají společného levého dělitele, pokud α = dξ a β = dη pro nějakou volbu ξ a η v ringu. Protože násobení není komutativní, existují dvě verze euklidovského algoritmu, jedna pro pravé dělitele a druhá pro levé dělitele.^[128] Výběr správných dělitelů, první krok při hledání gcd (α, β) pomocí euklidovského algoritmu lze zapsat

${displaystyle ho _ {0} = alpha -psi _ {0} eta = (xi -psi _ {0} eta) delta,}$

kde ψ₀ představuje kvocient a ρ₀ zbytek.^{[je zapotřebí objasnění ]} Tato rovnice ukazuje, že jakýkoli společný pravý dělitel α a β je rovněž společným dělitelem zbytku ρ₀. Analogická rovnice pro levé dělitele by byla

${displaystyle ho _ {0} = alfa - eta psi _ {0} = delta (xi -eta psi _ {0}).}$

S oběma možnostmi se postup opakuje výše uvedeným způsobem, dokud není identifikován největší společný pravý nebo levý dělitel. Stejně jako v euklidovské doméně je „velikost“ zbytku ρ₀ musí být přísně menší než βa musí existovat pouze konečný počet možných velikostí ρ₀, takže je zaručeno, že algoritmus bude ukončen.^{[je zapotřebí objasnění ][157]}

Většina výsledků pro GCD se přenáší na nekomutativní čísla.^{[je zapotřebí objasnění ]} Například, Bézoutova identita uvádí, že právo gcd (α, β) lze vyjádřit jako lineární kombinaci α a β.^[158] Jinými slovy, existují čísla σ a τ takhle

${displaystyle Gamma _ {ext {right}} = sigma alfa + au eta.}$

Analogická identita pro levou GCD je téměř stejná:

${displaystyle Gamma _ {ext {left}} = alfa sigma + eta au.}$

Bézoutovu identitu lze použít k řešení diofantických rovnic. Například jeden ze standardních důkazů o Lagrangeova věta o čtyřech čtvercích, že každé kladné celé číslo lze vyjádřit jako součet čtyř čtverců, je tímto způsobem založeno na čtveřicích GCD.^[157]

Viz také

• Euklidovský rytmus, metoda pro použití euklidovského algoritmu ke generování hudebních rytmů

Poznámky

Reference

Bibliografie

• Cohen, H. (1993). Kurz výpočetní algebraické teorie čísel. New York: Springer-Verlag. ISBN  0-387-55640-0.CS1 maint: ref = harv (odkaz)
• Cohn, H. (1962). Pokročilá teorie čísel. New York: Dover. ISBN  0-486-64023-X.CS1 maint: ref = harv (odkaz)
• Cox, D.; Malý, J .; O'Shea, D. (1997). Ideály, odrůdy a algoritmy: Úvod do výpočetní algebraické geometrie a komutativní algebry (2. vyd.). Springer-Verlag. ISBN  0-387-94680-2.CS1 maint: ref = harv (odkaz)
• Crandall, R.; Pomerance, C. (2001). Prvočísla: Výpočetní perspektiva (1. vyd.). New York: Springer-Verlag. ISBN  0-387-94777-9.CS1 maint: ref = harv (odkaz)
• Lejeune Dirichlet, P. G. (1894). Dedekind, Richarde (vyd.). Vorlesungen über Zahlentheorie (přednášky o teorii čísel) (v němčině). Braunschweig: Vieweg. LCCN  03005859. OCLC  490186017.CS1 maint: ref = harv (odkaz). Viz také Vorlesungen über Zahlentheorie
• Knuth, D. E. (1997). Umění počítačového programování, Volume 2: Seminumerical Algorithms (3. vyd.). Addison – Wesley. ISBN  0-201-89684-2.CS1 maint: ref = harv (odkaz)
• LeVeque, W. J. (1996) [1977]. Základy teorie čísel. New York: Dover. ISBN  0-486-68906-9.CS1 maint: ref = harv (odkaz)
• Mollin, R. A. (2008). Teorie základního čísla s aplikacemi (2. vyd.). Boca Raton: Chapman & Hall / CRC. ISBN  978-1-4200-6659-3.CS1 maint: ref = harv (odkaz)
• Ruda, O. (1948). Teorie čísel a její historie. New York: McGraw – Hill.CS1 maint: ref = harv (odkaz)
• Rosen, K.H. (2000). Teorie elementárních čísel a její aplikace (4. vydání). Reading, MA: Addison – Wesley. ISBN  0-201-87073-8.CS1 maint: ref = harv (odkaz)
• Schroeder, M. (2005). Teorie čísel ve vědě a komunikaci (4. vydání). Springer-Verlag. ISBN  0-387-15800-6.CS1 maint: ref = harv (odkaz)
• Stark, H. (1978). Úvod do teorie čísel. MIT Stiskněte. ISBN  0-262-69060-8.CS1 maint: ref = harv (odkaz)
• Stillwell, J. (1997). Čísla a geometrie. New York: Springer-Verlag. ISBN  0-387-98289-2.CS1 maint: ref = harv (odkaz)
• Stillwell, J. (2003). Prvky teorie čísel. New York: Springer-Verlag. ISBN  0-387-95587-9.CS1 maint: ref = harv (odkaz)
• Tattersall, J. J. (2005). Základní teorie čísel v devíti kapitolách. Cambridge: Cambridge University Press. ISBN  978-0-521-85014-8.CS1 maint: ref = harv (odkaz)

externí odkazy

• Demonstrace Euklidova algoritmu
• Weisstein, Eric W. „Euklidovský algoritmus“. MathWorld.
• Euklidův algoritmus na cut-the-uzel
• Euklidův algoritmus na PlanetMath.org.
• Euklidovský algoritmus na MathPages
• Euklidova hra na cut-the-uzel
• Hudba a Euklidův algoritmus