Euklidův algoritmus

Euklidův algoritmus  je účinný algoritmus pro nalezení největšího společného dělitele dvou celých čísel (neboli společné míry dvou segmentů ). Algoritmus je pojmenován po řeckém matematikovi Euklidovi (3. století př. n. l.), který jej poprvé popsal v knihách VII [1] a X [2] „ Počátků “. Je to jeden z nejstarších numerických algoritmů, které se dnes používají [3] .

Ve své nejjednodušší podobě je Euklidův algoritmus aplikován na pár kladných celých čísel a generuje nový pár, který se skládá z menšího čísla a rozdílu mezi větším a menším číslem. Postup se opakuje, dokud se čísla nerovnají. Nalezené číslo je největší společný dělitel původní dvojice. Euclid navrhl algoritmus pouze pro přirozená čísla a geometrické veličiny (délky, plochy, objemy). Nicméně, v 19. století to bylo zobecněno na jiné typy matematických objektů , včetně Gaussian celých čísel a polynomials v jedné proměnné . Toto vedlo ke vzniku představy o Euclidean prstenu v moderní obecné algebře . Později byl Euklidův algoritmus zobecněn na jiné matematické struktury , jako jsou uzly a vícerozměrné polynomy .

Existuje mnoho teoretických i praktických aplikací pro tento algoritmus. Zejména je základem pro kryptografický algoritmus veřejného klíče RSA [4] , který je široce používán v elektronickém obchodování . Algoritmus se také používá při řešení lineárních diofantických rovnic [5] , při konstrukci spojitých zlomků [6] , ve Sturmově metodě [7] . Euklidův algoritmus je hlavním nástrojem pro dokazování teorémů v moderní teorii čísel , jako je Lagrangeova věta o čtyřech čtvercích [8] a základní teorém aritmetiky [9] .

Historie

Starověcí řečtí matematici nazývali tento algoritmus ἀνθυφαίρεσις nebo ἀνταναίρεσις  - "vzájemné odčítání". Tento algoritmus nebyl objeven Euklidem , protože již o něm je zmínka v Tématu Aristotela (4. století př. n. l.) [3] . V Euklidových „Prvcích“ je popsána dvakrát – v knize VII pro nalezení největšího společného dělitele dvou přirozených čísel [1] a v knize X pro nalezení největší společné míry dvou homogenních veličin [2] . V obou případech je uveden geometrický popis algoritmu pro nalezení „společné míry“ dvou segmentů.

Historici matematiky se domnívají, že právě s pomocí Euklidova algoritmu (postup postupného vzájemného odčítání) byla existence nesouměřitelných veličin (stran a úhlopříček čtverce nebo stran a úhlopříček pravidelného pětiúhelníku ) poprvé objevena ve starověku. Řecká matematika [10] . Tento předpoklad však nemá dostatečné listinné důkazy. Algoritmus pro nalezení největšího společného dělitele dvou přirozených čísel je také popsán v knize I starověkého čínského pojednání Matematika v devíti knihách .

Popis

Euklidův algoritmus pro celá čísla

Nechť a být celá čísla, která se současně nerovna nule, a posloupnost čísel

je definováno tak, že každé je zbytkem po dělení předchozího čísla předchozím a předposlední je vyděleno posledním, tedy:

Potom gcd( a , b ), největší společný dělitel aab , je roven r n , poslednímu nenulovému členu této posloupnosti [ 11] .

Existenci takových r 1 , r 2 , …, r n , tedy možnost dělení se zbytkem m n pro libovolné celé číslo m a celé číslo n ≠ 0, dokazujeme indukcí na m .

Správnost tohoto algoritmu vyplývá z následujících dvou tvrzení [12] :

I. Nechť a = b ⋅ q + r , pak gcd (a, b) = gcd (b, r).

1. Nechť k je libovolný společný dělitel čísel aab , nemusí být nutně největší, pak a = t 1 ⋅ k a b = t 2 ⋅ k , kde t 1 a t 2 jsou celá čísla z definice.
2. Potom k je také společný dělitel b a r , protože b je dělitelné k podle definice, a (výraz v závorkách je celé číslo, takže k dělí r beze zbytku).
3. Platí to i obráceně a dokazuje se to podobně jako v bodě 2: libovolný dělitel b a r je také dělitelem a a b .
4. Všechny společné dělitele dvojic čísel ( a , b ) a ( b , r ) jsou tedy stejné. Jinými slovy, neexistuje žádný společný dělitel čísel ( a , b ), který by nebyl zároveň dělitelem ( b , r ), a naopak.
5. Zejména největší společný dělitel zůstává stejný, protože za předpokladu, že gcd ( a , b ) > gcd ( b , r ) nebo gcd ( a , b ) < gcd ( b , r ) jsou získány rozpory, proto gcd ( a , b ) = gcd ( b , r ). Q.E.D.

II. gcd( r , 0) = r pro libovolné nenulové r (protože 0 je dělitelné libovolným celým číslem).

Euklidův geometrický algoritmus

Nechť jsou dány dva segmenty délky aab . Odečtěte menší segment od většího segmentu a nahraďte větší segment výsledným rozdílem. Tuto operaci opakujeme a odečítáme menší segment od většího, dokud se segmenty nestanou stejnými. Pokud k tomu dojde, pak jsou původní segmenty souměřitelné a poslední získaný segment je jejich největší společnou mírou. Pokud neexistuje žádná společná míra, pak je proces nekonečný. V této podobě je algoritmus popsán Euklidem [2] a je implementován pomocí kompasu a pravítka .

Příklad

Pro ilustraci použijeme euklidovský algoritmus k nalezení gcd a = 1071 a b = 462. Nejprve odečteme násobek 462 od 1071, dokud nezískáme rozdíl menší než 462. Musíme odečíst 462 dvakrát, ( q 0 = 2), zbývající se zbytkem 147:

Potom odečteme násobek 147 od 462, dokud nezískáme rozdíl menší než 147. Musíme odečíst 147 třikrát ( q 1 = 3), přičemž zůstaneme se zbytkem 21:

Potom odečteme násobek 21 od 147, dokud nezískáme rozdíl menší než 21. Musíme odečíst 21 sedmkrát ( q 2 = 7), přičemž nezůstane žádný zbytek:

Posloupnost a > b > r 1 > r 2 > r 3 > ... > r n v tomto konkrétním případě tedy bude vypadat takto:

Protože poslední zbytek je nula, algoritmus končí 21 a gcd(1071, 462) = 21.

V tabulkové formě byly kroky následující:

Pokud je potřeba najít gcd pro více než dvě čísla, je algoritmus podobný, v každém kroku jsou všechna čísla kromě nejmenšího nahrazena zbytky modulo nejmenší. Nulové zbytky, pokud existují, jsou přeškrtnuty. Algoritmus končí, když zbývá jedno nenulové číslo, to je GCD.

Aplikace

Rozšířený Euklidův algoritmus a Bezoutův vztah

Vzorce pro lze přepsat takto:

Zde s a t jsou celá čísla. Tato reprezentace největšího společného dělitele se nazývá Bezoutův poměr a čísla s a t  jsou Bezoutovy koeficienty [13] . Bezoutův vztah je klíčový v důkazu Euklidova lemmatu a základní věty aritmetiky .

Pokračovací zlomky

Euklidův algoritmus je docela blízko příbuzný se spojitými zlomky [6] . Vztah a / b lze reprezentovat jako pokračující zlomek:

V tomto případě se pokračovací zlomek bez posledního členu rovná poměru Bezoutových koeficientů t / s , braných se znaménkem mínus:

Posloupnost rovností definujících euklidovský algoritmus lze přepsat do tvaru:

Poslední člen na pravé straně rovnice je vždy roven převrácené straně levé strany následující rovnice. Proto lze první dvě rovnice kombinovat ve tvaru:

Třetí rovností můžeme nahradit jmenovatele výrazu r 1 / r 0 , dostaneme:

Poslední poměr zbytků r k / r k −1 lze vždy nahradit pomocí další rovnosti v pořadí a tak dále až do poslední rovnice. Výsledkem je pokračující zlomek:

Ve výše uvedeném příkladu byl vypočten GCD(1071, 462) a bylo zjištěno, že kvocienty qk jsou 2, 3 a 7, v tomto pořadí. Proto 1071/462 lze zapsat jako:

Lineární diofantické rovnice

Diophantine rovnice  je rovnice s celočíselnými koeficienty a s jednou nebo více proměnnými a úkolem je najít pouze její celočíselné kořeny. Taková rovnice může mít nekonečný počet řešení, konečný počet řešení nebo vůbec žádné. Nejjednodušší diofantická rovnice je lineární se dvěma neznámými:

kde a , b , c  jsou celá čísla. Pomocí Euklidova algoritmu lze nalézt úplné řešení rovnice tohoto typu [5] . Nejprve pomocí tohoto algoritmu můžete určit d = gcd( a , b ). Potom pomocí rozšířeného Euklidova algoritmu určíme k a l tak, že:

To znamená, že x \u003d k a y \u003d l  je konkrétní řešení rovnice pro c \u003d d . Ukazuje se, že pokud c = q⋅d , pak x = q⋅k , y = q⋅l  je partikulárním řešením původní rovnice, protože:

Naopak, pokud existuje alespoň jedno řešení rovnice, pak c je násobkem d . Vyplývá to z toho, že d dělí jak a, tak b (a tedy celou levou stranu), takže musí dělit i c (pravou stranu). Lineární diofantická rovnice má tedy alespoň jedno řešení právě tehdy, když c je násobkem gcd( a , b ).

Variace a zobecnění

Euklidovský prsten

Prsteny , ve kterých je použitelný euklidovský algoritmus, se nazývají euklidovské kruhy [14] . Patří sem zejména okruhy celých čísel a okruhy polynomů .

Zobecněný Euklidův algoritmus pro polynomy

Euklidův algoritmus a rozšířený Euklidův algoritmus přirozeně zobecňují na okruh polynomů k [ x ] v jedné proměnné nad libovolným polem k , protože pro takové polynomy je definováno dělení se zbytkem. Při provádění Euklidova algoritmu pro polynomy, podobně jako u Euklidova algoritmu pro celá čísla, se získá polynomiální reziduální posloupnost (PRS) [15] .

Nechť cont(f) je podle definice gcd koeficientů polynomu z  obsahu polynomu . Podíl dělení f(x) cont(f) se nazývá primitivní část polynomu f(x) a označuje se primpart(f(x)). Tyto definice budou potřeba k nalezení GCD dvou polynomů p 1 (x) a p 2 (x) v kruhu . Pro polynomy přes celá čísla platí následující:

KLIKNĚTE KLIKNĚTE

KLIKNĚTE KLIKNĚTE

Problém hledání gcd dvou libovolných polynomů je tedy redukován na problém hledání gcd primitivních polynomů.

Nechť existují dva primitivní polynomy p 1 (x) a p 2 (x) ze Z[x], pro které je vztah mezi jejich mocninami splněn: deg(p 1 (x)) = ma deg(p 2 (x) ) = n, m > n. Dělení polynomů zbytkem znamená přesnou dělitelnost nejvyššího koeficientu děliče nejvyšším koeficientem dělitele, v obecném případě nelze dělení se zbytkem provést. Zavádí se proto algoritmus pseudodělení, který nicméně umožňuje získat pseudokvocient a pseudozbytek (prem), které samy budou patřit do množiny polynomů nad celými čísly.

Pseudodělením rozumíme, že samotnému dělení předchází násobení polynomu , tzn.

kde a  jsou pseudočástečný a pseudozbytek, v tomto pořadí.

Tak a navíc . Pak se Euklidův algoritmus skládá z následujících kroků:

1. Výpočet obsahu GCD:

GCD .

2. Výpočet primitivních částí:

3. Sestavení sekvence polynomiálních zbytků:

4. Vraťte výsledek:

Pokud , pak se vraťte , jinak se vraťte .

Zrychlené verze algoritmu

• Jednou z metod pro urychlení Euklidova celočíselného algoritmu je použití symetrického zbytku [16] :

• Jedna verze zrychleného Euklidova algoritmu pro polynomy je založena na skutečnosti, že střední hodnoty algoritmu závisí hlavně na vysokých mocninách. Aplikace strategie „ rozděl a panuj “ umožňuje snížit asymptotickou složitost algoritmu [16] .

Výpočetní složitost algoritmu

Výpočetní složitost Euklidova algoritmu byla plně prostudována. [17] Tuto složitost lze popsat jako součin počtu kroků dělení požadovaných algoritmem krát výpočetní složitost jednoho kroku. První známou analýzu Euklidova algoritmu navrhl Reinaud v roce 1811. [18] Ukázal, že počet kroků algoritmu pro dvojici čísel ( u , v ) je omezen na v . Později vylepšil hranici na v /2 + 2. Émile Léger v roce 1837 studoval nejhorší případ, kdy se k výpočtu gcd zadávají postupná Fibonacciho čísla . [19] V roce 1841 pak Pierre Joseph Fink ukázal [20] , že počet kroků algoritmu nepřesahuje 2 log 2  v  + 1. Algoritmus proto běží v polynomiálním čase o velikosti menšího z páru. čísel ( u , v ). [19] Finkovu analýzu zdokonalil Gabriel Lame v roce 1844. [21] Ukázal, že počet kroků potřebných k dokončení algoritmu není větší než pětkrát h  , což je počet číslic v desítkové reprezentaci menšího z dvojice čísel ( u , v ). [22] [23]

Když se GCD vypočítá pro čísla, která se vejdou do jednoho strojového slova , každý krok algoritmu trvá konstantní čas. V tomto případě Lameho analýza naznačuje, že výpočetní složitost se odhaduje na O ( h ). Ve výpočtovém modelu vhodném pro výpočty s čísly většími než jedno strojové slovo však může být odhad složitosti výpočtu jednoho zbytku O ( h 2 ). [24] V tomto případě lze celkový čas pro všechny kroky algoritmu analyzovat pomocí teleskopické řady , což ukazuje, že je také O ( h 2 ). Pro urychlení Euklidova algoritmu lze použít moderní algoritmické metody založené na Schönhage-Strassenově metodě pro rychlé násobení celých čísel. To vede ke kvazi-polynomiálnímu času . [25]

Počet kroků

Počet kroků pro výpočet gcd dvou přirozených čísel aab je označen jako T ( a ,  b ). Jestliže g  je největší společný dělitel aab , pak a  =  mg ab  =  ng pro dvě prvočísla ma n . Potom T ( a , b ) = T ( m , n ) , což můžeme vidět , když rovnice získané při výpočtu gcd pro dvojici ( a ,  b ) vydělíme g . [26] Na stejném principu zůstává počet kroků algoritmu nezměněn, pokud aab vynásobíme společným faktorem w , který je ekvivalentní T ( a , b ) = T ( wa , wb ) . Proto se počet kroků T může velmi lišit mezi sousedními dvojicemi čísel, jako jsou ( a ,  b ) a ( a ,  b+1 ), protože tato hodnota závisí na gcd.

Rekurzivní povaha Euklidova algoritmu dává následující rovnici T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = … = N + T ( r N −2 , r N −1 ) = N + 1 , kde T ( x , 0) = 0 za předpokladu. [17]

Nejhorší případ

Pokud Euklidův algoritmus vyžaduje N kroků pro dvojici přirozených čísel a  >  b  > 0, nejmenší hodnoty a a b , pro které to platí, jsou Fibonacciho čísla F N +2 a F N +1 , v tomto pořadí. [27] Jestliže pak Euklidův algoritmus vyžaduje N kroků pro dvojici čísel ( a , b ), kde a  >  b , platí následující nerovnosti a  ≥  F N +2 a b  ≥  F N +1 . To lze dokázat matematickou indukcí . Jestliže N  = 1, pak a je dělitelné b beze zbytku. Nejmenší přirozená čísla, pro která to platí, jsou b  = 1 a a  = 2, respektive F 2 a F 3 . Předpokládejme nyní, že výsledek platí pro všechny hodnoty N až M  − 1. První krok euklidovského algoritmu s M kroky je a  =  q 0 b  +  r 0 a euklidovský algoritmus pro dvojici čísel ( b , r 0 ), kde b  >  r 0 , vyžaduje M  − 1 kroků. Podle indukční hypotézy máme b  ≥  F M +1 a r 0  ≥  F M . Proto a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M +1  +  F M  =  F M +2 , což je požadovaná nerovnost. Tento důkaz, publikovaný Gabrielem Lamem v roce 1844, představuje počátek teorie výpočetní složitosti [ 28] a také první praktickou aplikaci Fibonacciho čísel . [27]

Kulhavý teorém

Počet dělení se zbytkem v procesu aplikace Euklidova algoritmu nepřesahuje pětinásobek počtu číslic menšího čísla zapsaného v desítkové soustavě [29] .

Průměr

Existují různé způsoby, jak vypočítat průměrný počet kroků v algoritmu. První metodou výpočtu je průměrný čas T ( a ) potřebný k výpočtu gcd daného čísla a a menšího přirozeného čísla b , zvoleného se stejnou pravděpodobností z celých čísel od 0 do a  − 1. [17]

Protože však T ( a , b ) hodně kolísá s gcd těchto dvou čísel, je zprůměrovaná funkce T ( a ) také zašuměná. [30] Pro snížení tohoto šumu se převezme druhý průměr τ ( a ) ze všech čísel relativně prvočíselných k a .

kde φ ( a ) je Eulerova funkce . Tento průměr roste plynule, jak se zvyšuje . [31]

Konstanta (Porterova konstanta [32] ) v tomto vzorci je , a ε je nekonečně malé .

Třetí střední hodnota Y ( n ) je definována jako průměrný počet kroků požadovaných , když jsou a a b vybrány náhodně ( rovnoměrně rozložené ) od 1 do n .

Výpočetní složitost kroku

V každém kroku Euklidova algoritmu se vypočítá koeficient q k a zbytek rk pro danou dvojici celých čísel r k −2 a rk −1 . Tato množství jsou spojena následujícím vztahem:

r k −2 = q k r k −1 + rk _

Výpočetní složitost každého kroku souvisí hlavně s nalezením q k , protože zbytek r k lze rychle vypočítat pomocí r k −2 , rk −1 a q k

r k = r k −2 − q k r k −1

Výpočetní složitost operace dělení počtu bitů velikosti h se odhaduje jako O ( h ( ℓ +1)), kde ℓ je velikost kvocientu. [24]

Pro srovnání, původní euklidovský algoritmus, využívající odečítání, může být mnohem pomalejší. Ve většině případů je koeficient q k malé číslo. Pravděpodobnost daného kvocientu q je přibližně rovna ln| u /( u  − 1)|, kde u  = ( q  + 1) 2 . [33] Pro ilustraci, pravděpodobnost podílu 1, 2, 3 nebo 4 je přibližně 41,5 %, 17,0 %, 9,3 % a 5,9 %. Protože odčítání je rychlejší než dělení, zvláště pro čísla větší než jedno slovo, [34] Euklidův algoritmus využívající odčítání může být konkurenceschopnější než algoritmus využívající dělení. [35] Toto se používá v binárním algoritmu pro výpočet gcd . [36]

Odhad složitosti algoritmu se vypočítá jako součin počtu kroků a času potřebného k dokončení jednoho kroku. Ukazuje, že Euklidův algoritmus roste kvadraticky O ( h 2 ), kde h  je průměrný počet číslic ve dvou počátečních číslech aab v desítkové soustavě. Nechť h 0 , h 1 , …, h N −1 představuje počet číslic v po sobě jdoucích zbytcích r 0 ,  r 1 , …,  r N −1 . Protože počet kroků N roste lineárně s h , je doba běhu omezena následujícím výrazem:

Poznámky

1. ↑ 1 2 Mordukhai-Boltovskoy, 1949 , s. 11-13.
2. ↑ 1 2 3 Mordukhai-Boltovskoy, 1949 , str. 103-105.
3. ↑ 1 2 Knuth, 2001 , str. 378.
4. ↑ Menezes, 1996 , str. 286.
5. ↑ 1 2 Courant, 2001 , str. 74-76.
6. ↑ 1 2 Vinogradov, 1952 , str. 14-18.
7. ↑ Engeler, 1987 , str. 24-31.
8. ↑ Tikhomirov, 2003 , str. 11-14.
9. ↑ Kaluzhin, 1969 , s. 6-14.
10. ↑ Zeiten, 1932 , str. 112-114.
11. ↑ Vinogradov, 1952 , s. 9-10.
12. ↑ Courant, 2001 , str. 67-70.
13. ↑ Hasse, 1953 , str. 29-30.
14. ↑ Kurosh, 1973 , str. 91-92.
15. ↑ Pankratiev, 2007 , s. 54-58.
16. ↑ 12 Gathen , 2013 , str. 313-326.
17. ↑ 1 2 3 Knuth, 1997 , str. 344.
18. ↑ Shallit, 1994 , str. 414.
19. ↑ 1 2 Shallit, 1994 , str. 401-419.
20. ↑ Shallit, 1994 , str. 413.
21. ↑ Kulhavý, 1844 , str. 867-870.
22. ↑ Grossman, 1924 , str. 443.
23. ↑ Abramov S. A. Matematické konstrukce a programování. - M., Nauka , 1978. - Náklad 100 000 výtisků. — c. 170
24. ↑ 1 2 Knuth, 1997 , s. 257-261.
25. ↑ Moeller, 2005 , s. jeden.
26. ↑ Ruda, 1948 , str. 45.
27. ↑ 1 2 Knuth, 1997 , s. 343.
28. ↑ LeVeque, 1996 , s. 3.
29. ↑ Abramov S. A. Matematické konstrukce a programování. - M., Nauka, 1978. - Náklad 100 000 výtisků. — c. 170
30. ↑ Knuth, 1997 , str. 353.
31. ↑ Tonkov, 1974 , s. 47-57.
32. ↑ Weisstein, Eric W. Porter's Constant  na webu Wolfram MathWorld .
33. ↑ Knuth, 1997 , str. 352.
34. ↑ Vagon, 1999 , s. 335-336.
35. ↑ Cohen, 1993 , str. čtrnáct.
36. ↑ Cohen, 1993 , str. 14-15, 17-18.

Literatura

• Abramov S. A. Nejslavnější algoritmus // Kvant / ed. A. L. Semenov , A. A. Gaifullin - MIAN , 1985. - sv. 11. - S. 44-46. — ISSN 0130-2221
• Vinogradov I.M. Základy teorie čísel . - M. - L. : GITTL, 1952. - 180 s. - ISBN 978-5-811-40535-0 .
• Kaluzhin L. A. Základní teorém aritmetiky. — Populární přednášky o matematice . - M .: Nauka, 1969. - 33 s.
• Knut D. E. Umění programování. - Williams, 2001. - T. 2. - 829 s. — ISBN 5-8459-0081-6 .
• Courant R., Robbins G. Dodatek ke kapitole I, § 4. // Co je matematika?  - 3. vydání, Rev. a doplňkové - M. , 2001. - 568 s. - ISBN 5-900916-45-6 .
• Kurosh A. G. Přednášky o obecné algebře / ed. O. N. Golovin - 2. vyd. — M .: Nauka , 1973. — 400 s. — ISBN 978-5-8114-0617-3
• Počátky Euklida / přeloženo z řečtiny. a comm. D. D. Mordukhai-Boltovsky, ed. Vygodsky M. Ya. a Veselovsky I. N. - GITTL, 1949. - T. 2. - 511 s.
• Pankratiev EV Prvky počítačové algebry. - INTUIT, 2007. - 217 s. - ISBN 978-5-955-60099-4 .
• Tikhomirov VM Velcí matematici minulosti a jejich velké teorémy. — 2. vyd., opraveno. - MTsNMO , 2003. - 16 s. — ISBN 5-94057-110-7 .
• Hasse G. Přednášky o teorii čísel. - Ed. zahraniční literatura, 1953. - 527 s.
• Zeiten GG Dějiny matematiky ve starověku a ve středověku. - GTTI, 1932. - 232 s.
• Engeler E. Metamatematika elementární matematiky. — M .: Mir, 1987. — 128 s.
• Cohen H. Kurz výpočetní algebraické teorie čísel . - Springer-Verlag, 1993. - ISBN 0-387-55640-0 .
• von zur Gathen J., Gerhard J. Moderní počítačová algebra . - Cambridge University Press, 2013. - 808 s. — ISBN 978-1-107-03903-2 .
• Grossman H. O počtu dělení při hledání GCD  //  The American Mathematical Monthly. - 1924. - Sv. 31 , iss. 9 . - str. 443 . - doi : 10.2307/2298146 . — .
• Knuth D.E. Umění počítačového programování . - 3. - Addison-Wesley, 1997. - V. 2: Seminumerické algoritmy. — ISBN 0-201-89684-2 .
• Lamé G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers  (francouzsky) . Comptes Rendus Acad. Sci., 1844. - č. 19 .
• LeVeque WJ Základy teorie čísel  (anglicky) . - Dover, 1996. - ISBN 0-486-68906-9 .
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC-Press, 1996. - 816 s. - (Diskrétní matematika a její aplikace). - ISBN 0-8493-8523-7 .
• Moeller Niels. Matematika počítání  (anglicky) . — 2005.
• Ore O. Teorie čísel a její historie  (anglicky) . — McGraw–Hill, 1948.
• Shallit J. Origins of the analysis of the Euclidean algorithm  (anglicky)  // Historia Math .. - 1994. - Vol. 21 . - doi : 10.1006/hmat.1994.1031 .
• Tonkov T. O průměrné délce konečných zlomků  (anglicky)  // Acta Arithmetica. - 1974. - Sv. 26 .
• Wagon S. Mathematica v akci  . - Springer-Verlag, 1999. - ISBN 0-387-98252-3 .

Odkazy

• Implementace Euklidova algoritmu v Pascalu

• Euklidův algoritmus na e-maxx.ru
• Implementace rozšířeného Euklidova algoritmu v C

Slovníky a encyklopedie	Velká dánština Skvělý norský Velký Rus chorvatský Britannica (online) Brockhaus
V bibliografických katalozích	GND : 4659898-4