Euklidovský algoritmus - Euclidean algorithm

Euclidova metoda pro nalezení největšího společného dělitele (GCD) dvou počátečních délek BA a DC, přičemž obě jsou definovány jako násobky společné „jednotkové“ délky. Délka DC je kratší a používá se k „měření“ BA, ale pouze jednou, protože zbývající EA je menší než DC. EA nyní měří (dvakrát) kratší délku DC, přičemž zbytek FC je kratší než EA. Poté FC měří (třikrát) délku EA. Protože není žádný zbytek, proces končí tím, že FC je GCD. Vpravo Nicomachův příklad s čísly 49 a 21, jejichž výsledkem je GCD 7 (odvozeno od Heath 1908: 300).

V matematice je euklidovský algoritmus nebo Euclidův algoritmus efektivní metodou pro výpočet největšího společného dělitele (GCD) dvou celých čísel (čísel), největšího počtu, který je oba beze zbytku rozděluje . Je pojmenována po starověkém řeckém matematikovi Euclidovi , který ji poprvé popsal ve svých Prvcích (asi 300 př. N. L.). Je to příklad algoritmu , postup při provádění výpočtu podle přesně definovaných pravidel a je jedním z nejstarších běžně používaných algoritmů. Lze jej použít k redukci zlomků na jejich nejjednodušší formu 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 zmenšuje větší ze dvou čísel, opakování tohoto postupu 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. Tím, couvání kroky , nebo pomocí rozšířeného Euklidova algoritmu , GCD může být vyjádřen jako lineární kombinace z obou původních čísel, která je součtem dvou čísel, z nichž každý vynásobí celé číslo (například, 21 = 5 x 105 + (−2) × 252). Skutečnost, že GCD lze vždy vyjádřit tímto způsobem, se nazývá Bézoutova identita .

Verze euklidovského algoritmu popsaná výše (a Euclidem) může provést mnoho odečítacích kroků k nalezení GCD, když je jedno z daných čísel mnohem větší než druhé. Efektivnější verze algoritmu tyto kroky zkratuje, místo toho nahradí větší ze dvou čísel jeho zbytkem při dělení menším ze dvou (u této verze se algoritmus zastaví, když dosáhne 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 dokázal Gabriel Lamé v roce 1844 a je počátkem 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 zlomků na jejich nejjednodušší formu a pro dělení v modulární aritmetice . Výpočty využívající tento algoritmus jsou součástí kryptografických protokolů, které se používají k zabezpečení internetové komunikace, a v metodách prolomení těchto kryptosystémů faktorováním velkých složených čísel . Euklidovský algoritmus může být použit k řešení diofantických rovnic , jako je hledání čísel, která splňují více kongruencí podle čínské zbytkové věty , pro konstrukci pokračujících zlomků a pro nalezení přesných racionálních přiblížení ke skutečným číslům. Nakonec jej lze použít jako základní nástroj pro dokazování vět v teorii čísel, jako je Lagrangeova věta o čtyřech čtvercích a jedinečnost primární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, jako jsou Gaussova celá čísla a polynomy jedné proměnné. To vedlo k moderním abstraktním algebraickým pojmům, jako jsou euklidovské domény .

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

Euklidovský algoritmus vypočítává největšího společného dělitele (GCD) dvou přirozených čísel a a b . Největší společný dělitel g je největší přirozené číslo, které rozděluje 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ý ukazatel (GCM). Největší společný dělitel je často psán jako gcd ( a , b ) nebo, jednodušeji, jako ( a , b ), ačkoli tento druhý zápis je nejednoznačný, používá se také pro pojmy jako ideál v kruhu celých čísel , který je velmi blízký související s GCD.

Pokud gcd ( a , b ) = 1, pak a a b se říká, že jsou coprime (nebo relativně primární). Tato vlastnost neznamená, že a nebo b jsou prvočísla . Například ani 6 ani 35 není prvočíslo, protože oba mají dva prvočíselné faktory: 6 = 2 × 3 a 35 = 5 × 7. Nicméně 6 a 35 jsou coprime. Žádné jiné přirozené číslo než 1 nedělí 6 a 35, protože nemají společné žádné hlavní faktory.

„Vysoký, štíhlý obdélník rozdělený na mřížku čtverců. Obdélník je dva čtverce široký a pět čtverců vysoký.“

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 lze obdélník a -by- b pokrýt čtvercovými dlaždicemi délky strany c pouze pokud je c společným dělitelem a a b .

Nechť g = gcd ( a , b ). Protože a a b jsou oba násobky g , lze je zapsat a = mg a b = ng a neexistuje větší číslo G > g, pro které by to platilo. Přirozená čísla m a n musí být coprime, protože jakýkoli společný faktor by mohl být započítán z m a n, aby bylo g větší. Jakékoli jiné číslo c, které dělí a a b, tedy musí také dělit g . Největší společný dělitel g z a b je unikátní (pozitivní) společný dělitel a , b , která je dělitelná jiného společného dělitele c .

GCD lze zobrazit následujícím způsobem. Zvažte obdélníkovou oblast a by b a jakýkoli společný dělitel c, který přesně dělí a a b . Strany obdélníku lze rozdělit na segmenty délky c , které rozdělují obdélník na mřížku čtverců délky strany c . Největší společný dělitel g je největší hodnota c, u které je to možné. Pro ilustraci lze obdélníkovou oblast 24 x 60 rozdělit na mřížku: čtverce 1 x 1, čtverce 2 x 2, čtverce 3 x 3, čtverce 4 x 4, 6 x -6 čtverců nebo 12 na 12 políček. Proto je 12 největším společným dělitelem 24 a 60. Obdélníkovou oblast 24 x 60 lze rozdělit na mřížku čtverců o velikosti 12 x 12, se dvěma čtverci podél jednoho okraje (24/12 = 2) a pěti čtverce podél druhého (60/12 = 5).

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

Další definice GCD je užitečná v pokročilé matematice, zejména v teorii prstenů . Největší společný dělitel g dvou nenulových čísel dobu a b , je také jejich nejmenší kladné celé lineární kombinace, to znamená, že nejmenší kladné číslo formuláře ua + VB , kde u a v jsou celá čísla. Množina 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 jazykem je ideální generované a b je ideální generované g samotným (ideálu generovaného jediným prvkem je nazýván hlavní ideál , a všechny ideály celých čísel jsou hlavní ideál). 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 oba termíny 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, ale lze jej také vypočítat opakovaným odebráním GCD dvojic čísel. 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ý vypočítává 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ší. Nechť k je 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} . Protože algoritmus zajišťuje, že se zbytky plynule snižují s každým krokem, r _{k −1} je menší než jeho předchůdce r _{k −2} . Cílem k -tého kroku je najít 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 čísla r _{k −1} se odečtou od většího čísla r _{k −2,} dokud zbytek r _k není menší než r _{k −1} .

V počátečním kroku ( k = 0), zbytky r _-2 a r _-1 rovná a b jsou čísla, pro které je GCD se žádá. V dalším kroku ( k = 1) se zbytky rovnají b a zbytek r ₀ počátečního kroku atd. Algoritmus lze tedy zapsat jako posloupnost rovnic

{\ displaystyle {\ begin {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 {aligned}}}

Pokud je menší než b , je prvním krokem algoritmu zamění čísla. Například pokud a < b , počáteční kvocient q _{0 se} rovná nule a zbytek r ₀ je a . Tak, r _k je menší než jeho předchůdce r _k_-1 pro všechna k ≥ 0.

Protože se zbytky snižují každým krokem, ale nikdy nemohou být záporné, musí se zbytek r _N nakonec rovnat nule, v tomto okamžiku se algoritmus zastaví. Konečný 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 r ₀ a nulou existuje pouze konečný počet nezáporných celých čísel .

Doklad o platnosti

Platnost euklidovského algoritmu lze prokázat dvoustupňovým argumentem. V prvním kroku je ukázán konečný nenulový zbytek r _{N −1} k rozdělení a a b . Jelikož je společným dělitelem, musí být menší než nebo roven největšímu společnému děliteli g . Ve druhém kroku je ukázáno, že jakýkoli společný dělitel a a b , včetně g , musí dělit r _{N −1} ; proto g musí být menší nebo roven r _{N −1} . Tyto dva závěry jsou nekonzistentní, pokud r _{N −1} = g .

Abychom ukázali, že r _{N −1} dělí a a b (první krok), r _{N −1} dělí svého předchůdce r _{N −2}

r N -2 = q N r N -1

protože konečný zbytek 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 výrazy na pravé straně rovnice. Opakováním stejného argumentu r _{N −1} rozdělí všechny předchozí zbytky, včetně a a b . Žádný z předchozích zbytků r _{N −2} , r _{N −3} atd. Nedělí a a b , protože zanechávají zbytek. Protože 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 a a b (jinými slovy jakýkoli společný dělitel a a b ) rozděluje zbytky r _k . Podle definice lze a a b zapsat jako násobky c : a = mc a b = nc , kde m a n jsou přirozená čísla. Proto c dělí počáteční zbytek r ₀ , protože r ₀ = a - q ₀b = mc - q ₀nc = ( m - q ₀n ) c . Analogický argument ukazuje, že c dělí i následující zbytky r ₁ , r ₂ atd. Největší společný dělitel g proto musí dělit r _{N −1} , což znamená, že g ≤ r _{N −1} . Protože první část argumentu ukazovala opak ( r _{N −1} ≤ g ), vyplývá z toho, že g = r _{N −1} . Tak, g je největší společný dělitel všechny následující dvojice:

g = gcd (a, b) = gcd (b, r 0) = gcd (r 0, r 1) = ... = gcd (r N -2, r N -1) = r N -1 .

Fungoval příklad

Odečtená animace euklidovského algoritmu. 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, přičemž zůstává obdélník 462 × 147. Tento obdélník je obkládán čtverci 147 × 147, dokud nezůstane obdélník 21 × 147, který je zase obkládán čtverci 21 × 21, takže nezůstane žádná odkrytá oblast. Nejmenší velikost čtverce, 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. Nejprve začneme odečítat násobky 462 od 1071, dokud není zbytek menší než 462. Dva takové násobky lze odečíst ( q ₀ = 2), zbývající část 147:

1071 = 2 \times 462 + 147.

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

462 = 3 \times 147 + 21.

Poté se odečtou násobky 21 od 147, dokud není zbytek menší než 21. Sedm násobků lze odečíst ( q ₂ = 7), přičemž nezůstane žádný zbytek:

147 = 7 \times 21 + 0.

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

Krok k	Rovnice	Kvocient a zbytek
0	$1071 = q 0 462 + r 0$	$q 0 = 2$ a $r 0 = 147$
1	$462 = q 1 147 + r 1$	$q 1 = 3$ a $r 1 = 21$
2	$147 = q 2 21 + r 2$	$q 2 = 7$ a $r 2 = 0$ ; algoritmus končí

Vizualizace

Euklidovský algoritmus lze vizualizovat pomocí analogie obkladů, která je uvedena výše pro největšího společného dělitele. Předpokládejme, že chceme pokrýt obdélník a -by- b čtvercovými dlaždicemi přesně, kde a je větší ze dvou čísel. Nejprve se pokusíme obkládat obdélník pomocí čtvercových dlaždic b -by- b ; toto však ponechá zbytkový obdélník r ₀ -by- b , kde r ₀ < b . Poté se pokusíme vyložit zbytkový obdélník pomocí čtvercových dlaždic r ₀ -by- r ₀ . Zůstane tak druhý zbytkový obdélník r ₁ -by- r ₀ , který se pokusíme obkládat pomocí čtvercových dlaždic r ₁ -by- r ₁ atd. Sekvence končí, když neexistuje žádný zbývající obdélník, tj. Když čtvercové dlaždice přesně překryjí předchozí zbývající 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 na 21 (zobrazeno červeně) a 21 je GCD 1071 a 462, rozměry původního obdélníku (zobrazené zeleně).

Euklidovská divize

V každém kroku k vypočítá euklidovský algoritmus podíl 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 non-negativní a je přísně nižší než absolutní hodnota z r _{k -1} . Věta, která je základem definice euklidovské divize, zajišťuje, že takový kvocient a zbytek vždy existují a jsou jedinečné.

V Euclidově původní verzi algoritmu je podíl a zbytek nalezen opakovaným odečtením; to znamená, že r _{k −1} se odečte od r _{k −2} opakovaně, dokud není zbytek r _k menší než r _{k −1} . Poté se r _k a r _{k −1} vymění a proces se opakuje. Euklidovské dělení redukuje všechny kroky mezi dvěma ústřednami do jednoho kroku, který je tak efektivnější. Navíc kvocienty nejsou potřeba, takže je možné nahradit euklidovské dělení operací modulo , která dává pouze zbytek. Iterace euklidovského algoritmu se tak stává jednoduše

r k = r k -2 mod r k -1 .

Implementace

Implementace algoritmu mohou být vyjádřeny v pseudokódu . Například verze založená na dělení může být naprogramována jako

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

Na začátku k th iterace obsahuje proměnná b 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 rekurznímu vzorci r _k ≡ r _{k −2} mod r _{k −1} . Dočasné proměnné t má hodnotu r _{k -1} , zatímco další zbytek r _k se vypočte. Na konci iterace smyčky obsahuje proměnná b zbytek r _k , zatímco proměnná a drží svého předchůdce r _{k −1} .

(Pokud jsou povoleny záporné vstupy nebo pokud funkce mod může vracet záporné hodnoty, musí být poslední řádek změněn na návrat max (a, −a).)

Ve verzi založené na odčítání, což byla Euclidova původní verze, je zbývající výpočet ( ) nahrazen opakovaným odečtením. 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 obsahuje kladná celá čísla a zastaví se, když a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Proměnné a a b se střídají a drží předchozí zbytky r _{k −1} a r _{k −2} . Předpokládejme, že a je na začátku iterace větší než b ; pak a se rovná r _{k −2} , protože r _{k −2} > r _{k −1} . Během iterace smyčky se a sníží o násobky předchozího zbytku b, dokud a není menší než b . Pak a je další zbytek r _k . Poté se b sníží o násobky a, dokud nebude opět menší než a , čímž bude další zbytek r _{k +1} atd.

Rekurzivní verze je založena na rovnosti GCD po sobě jdoucích zbytků a zastavovací podmínce gcd ( r _{N −1} , 0) = r _{N −1} .

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(Jak je uvedeno výše, pokud jsou povoleny záporné vstupy nebo pokud funkce mod může vracet záporné hodnoty, musí být instrukce „ return a“ změněna na „ return max (a, −a)“.)

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

Metoda nejméně absolutních zbytků

V jiné verzi Euclidova algoritmu je podíl v každém kroku zvýšen o jeden, pokud je výsledný negativní zbytek menší než typický pozitivní zbytek. Dříve rovnice

r k -2 = q k r k -1 + r k

předpokládal, že $| r k -1 | > r k > 0$ . Lze však vypočítat alternativní negativní zbytek $e k$ :

r k -2 = (q k + 1) r k -1 + e k

pokud $r k -1 > 0$ nebo

r k -2 = (q k - 1) r k -1 + e k

pokud $r k -1 <0$ .

Je -li $r k$ nahrazeno $e k .$ když $| e k | <| r k |$ , pak dostaneme takovou variantu euklidovského algoritmu, že

| r k | \leq | r k -1 | / 2

v každém kroku.

Leopold Kronecker ukázal, že tato verze vyžaduje nejméně kroků z jakékoli verze Euclidova algoritmu. Obecněji bylo prokázáno, že pro všechna vstupní čísla a a b je počet kroků minimální právě tehdy, když je vybráno $q k$ v pořadí, kde je zlatý řez . ${\ Displaystyle \ left | {\ frac {r_ {k+1}} {r_ {k}}} \ right | <{\ frac {1} {\ varphi}} \ sim 0,618,}$ ${\ Displaystyle \ varphi}$

Historický vývoj

„Znázornění Euclida jako vousatého muže držícího k tabletu dvojici rozdělovačů.“

Euklidovský algoritmus byl pravděpodobně vynalezen před Euclidem , který je zde zobrazen s kompasem na obraze kolem roku 1474.

Euklidovský algoritmus je jedním z nejstarších běžně používaných algoritmů. Objevuje se v Euclidových prvcích (asi 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 někdo řekl, že to tam bylo formulováno pro reálná čísla . Ale délky, oblasti a objemy, reprezentované jako reálná čísla v moderním použití, nejsou měřeny ve stejných jednotkách a neexistuje žádná přirozená jednotka délky, plochy, nebo objem; pojem 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, která měří a a b rovnoměrně; jinými slovy, délky a a b jsou celočíselné násobky délky g .

Algoritmus pravděpodobně nebyl objeven Euclidem , který ve svých Prvcích sestavil výsledky od dřívějších matematiků . Matematik a historik BL van der Waerden naznačuje, že kniha VII pochází z učebnice teorie čísel napsané matematiky ve škole Pythagoras . Algoritmus byl pravděpodobně znám Eudoxem z Cnidus (asi 375 př. N. L. ). Algoritmus může dokonce zastarat Eudoxus, soudě podle použití odborného výrazu ἀνθυφαίρεσις ( antyphairesis , reciproční odčítání) v dílech Euclida a Aristotela .

O staletí později byl Euclidův algoritmus objeven nezávisle jak v Indii, tak v Číně, především pro řešení diofantických rovnic, které vznikly v astronomii a vytváření přesných kalendářů. Na konci 5. století indický matematik a astronom Aryabhata popsal algoritmus jako „pulverizer“, možná kvůli jeho účinnosti při řešení diofantických rovnic. Ačkoli zvláštní případ čínské zbytkové věty již byl popsán v čínské knize Sunzi Suanjing , obecné řešení publikoval Qin Jiushao ve své knize z roku 1247 Shushu Jiuzhang (數書九章Mathematical Treatise in Nine Sections ). Euclidean algoritmus byl poprvé popsán numericky a propagován v Evropě ve druhém vydání Bachet je Problèmes plaisants et delectables ( příjemné a příjemný problémy , 1624). V Evropě byl také použit k řešení diofantických rovnic a při vývoji pokračujících zlomků . Rozšířila Euclidean algoritmus byl publikován anglický matematik Nicholas Saunderson , který ji připsat Roger Cotes jako způsobu k účinnému výpočtu pokračující frakce.

V 19. století vedl euklidovský algoritmus k vývoji nových číselných systémů, jako jsou Gaussova celá čísla a Eisensteinova celá čísla . V roce 1815 Carl Gauss použil euklidovský algoritmus k prokázání jedinečné faktorizace Gaussových celých čísel , přestože jeho práce byla poprvé publikována v roce 1832. Gauss zmínil algoritmus ve svých Disquisitiones Arithmeticae (publikoval 1801), ale pouze jako metodu pro pokračování zlomků . Zdá se, že Peter Gustav Lejeune Dirichlet byl první, kdo popsal euklidovský algoritmus jako základ pro velkou část teorie čísel. Lejeune Dirichlet poznamenal, že mnoho výsledků teorie čísel, jako je unikátní faktorizace, by platilo pro jakýkoli jiný systém čísel, na který by mohl být aplikován euklidovský algoritmus. Přednášky Lejeune Dirichletové o teorii čísel upravil a rozšířil Richard Dedekind , který použil Euclidův algoritmus ke studiu algebraických celých čísel , nového obecného typu čísel. Například Dedekind byl první, kdo dokázal Fermatovu větu o dvou čtvercích pomocí jedinečné faktorizace Gaussových celých čísel. Dedekind také definoval koncept euklidovské domény , číselného systému, ve kterém lze definovat generalizovanou verzi euklidovského algoritmu (jak je popsáno níže ). V posledních desetiletích 19. století se euklidovský algoritmus postupně zastínil Dedekindovou obecnější teorií ideálů .

„[Euklidovský algoritmus] je dědečkem všech algoritmů, protože je to nejstarší netriviální algoritmus, který přežil do dnešních dnů.“

Donald Knuth , Umění počítačového programování, sv. 2: Seminumerické algoritmy , 2. vydání (1981), s. 318.

Další aplikace Euclidova algoritmu byly vyvinuty v 19. století. V roce 1829 Charles Sturm ukázal, že algoritmus byl užitečný v metodě Sturmova řetězce pro počítání skutečných kořenů polynomů v jakémkoli daném intervalu.

Euklidovský algoritmus byl první celočíselný relační algoritmus , což je metoda pro hledání celočíselných vztahů mezi úměrnými reálnými čísly. Bylo vyvinuto několik nových celočíselných relačních algoritmů , například algoritmus Helamana Fergusona a RW Forcade (1979) a algoritmus LLL .

V roce 1969 Cole a Davie vyvinuli hru pro dva hráče na základě euklidovského algoritmu s názvem The Game of Euclid , která má optimální strategii. Hráči začínají dvěma hromadami kamenů a a b . Hráči se střídají v odstraňování m násobků menší hromádky z větších. Pokud se tedy dvě hromádky skládají z kamenů x a y , kde x je větší než y , může další hráč zmenšit větší hromádku z x kamenů na x - moje kameny, pokud je to druhé nezáporné celé číslo. Vítězem je první hráč, který sníží jednu hromádku na nula kamenů.

Matematické aplikace

Bézoutova identita

Bézoutova identita uvádí, že největšího společného dělitele g dvou celých čísel a a b lze znázornit jako lineární součet původních dvou čísel a a b . Jinými slovy, vždy je možné najít celá čísla s a t taková, že g = sa + tb .

Celá čísla s a t lze vypočítat z podílů q ₀ , q ₁ atd. Obrácením pořadí rovnic v Euclidově algoritmu. Počínaje rovnicí předposlední lze g vyjádřit pomocí kvocientu q _{N −1} a dvou předchozích zbytků, r _{N −2} a r _{N −3} :

g = r N -1 = r N -3 - q N -1 r N -2 .

Tyto dva zbytky mohou být rovněž vyjádřeny jako jejich kvocienty 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 .

Dosazením těchto vzorců pro r _{N −2} a r _{N −3} do první rovnice vznikne 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, dokud není dosaženo původních čísel a a b :

r 2 = r 0 - q 2 r 1

r 1 = b - q 1 r 0

r 0 = a - q 0 b .

Poté, co všechny zbytky r ₀ , r ₁ , atd. Jsou substituovány, konečná rovnice vyjadřuje g jako lineární součet a a b : g = sa + tb . Bézoutovu identitu , a tedy i předchozí algoritmus, lze oba zobecnit na kontext euklidovských domén .

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 . Uvažujme množinu všech čísel ua + vb , kde u a v jsou libovolná dvě celá čísla. Protože a a b jsou obě dělitelné g , každé číslo v sadě je dělitelné g . Jinými slovy, každé číslo sady je celočíselný násobek g . To platí pro každého společného dělitele a a b . Na rozdíl od jiných běž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 v = 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 libovolný násobek m z g lze získat volbou u = ms a v = mt , kde s a t jsou celá čísla Bézoutovy identity. To lze vidět vynásobením Bézoutovy identity m ,

mg = msa + mtb .

Proto je množina všech čísel ua + vb je ekvivalentní k sadě násobků m o 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 ). GCD se říká, že je generátor ideálu z a b . Tato definice GCD vedla k moderním abstraktním algebraickým konceptům principálního ideálu (ideálu generovaného jediným prvkem) a hlavní ideální domény ( domény, ve které je každý ideál hlavním ideálem).

Pomocí tohoto výsledku lze vyřešit určité problémy. Zvažte například dvě odměrky objemu a a b . Sečtením/odečtením u násobků prvního šálku a v násobků druhého šálku lze změřit jakýkoli objem ua + vb . Tyto objemy jsou všechny 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ého euklidovského algoritmu . Toto rozšíření přidává do Euclidova algoritmu dvě rekurzivní rovnice

s k = s k -2 - q k s k -1

t k = t k -2 - q k t k -1

s počátečními hodnotami

s -2 = 1, t -2 = 0

s -1 = 0, t -1 = 1.

Pomocí této rekurze jsou Bézoutova celá čísla s a t dána s = s _N a t = t _N , kde N+1 je krok, ve kterém algoritmus končí r _N+1 = 0.

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

r j = s j a + t j b

pro všechny j menší než k . K tém kroku algoritmus dává rovnici

r k = r k -2 - q k r k -1 .

Protože se předpokládalo, že rekurzivní vzorec je správný pro r _{k −2} a r _{k −1} , lze je vyjádřit pomocí odpovídajících s a t proměnných

r k = (s k -2 a + t k -2 b) - q k (s k -1 a + t k -1 b).

Přeuspořádáním této rovnice se získá rekurzivní vzorec pro krok k podle potřeby

r k = s k a + t k b = (s k -2 - q k s k -1) a + (t k -2 - q k t k -1) b .

Maticová metoda

Celá čísla s a t lze také nalézt pomocí ekvivalentní maticové metody. Posloupnost rovnic Euclidova algoritmu

{\ Displaystyle {\ begin {aligned} a & = q_ {0} b+r_ {0} \\ b & = q_ {1} r_ {0}+r_ {1} \\ & \, \, \, \ vdots \ \ r_ {N-2} & = q_ {N} r_ {N-1} +0 \ end {zarovnáno}}}

lze zapsat jako součin kvocientních matic 2 na 2 násobících dvourozměrný zbytek vektoru

{\ Displaystyle {\ begin {pmatrix} a \\ b \ end {pmatrix}} = {\ begin {pmatrix} q_ {0} & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} b \\ r_ {0} \ end {pmatrix}} = {\ begin {pmatrix} q_ {0} & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} q_ {1} & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} r_ {0} \\ r_ {1} \ end {pmatrix}} = \ cdots = \ prod _ {i = 0}^{N} {\ begin {pmatrix} q_ {i} & 1 \ \ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} r_ {N-1} \\ 0 \ end {pmatrix}} \ ,.}

Nechť M představuje součin všech matic kvocientu

{\ Displaystyle \ mathbf {M} = {\ begin {pmatrix} m_ {11} & m_ {12} \\ m_ {21} & m_ {22} \ end {pmatrix}} = \ prod _ {i = 0}^{ N} {\ begin {pmatrix} q_ {i} & 1 \\ 1 & 0 \ end {pmatrix}} = {\ begin {pmatrix} q_ {0} & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} q_ {1} & 1 \\ 1 & 0 \ end {pmatrix}} \ cdots {\ begin {pmatrix} q_ {N} & 1 \\ 1 & 0 \ end {pmatrix}} \ ,.}

To zjednodušuje euklidovský algoritmus do formuláře

{\ Displaystyle {\ begin {pmatrix} a \\ b \ end {pmatrix}} = \ mathbf {M} {\ begin {pmatrix} r_ {N-1} \\ 0 \ end {pmatrix}} = \ mathbf { M} {\ begin {pmatrix} g \\ 0 \ end {pmatrix}} \ ,.}

Pro expresi g jako lineární součet a B , obě strany této rovnice lze vynásobit inverzní matricového M . Determinant z M se rovná (1) ^N¹ , protože se rovná součinu determinant kvocient matric, z nichž každý je negativní. Protože determinant M není nikdy nula, vektor konečných zbytků lze vyřešit pomocí inverzní funkce M

{\ Displaystyle {\ begin {pmatrix} g \\ 0 \ end {pmatrix}} = \ mathbf {M} ^{-1} {\ begin {pmatrix} a \\ b \ end {pmatrix}} = (-1 )^{N+1} {\ begin {pmatrix} m_ {22} &-m_ {12} \\-m_ {21} & m_ {11} \ end {pmatrix}} {\ begin {pmatrix} a \\ b \ end {pmatrix}} \ ,.}

Protože horní rovnice dává

g = (-1) N +1 (m 22 a - m 12 b),

obě celá čísla bézoutova rovnost jsou y = (-1) ^{N + 1}m ₂₂ a t = (-1) ^N m ₁₂ . Maticová metoda je stejně účinná jako ekvivalentní rekurze, se dvěma násobeními a dvěma přírůstky na krok euklidovského algoritmu.

Euclidovo lemma a jedinečná faktorizace

Bézoutova identita je nezbytná pro mnoho aplikací Euclidova algoritmu, například pro demonstraci jedinečné faktorizace čísel na primární faktory. Pro ilustraci předpokládejme, že číslo L lze zapsat jako součin dvou faktorů u a v , tj. L = uv . Pokud jiné číslo w také dělí L, ale je coprime s u , pak w musí dělit v , následujícím argumentem: Je -li největší společný dělitel u a w 1, pak lze najít celá čísla s a t tak, že

1 = su + tw .

podle Bézoutovy identity. Vynásobením obou stran v získáte vztah

v = suv + twv = sL + twv .

Protože w dělí oba výrazy na pravé straně, musí také rozdělit levou stranu, v . Tento výsledek je známý jako Euclidovo lemma . Konkrétně, pokud je prvočíslo rozdělí L , pak to musí rozdělit alespoň jeden faktor L . A naopak, pokud je číslo w coprime pro každou z řady čísel a ₁ , a ₂ , ..., a _n , pak w je také coprime pro jejich součin, a ₁ × a ₂ × ... × a _n .

Euclidovo lemma stačí k prokázání, že každé číslo má jedinečnou faktorizaci na prvočísla. Abychom to viděli, předpokládejme opak, že existují dvě nezávislé faktorizace L na m a n primárních faktorů

L = p 1 p 2 \dots p m = q 1 q 2 \dots q n .

Protože každé prvočíslo p dělí L za předpokladu, musí také rozdělit jeden z faktorů q ; protože každé q je také prvočíslo, musí to být tak, že p = q . Iterativně dělené p faktory ukazuje, že každé p má stejný protějšek q ; obě hlavní faktorizace jsou až na jejich pořadí totožné. Unikátní faktorizace čísel na prvočísla má mnoho aplikací v matematických důkazech, jak je uvedeno níže.

Lineární diofantické rovnice

Graf lineární diofantické rovnice , 9 x + 12 y = 483. Roztoky jsou znázorněny jako modré kruhy.

Diofantické rovnice jsou rovnice, ve kterých jsou řešení omezena na celá čísla; jsou pojmenovány podle alexandrijského matematika 3. století Diophanta . Typická lineární diofantinická rovnice hledá celá čísla x a y taková, že

ax + o = c

kde a , b a c jsou dána celá čísla. To lze zapsat jako rovnici pro x v modulární aritmetice :

sekera \equiv c mod b .

Nechť g je největší společný dělitel a a b . Oba výrazy v ax + by byly dělitelné g ; proto musí být c také dělitelné g , nebo rovnice nemá řešení. Vydělením obou stran c / g lze rovnici redukovat na Bezoutovu identitu

sa + tb = g

kde s a t lze nalézt rozšířeným euklidovským algoritmem . To poskytuje jedno řešení diophantské rovnice, x ₁ = s ( c / g ) a y ₁ = t ( c / g ).

Lineární diofantická rovnice obecně nemá žádná řešení nebo nekonečný počet řešení. Chcete -li najít to druhé, zvažte dvě řešení, ( x ₁ , y ₁ ) a ( x ₂ , y ₂ ), kde

sekera 1 + o 1 = c = sekera 2 + o 2

nebo ekvivalentně

a (x 1 - x 2) = b (y 2 - y 1).

Nejmenší rozdíl mezi dvěma řešeními x je tedy b / g , zatímco nejmenší rozdíl mezi dvěma řešeními y je a / g . Řešení tedy mohou být vyjádřena jako

x = x 1 - bu / g

y = y 1 + au / g

.

Tím, že se u může měnit ve všech možných celých číslech, lze z jednoho řešení ( x ₁ , y ₁ ) generovat nekonečnou rodinu řešení . Pokud jsou požadována řešení jako kladná celá čísla ( x > 0, y > 0), může být možný pouze konečný počet řešení. Toto omezení přijatelných řešení umožňuje některým systémům diofantických rovnic s více neznámými než rovnicemi mít konečný počet řešení; to je nemožné pro systém lineárních rovnic, když řešení může být jakékoli reálné číslo (viz Nedeterminovaný systém ).

Multiplikativní inverze a algoritmus RSA

Konečné pole je sada čísel se čtyřmi všeobecných operací. Operace se nazývají sčítání, odčítání, násobení a dělení a mají své obvyklé vlastnosti, jako je komutativita , asociativita a distribučnost . Příkladem konečného pole je sada 13 čísel {0, 1, 2, ..., 12} využívajících modulární aritmetiku . V tomto poli jsou výsledky jakékoli matematické operace (sčítání, odčítání, násobení nebo dělení) redukovány modulo 13; to znamená, že násobky 13 se sčítají nebo odčí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 jakékoli prvočíslo p ; za použití složitějších definic, oni mohou také být definovány pro každou napájecí m o lukrativní p ^m . Konečná pole se často nazývají Galoisova pole a jsou zkrácena jako GF ( p ) nebo GF ( p ^m ).

V takovém poli s m čísly má každý nenulový prvek a jedinečnou modulární multiplikativní inverzi , a ⁻¹ takovou, že aa ⁻¹ = a ⁻¹a ≡ 1 mod m . Tuto převrácenou hodnotu lze najít řešením osy kongruenční rovnice ≡ 1 mod m nebo ekvivalentní lineární diofantické rovnice

sekera + my = 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 algoritmu RSA , který je široce používán v elektronickém obchodování ; konkrétně rovnice určuje celé číslo použité k dešifrování zprávy. Ačkoli algoritmus RSA používá spíše prstence než pole, euklidovský algoritmus lze stále použít k nalezení multiplikativní inverze tam, kde existuje. Euklidovský algoritmus má také další aplikace v kódech opravujících chyby ; může být například použit jako alternativa k algoritmu Berlekamp – Massey pro dekódování kódů BCH a Reed – Solomon , které jsou založeny na Galoisových polích.

Čínská věta o zbytku

Euklidův algoritmus lze také použít k řešení více lineárních diofantických rovnic. Takové rovnice vznikají v čínské větě o zbytku , která popisuje novou metodu pro reprezentaci celého čísla x . Místo toho, aby reprezentoval celé číslo jeho číslicemi, může být reprezentováno jeho zbytky x _i modulo sadu N coprime čísel m _i :

{\ Displaystyle {\ begin {aligned} x_ {1} & \ equiv x {\ pmod {m_ {1}}} \\ x_ {2} & \ equiv x {\ pmod {m_ {2}}} \\ & \, \, \, \ vdots \\ x_ {N} & \ equiv x {\ pmod {m_ {N}}} \,. \ end {aligned}}}

Cílem je určit x z jeho N zbytků x _i . Řešením je spojit více rovnic do jedné lineární diofantické rovnice s mnohem větším modulem M, který je součinem všech jednotlivých modulů m _i , a definovat M _i jako

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

Každé M _i je tedy součinem všech modulů kromě m _i . Řešení závisí na zjištění N nová čísla h _i tak, že

{\ Displaystyle M_ {i} h_ {i} \ equiv 1 {\ pmod {m_ {i}}} \ ,.}

S těmito čísly h _i může být celé číslo x rekonstruováno z jeho zbytků x _i pomocí rovnice

{\ Displaystyle x \ equiv (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í inverze M _i , lze je nalézt pomocí Euclidova algoritmu, jak je popsáno v předchozím pododdíle.

Stern – Brocot strom

Euklidovský algoritmus lze použít k uspořádání sady všech kladných racionálních čísel do nekonečného binárního vyhledávacího stromu , který se nazývá Stern – Brocotův strom . Číslo 1 (vyjádřeno jako zlomek 1/1) je umístěno v kořeni stromu a umístění libovolného jiného čísla a / b lze zjistit výpočtem gcd ( a , b ) pomocí původní podoby euklidovského algoritmu , ve kterém každý krok nahradí větší ze dvou daných čísel svým rozdílem s menším číslem (nikoli jeho zbytkem), přičemž se zastaví, když je dosaženo dvou stejných čísel. Krok euklidovského algoritmu, který nahrazuje první ze dvou čísel, odpovídá kroku ve stromu od uzlu k jeho pravému dítěti a krok, který nahrazuje druhé ze dvou čísel, odpovídá kroku ve stromu z uzlu svému levému dítěti. Sekvence takto konstruovaných kroků nezávisí na tom, zda je a / b zadána v nejnižších termínech, a tvoří cestu od kořene k uzlu, který obsahuje číslo a / b . Tuto skutečnost lze použít k prokázání, že každé kladné racionální číslo se v tomto stromu objeví přesně jednou.

Například 3/4 lze najít tak, že začnete u kořene, jednou přejdete doleva a pak dvakrát doprava:

Stern – Brocotův strom a Stern – Brocotův sled pořadí i pro i = 1, 2, 3, 4

{\ Displaystyle {\ begin {aligned} & \ gcd (3,4) & \ leftarrow \\ = {} & \ gcd (3,1) & \ rightarrow \\ = {} & \ gcd (2,1) & \ rightarrow \\ = {} & \ gcd (1,1). \ end {aligned}}}

Euklidovský algoritmus má téměř stejný vztah k jinému binárnímu stromu na racionálních číslech nazývaných Calkin -Wilfův strom . Rozdíl je v tom, že cesta je obrácená: namísto vytvoření cesty z kořene stromu k cíli vytvoří cestu z cíle do kořene.

Pokračující zlomky

Euklidovský algoritmus má úzký vztah s pokračujícími zlomky . Posloupnost rovnic lze zapsat do formuláře

{\ displaystyle {\ begin {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}}}

Poslední výraz na pravé straně se vždy rovná inverzi levé strany další rovnice. První dvě rovnice lze tedy zkombinovat a vytvořit

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

Třetí rovnici lze použít k nahrazení jmenovatele výrazem r ₁ / r ₀ , čímž se získá

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

Konečný poměr zbytků r _k / r _{k −1} lze vždy nahradit pomocí další rovnice v řadě až do konečné rovnice. Výsledkem je pokračující zlomek

{\ 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}] \ ,. }

Ve výše uvedeném zpracovaném příkladu byl vypočítán gcd (1071, 462) a kvocienty q _k byly 2, 3 a 7. Proto může být zapsán zlomek 1071/462

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

jak lze potvrdit výpočtem.

Faktorizační algoritmy

Výpočet největšího společného dělitele je zásadním krokem v několika celočíselných faktorizačních algoritmech, jako je Pollardův rho algoritmus , Shorův algoritmus , Dixonova faktorizační metoda a Lenstraova eliptická křivková faktorizace . K efektivnímu nalezení tohoto GCD lze použít euklidovský algoritmus. Faktorizace pokračující frakce používá pokračující frakce, které jsou určeny pomocí Euclidova algoritmu.

Algoritmická účinnost

Počet kroků v euklidovském algoritmu pro gcd ( x , y ). Světlejší (červené a žluté) body označují relativně málo kroků, zatímco tmavší (fialové a modré) body označují více kroků. Největší tmavá oblast sleduje čáru y = Φx , kde Φ je zlatý řez .

Výpočtová účinnost Euclidova algoritmu byla důkladně studována. Tuto účinnost lze popsat počtem kroků dělení, které algoritmus vyžaduje, vynásobenými výpočetními náklady každého kroku. První známá analýza Euclidova algoritmu je dána AAL Reynaudem v roce 1811, který ukázal, že počet kroků dělení na vstupu ( u , v ) je ohraničen v ; později to vylepšil na v /2 + 2. Později, v roce 1841, PJE Finck ukázal, že počet kroků dělení je maximálně 2 log ₂ v + 1, a proto Euclidův algoritmus běží v čase polynom ve velikosti vstupu. Émile Léger , v roce 1837, studoval nejhorší případ, kdy vstupy jsou po sobě jdoucí Fibonacciho čísla . Finckovu analýzu zpřesnil Gabriel Lamé v roce 1844, který ukázal, že počet kroků potřebných k dokončení není nikdy větší než pětinásobek počtu h základny-10 číslic menšího počtu b .

V modelu jednotných nákladů (vhodný pro analýzu složitosti výpočtu gcd na číslech, která se vejdou do jednoho strojového slova) trvá každý krok algoritmu konstantní čas a z Lamého analýzy vyplývá, že celková doba běhu je také O ( h ). V modelu výpočtu vhodného pro výpočet s většími čísly však mohou být výpočetní náklady na jeden zbývající výpočet v algoritmu stejně velké jako O ( h ² ). V tomto případě lze celkový čas pro všechny kroky algoritmu analyzovat pomocí teleskopické řady , což ukazuje, že je také O ( h ² ). K urychlení lze použít moderní algoritmické techniky založené na Schönhage -Strassenově algoritmu pro rychlé celočíselné násobení, což vede k kvazilineárním algoritmům pro GCD.

Počet kroků

Počet kroků pro výpočet GCD dvou přirozených čísel a a b může být označen T ( a , b ). Pokud g je GDC a B , pak = mg a b = ng dva coprime čísel m a n . Pak

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

jak lze vidět vydělením všech kroků v euklidovském algoritmu g . Podle stejného argumentu zůstává počet kroků stejný, pokud a a b jsou vynásobeny společným faktorem w : T ( a , b ) = T ( wa , wb ). Počet kroků T se proto může dramaticky lišit mezi sousedními dvojicemi čísel, jako jsou T ( a , b ) a T ( a , b + 1), v závislosti na velikosti dvou GCD.

Rekurzivní povaha euklidovského algoritmu dává další 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.

Nejhorší případ

Pokud euklidovská algoritmus vyžaduje N kroky pro dvojici přirozených čísel > b > 0, nejmenší hodnoty a b , pro které je to pravda, jsou čísla Fibonacci F _N₂ a F _N₁ , v tomto pořadí. Přesněji, pokud euklidovský algoritmus vyžaduje N kroků pro pár a > b , pak má jeden a ≥ F _N₊₂ a b ≥ F _N₊₁ . To lze ukázat indukcí . Pokud N = 1, b rozdělí a beze zbytku; nejmenší přirozená čísla, pro která to platí, je b = 1 a a = 2, což jsou F ₂ a F ₃ . Nyní předpokládejme, že výsledek platí pro všechny hodnoty N až M - 1. První krok M -Krok algoritmu je = q ₀b + r ₀ , a Euclidean algoritmus vyžaduje M - 1 stupni pro páru b > r ₀ . Indukcí hypotézy, musí b ≥ F _M_{+ 1} a r ₀ ≥ F _M . Proto a = q ₀b + r ₀ ≥ b + r ₀ ≥ F _M₊₁ + F _M = F _M₊₂ , což je požadovaná nerovnost. Tento důkaz, který vydal Gabriel Lamé v roce 1844, představuje počátek teorie výpočetní složitosti a také první praktickou aplikaci Fibonacciho čísel.

Tento výsledek stačí k prokázání, že počet kroků v Euclidově algoritmu nemůže být nikdy větší než pětinásobek počtu jeho číslic (základ 10). Pokud algoritmus vyžaduje N kroků, pak b je větší nebo rovno F _{N +1,} což je zase větší nebo rovno φ ^{N −1} , kde φ je zlatý poměr . Protože b ≥ φ ^{N −1} , pak N - 1 ≤ log _φ b . Protože log ₁₀φ > 1/5, ( N - 1)/5 <log ₁₀φ log _φ b = log ₁₀b . Tedy N ≤ 5 log ₁₀b . Euklidovský algoritmus tedy vždy potřebuje méně než O ( h ) dělení, kde h je počet číslic v menším počtu b .

Průměrný

Průměrný počet kroků provedených euklidovským algoritmem byl definován třemi různými způsoby. První definice je průměrná doba T ( ) potřebná pro výpočet GCD daného čísla A a menší přirozené číslo B zvolený se stejnou pravděpodobností z celých čísel 0 až - 1

{\ Displaystyle T (a) = {\ frac {1} {a}} \ sum _ {0 \ leq b <a} T (a, b).}

Protože však T ( a , b ) dramaticky kolísá s GCD těchto dvou čísel, průměrná funkce T ( a ) je rovněž "hlučná".

Aby se tento hluk snížil, převezme druhý průměr τ ( a ) všechna čísla souběžně s a

{\ Displaystyle \ tau (a) = {\ frac {1} {\ varphi (a)}} \ sum _ {\ begin {smallmatrix} 0 \ leq b <a \\\ gcd (a, b) = 1 \ end {smallmatrix}} T (a, b).}

Existuje φ ( a ) coprime celá čísla menší než a , kde φ je Eulerova totientová funkce . Tento tau průměr roste hladce s a

{\ Displaystyle \ tau (a) = {\ frac {12} {\ pi ^{2}}} \ ln 2 \ ln a+C+O (a ^{-1/6- \ varepsilon})}}

přičemž zbytková chyba je řádu a ^{- (1/6) + ε} , kde ε je nekonečně malé . Konstanta C ( Porterova konstanta ) v tomto vzorci se rovná

{\ Displaystyle C = -{\ frac {1} {2}}+{\ frac {6 \ ln 2} {\ pi ^{2}}} \ left (4 \ gamma -{\ frac {24} {\ pi ^{2}}} \ zeta '(2) +3 \ ln 2-2 \ vpravo) \ cca 1,467}

kde γ je Euler – Mascheroniho konstanta a ζ 'je derivát funkce Riemannova zeta . Úvodní koeficient (12/π ² ) ln 2 byl určen dvěma nezávislými metodami.

Protože první průměr se může vypočítat z tau průměru jako součet za dělitele d z A

{\ Displaystyle T (a) = {\ frac {1} {a}} \ sum _ {d \ mid a} \ varphi (d) \ tau (d)}

lze to aproximovat podle vzorce

{\ Displaystyle T (a) \ cca C+{\ frac {12} {\ pi ^{2}}} \ ln 2 \ left (\ ln a-\ sum _ {d \ mid a} {\ frac {\ Lambda (d)} {d}} \ vpravo)}

kde Λ ( d ) je Mangoldtova funkce .

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

{\ 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).}

Dosazením přibližného vzorce pro T ( a ) do této rovnice se získá odhad pro Y ( n )

{\ Displaystyle Y (n) \ zhruba {\ frac {12} {\ pi ^{2}}} \ ln 2 \ ln n+0,06.}

Výpočetní náklady na krok

V každém kroku k euklidovského algoritmu se vypočítá kvocient q _k a zbytek r _k pro daný pár celých čísel r _{k −2} a r _{k −1}

r k -2 = q k r k -1 + r k .

Výpočetní náklady na krok jsou spojeny hlavně s nalezením q _k , protože zbytek r _k lze rychle vypočítat z r _{k −2} , r _{k −1} a q _k

r k = r k -2 - q k r k -1 .

Výpočetní náklady na dělení h -bitových čísel se škálují na O ( h ( ℓ +1)), kde ℓ je délka kvocientu.

Pro srovnání, Euclidův původní algoritmus založený na odčítání může být mnohem pomalejší. Jediné celočíselné dělení je ekvivalentní kvocientu q počtu odčítání. V případě, že poměr A a B je velmi velký, kvocient je velký a bude vyžadovat mnoho odčítání. Na druhé straně se ukázalo, že kvocienty jsou velmi pravděpodobně malá celá čísla. Pravděpodobnost daného kvocientu q je přibližně ln | u /( u - 1) | kde u = ( q + 1) ² . Pro ilustraci je pravděpodobnost kvocientu 1, 2, 3 nebo 4 zhruba 41,5%, 17,0%, 9,3%, respektive 5,9%. Protože operace odčítání je rychlejší než dělení, zvláště u velkých čísel, je Euclidův algoritmus založený na odčítání konkurenceschopný s verzí založenou na dělení. Toho se využívá v binární verzi Euclidova algoritmu.

Kombinace odhadovaného počtu kroků s odhadovanými výpočetními náklady na krok ukazuje, že Euclidův algoritmus roste kvadraticky ( h ² ) s průměrným počtem číslic h v počátečních dvou číslech a a b . Nechť h ₀ , h ₁ , ..., h _{N −1} představují počet číslic v po sobě jdoucích zbytcích r ₀ , r ₁ , ..., r _{N −1} . Protože počet kroků N roste lineárně s h , doba běhu je ohraničena

{\ Displaystyle O {\ Big (} \ sum _ {i <N} h_ {i} (h_ {i} -h_ {i+1} +2) {\ Big)} \ subseteq O {\ Big (} h \ sum _ {i <N} (h_ {i} -h_ {i+1} +2) {\ Big)} \ subseteq O (h (h_ {0}+2N)) \ subseteq O (h^{2 }).}

Alternativní metody

Euclidův algoritmus je díky své jednoduchosti v praxi široce používán, zejména pro malá čísla. Pro srovnání lze určit účinnost alternativ k Euclidovu algoritmu.

Jeden neefektivní přístup k nalezení GCD dvou přirozených čísel a a b je vypočítat všechny jejich společné dělitele; GCD je pak největším společným dělitelem. Společné dělitele lze nalézt vydělením obou čísel postupnými celými čísly od 2 do menšího čísla b . Počet kroků tohoto přístupu roste lineárně s b , nebo exponenciálně v počtu číslic. Dalším neefektivním přístupem je najít primární faktory jednoho nebo obou čísel. Jak bylo uvedeno výše , GCD se rovná součinu hlavních faktorů sdílených dvěma čísly a a b . Současné metody primární faktorizace jsou také neúčinné; mnoho moderních kryptografických systémů na tuto neefektivitu dokonce spoléhá.

Binární GCD algoritmus je účinná alternativa, která náhražky divize s rychlejšími operací tím, že využívá binární reprezentaci používanou počítači. Tato alternativa však má také měřítko jako O ( h ²) . Je obecně rychlejší než euklidovský algoritmus na skutečných počítačích, i když se škáluje stejným způsobem. Dodatečnou efektivitu lze získat prozkoumáním pouze úvodních číslic dvou čísel a a b . Binární algoritmus lze rozšířit na další báze ( k -ary algoritmy), a to až pětinásobným zvýšením rychlosti. Lehmerův GCD algoritmus používá stejný obecný princip jako binární algoritmus k urychlení výpočtů GCD v libovolných základnách.

Rekurzivní přístup pro velmi velká celá čísla (s více než 25 000 číslicemi) vede k kvasilineárním celočíselným GCD algoritmům, jako jsou Schönhage a Stehlé a Zimmermann. Tyto algoritmy využívají maticovou formu 2 × 2 euklidovského algoritmu uvedeného výše . Tyto kvazilineární metody se obecně měří jako O ( h (log h ) ² (log log h )).

Zobecnění

Přestože se k nalezení největšího společného dělitele dvou přirozených čísel (kladná celá čísla) používá euklidovský algoritmus, lze jej zobecnit na skutečná čísla a na další matematické objekty, jako jsou polynomy , kvadratická celá čísla a Hurwitzovy kvaterniony . V posledně jmenovaných případech se používá euklidovský algoritmus k prokázání zásadní vlastnosti jedinečné faktorizace, tj. Že taková čísla lze jedinečně rozdělit na neredukovatelné prvky , protějšky prvočísel. Unikátní faktorizace je nezbytná pro mnoho důkazů teorie čísel.

Racionální a reálná čísla

Euclidův algoritmus lze aplikovat na reálná čísla , jak popsal Euclid v knize 10 jeho prvků . Cílem algoritmu je identifikovat skutečné číslo $g$ tak, aby dvě daná reálná čísla $a$ a $b$ byla celočíselnými násobky: $a = mg$ a $b = ng$ , kde $m$ a $n$ jsou celá čísla . Tato identifikace je ekvivalentní nalezení celočíselného vztahu mezi reálnými čísly $a$ a $b$ ; to znamená, že určuje celá čísla $s$ a $t$ taková, že $sa + tb = 0$ . Euclid používá tento algoritmus k řešení otázky nesouměřitelných délek .

Euklidovský algoritmus skutečného čísla se liší od svého celočíselného protějšku ve dvou ohledech. Za prvé, zbytky $r k$ jsou reálná čísla, ačkoli kvocienty $q k$ jsou celá čísla jako dříve. Za druhé, není zaručeno, že algoritmus skončí konečným počtem $N$ kroků. Pokud ano, zlomek $a / b$ je racionální číslo, tj. Poměr dvou celých čísel

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

a lze jej zapsat jako konečný pokračující zlomek $[q 0; q 1, q 2, ..., q N]$ . Pokud se algoritmus nezastaví, zlomek $a / b$ je iracionální číslo a lze jej popsat nekonečným pokračujícím zlomkem $[q 0; q 1, q 2,\dots]$ . Příklady nekonečných pokračujících zlomků jsou zlatý řez $φ = [1; 1, 1, ...]$ a odmocnina ze dvou , $\sqrt 2 = [1; 2, 2, ...]$ . Algoritmus se pravděpodobně nezastaví, protože téměř všechny poměry $a / b$ dvou reálných čísel jsou iracionální.

Nekonečná pokračující frakce může být zkrácena v kroku $k [q 0; Q 1, Q 2, ..., q K]$ , čímž se získá aproximace $v / b$ , který zlepšuje jak $k$ se zvyšuje. Aproximaci popisují konvergenty $m k / n k$ ; čitatel a jmenovatelé jsou souběžní a dodržují relaci opakování

{\ Displaystyle {\ begin {aligned} m_ {k} & = q_ {k} m_ {k-1}+m_ {k-2} \\ n_ {k} & = q_ {k} n_ {k-1} +n_ {k-2}, \ end {zarovnáno}}}

kde $m -1 = n -2 = 1$ a $m -2 = n -1 = 0$ jsou počáteční hodnoty rekurze. Konvergentní $m k / n k$ je nejlepší aproximací racionálního čísla k $a / b$ se jmenovatelem $n k$ :

{\ Displaystyle \ left | {\ frac {a} {b}}-{\ frac {m_ {k}} {n_ {k}}} \ right | <{\ frac {1} {n_ {k}^{ 2}}}.}

Polynomy

Polynomy v jedné proměnné x lze sčítat, násobit a rozdělovat na neredukovatelné polynomy , což jsou analogie prvočísel pro celá čísla. Největší společný dělitelný polynom $g (x)$ dvou polynomů $a (x)$ a $b (x)$ je definován jako součin jejich sdílených neredukovatelných polynomů, které lze identifikovat pomocí euklidovského algoritmu. Základní postup je podobný jako u celých čísel. V každém kroku $k$ je identifikován kvocient polynomu $q k (x)$ a zbývající polynom $r k (x),$ aby byla splněna rekurzivní rovnice

{\ Displaystyle r_ {k-2} (x) = q_ {k} (x) r_ {k-1} (x)+r_ {k} (x),}

kde $r -2 (x) = a (x)$ a $r -1 (x) = b (x)$ . Každý kvocient polynomu je vybrán tak, že každý zbytek je buď nula, nebo má stupeň, který je menší než stupeň jeho předchůdce: $deg [r k (x)] <deg [r k -1 (x)]$ . Protože stupeň je nezáporné celé číslo a protože klesá s každým krokem, euklidovský algoritmus končí v konečném počtu kroků. Poslední nenulový zbytek je největším společným dělitelem původních dvou polynomů, $a (x)$ a $b (x)$ .

Zvažte například následující dva kvartické polynomy, z nichž každý součiní dva kvadratické polynomy

{\ Displaystyle {\ begin {aligned} a (x) & = x^{4} -4x^{3}+4x^{2} -3x+14 = (x^{2} -5x+7) (x ^{2}+x+2) \ qquad {\ text {a}} \\ b (x) & = x^{4}+8x^{3}+12x^{2}+17x+6 = (x ^{2}+7x+3) (x^{2}+x+2). \ End {zarovnaný}}}

Dělení $se (x)$ o $b (x)$ se získá zbytkové $r 0 (x) = x 3 + (2/3) x 2 + (5/3) x - (2/3)$ . V dalším kroku je $b (x)$ děleno $r 0 (x),$ čímž se získá zbytek $r 1 (x) = x 2 + x + 2$ . A konečně, dělení $r 0 (x)$ o $r 1 (x)$ se získá zbytek nula, což ukazuje, že $R 1 (x)$ je největší společný dělitel polynomu $a (x)$ a $b (x)$ , v souladu s jejich faktorizace.

Mnoho z aplikací popsaných výše pro celá čísla se přenáší na polynomy. Euklidovský algoritmus lze použít k řešení lineárních diofantických rovnic a čínských zbývajících problémů pro polynomy; lze definovat i pokračující zlomky polynomů.

Polynomiální euklidovský algoritmus má další aplikace, například Sturmovy řetězce , metodu pro počítání nul polynomu, které leží uvnitř daného reálného intervalu . To zase má aplikace v několika oblastech, jako je kritérium stability Routh – Hurwitz v teorii řízení .

Koeficienty polynomů nakonec nemusí být čerpány z celých čísel, reálných čísel nebo dokonce komplexních čísel. Koeficienty mohou být například čerpány z obecného pole, jako jsou konečná pole $GF (p)$ popsaná výše. Odpovídající závěry o euklidovském algoritmu a jeho aplikacích platí i pro takové polynomy.

Gaussova celá čísla

Distribuce Gaussových prvočísel

u + vi

v komplexní rovině, s normami

u 2 + v 2

menší než 500

Gaussova celá čísla jsou komplexní čísla tvaru $α = u + vi$ , kde $u$ a $v$ jsou obyčejná celá čísla a $i$ je druhá odmocnina záporného čísla . Definováním analogu euklidovského algoritmu lze Gaussova celá čísla ukázat jako jednoznačně faktorizovatelná, a to výše uvedeným argumentem . Tato jedinečná faktorizace je užitečná v mnoha aplikacích, jako je odvozování všech Pythagorových trojic nebo dokazování Fermatovy věty na součtech dvou čtverců . Euclidovský algoritmus je v takových aplikacích obecně vhodný, ale není nezbytný; například věty lze často dokázat jinými argumenty.

Euklidovský algoritmus vyvinutý pro dvě Gaussova celá čísla $α$ a $β$ je téměř stejný jako pro běžná celá čísla, ale liší se ve dvou ohledech. Stejně jako dříve je úkolem v každém kroku $k$ identifikovat kvocient $q k$ a zbytek $r k$ tak, že

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

kde $r k -2 = α$ , kde $r k -1 = β$ a kde každý zbytek je přísně menší než jeho předchůdce: $| r k | <| r k -1 |$ . Prvním rozdílem je, že kvocienty a zbytky jsou samy o sobě Gaussovými celými čísly, a jsou tedy komplexními čísly . Kvocienty $q k$ se obecně nacházejí zaokrouhlováním reálných a komplexních částí přesného poměru (například komplexního čísla $α / β$ ) na nejbližší celá čísla. Druhý rozdíl spočívá v nutnosti definovat, jak může být jeden komplexní zbytek „menší“ než druhý. K tomu je definována normální funkce $f (u + vi) = u 2 + v 2$ , která převede každé Gaussovo celé číslo $u + vi$ na obyčejné celé číslo. Po každém kroku $k$ euklidovského algoritmu je norma zbytku $f (r k)$ menší než norma předchozího zbytku $f (r k -1)$ . Protože norma je nezáporné celé číslo a klesá s každým krokem, končí euklidovský algoritmus pro Gaussova celá čísla konečným počtem kroků. Konečný nenulový zbytek je $gcd (α, β)$ , Gaussovo celé číslo největší normy, které dělí $α$ a $β$ ; je jedinečný až do násobení jednotkou, $\pm 1$ nebo $\pm i$ .

Mnoho dalších aplikací euklidovského algoritmu se přenáší na Gaussova celá čísla. Může být například použit k řešení lineárních diofantických rovnic a čínských zbývajících problémů pro Gaussova celá čísla; lze také definovat pokračující zlomky Gaussových celých čísel.

Euklidovské domény

Sada prvků pod dvěma binárními operacemi , označovaná jako sčítání a násobení, se nazývá euklidovská doména, pokud tvoří komutativní kruh $R$ a zhruba řečeno, lze -li na nich provést generalizovaný euklidovský algoritmus. Dvě operace takového prstence nemusí být sčítání a násobení běžné aritmetiky; spíše mohou být obecnější, například operace matematické skupiny nebo monoidu . Tyto obecné operace by však měly respektovat mnoho zákonů, kterými se řídí běžná aritmetika, jako je komutativita , asociativita a distribučnost .

Zobecněný euklidovský algoritmus vyžaduje euklidovskou funkci , tj. Mapování $f$ z $R$ do množiny nezáporných celých čísel tak, že pro jakékoli dva nenulové prvky $a$ a $b$ v $R$ existují $q$ a $r$ v $R$ tak, že $a = qb + r$ a $f (r) < f (b)$ . Příklady takových mapování jsou absolutní hodnota pro celá čísla, stupeň pro univariantní polynomy a norma pro Gaussova celá čísla výše . Základním principem je, že každý krok algoritmu neúprosně snižuje f ; pokud tedy lze $f$ omezit pouze na konečný počet opakování, musí se algoritmus zastavit v konečném počtu kroků. Tento princip se opírá o dobře uspořádanou vlastnost nezáporných celých čísel, která tvrdí, že každá neprázdná sada nezáporných celých čísel má nejmenšího člena.

Základní teorém aritmetiky se vztahuje na všechny euklidovský domény: Jedno číslo od euklidovské domény mohou být zapracovány do jednoznačně nerozložitelné prvky . Jakákoli euklidovská doména je jedinečnou faktorizační doménou (UFD), ačkoli opak není pravdivý. Euklidovské domény a UFD jsou podtřídy GCD domén , domén, ve kterých vždy existuje největší společný dělitel dvou čísel. Jinými slovy, může existovat největší společný dělitel (pro všechny páry prvků v doméně), i když to nemusí být možné najít pomocí euklidovského algoritmu. Euclidean doména je vždy hlavní domény ideální (PID), což je integrální doménu , ve které každý ideální je hlavní ideální . Opět platí, že opak není pravdivý: ne každý PID je euklidovská doména.

Unikátní faktorizace euklidovských domén je užitečná v mnoha aplikacích. Unikátní faktorizace Gaussových celých čísel je například výhodná při odvozování vzorců pro všechny Pythagorovy trojky a při dokazování Fermatovy věty o součtech dvou čtverců . Unikátní faktorizace byla také klíčovým prvkem při pokusu o důkaz Fermatovy poslední věty publikované v roce 1847 Gabrielem Lamé, stejným matematikem, který analyzoval účinnost Euclidova algoritmu na základě návrhu Josepha Liouville . Přístup lame je nutné jedinečnou faktorizaci čísel tvaru $x + ωy$ , kde $x$ a $y$ jsou celá čísla, a $ω = e 2 iπ / n$ je $n$ th kořen 1, to znamená, že $ω n = 1$ . I když tento přístup úspěšný pro některé hodnoty $n$ (jako je $n = 3$ , se Eisenstein celá čísla ), obecně počtech dělat ne faktor jednoznačně. Toto selhání jedinečné faktorizace v některých cyklotomických polích vedlo Ernsta Kummera ke konceptu ideálních čísel a později Richarda Dedekinda k ideálům .

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

Distribuce Eisensteinových prvočísel

u + vω

v komplexní rovině s normami menšími než 500. Číslo

ω

je odmocnina z 1 .

Tyto kvadratické celočíselné kroužky jsou užitečné pro ilustraci Euclidean domény. Kvadratická celá čísla jsou zobecněními Gaussových celých čísel, ve kterých je imaginární jednotka i nahrazena číslem $ω$ . Tak mají tvar $U + vω$ , kde $u$ a $v$ jsou celá čísla a $ω$ má jednu ze dvou forem, v závislosti na parametru $D$ . Pokud se $D$ nerovná násobku čtyř plus jedna, pak

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

Pokud se však D rovná násobku čtyř plus jedna, pak

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

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

Pokud $f$ může být jakákoli euklidovská funkce, pak seznam možných hodnot $D,$ pro které je doména euklidovská, ještě není znám. První příklad euklidovské domény, která nebyla normálně-euklidovská (s $D = 69$ ), byl publikován v roce 1994. V roce 1973 Weinberger dokázal, že kvadratický celočíselný prstenec s $D > 0$ je euklidovský, a pouze pokud je to principál ideální doména , za předpokladu, že zobecněná Riemannova hypotéza platí.

Nekomutativní prsteny

Euklidovský algoritmus může být aplikován na některé nekomutativní prstence, jako je sada Hurwitzových čtveřic . Nechť $α$ a $β$ představují dva prvky z takového kruhu. Mají společný pravý dělitel $δ,$ pokud $α = ξδ$ a $β = ηδ$ pro nějakou volbu $ξ$ a $η$ v kruhu. Podobně mají společného levého dělitele, pokud $α = dξ$ a $β = dη$ pro určitou volbu $ξ$ a $η$ v kruhu. Vzhledem k tomu, že násobení není komutativní, existují dvě verze euklidovského algoritmu, jedna pro pravé dělitele a druhá pro levé dělitele. Výběr správných dělitelů, první krok při hledání $gcd (α, β)$ pomocí euklidovského algoritmu, lze zapsat

{\ Displaystyle \ rho _ {0} = \ alpha -\ psi _ {0} \ beta = (\ xi -\ psi _ {0} \ eta) \ delta,}

kde $ψ 0$ představuje kvocient a $ρ 0$ zbytek. Tato rovnice ukazuje, že jakýkoli společný pravý dělitel $α$ a $β$ je rovněž společným dělitelem zbytku $ρ 0$ . Analogická rovnice pro levé dělitele by byla

{\ Displaystyle \ rho _ {0} = \ alpha -\ beta \ psi _ {0} = \ delta (\ xi -\ eta \ psi _ {0}).}

U každé volby se postup opakuje, jak je uvedeno výše, dokud není identifikován největší společný pravý nebo levý dělitel. Stejně jako v euklidovské doméně musí být „velikost“ zbytku $ρ 0$ (formálně jeho norma ) přísně menší než $β$ a pro $ρ 0$ musí existovat pouze konečný počet možných velikostí , aby byl algoritmus zaručen vypovědět.

Většina výsledků pro GCD se přenáší na nekomutativní čísla. Například identita Bézout se uvádí, že pravý $gcd (α, β)$ může být vyjádřena jako lineární kombinace $alfa$ a $beta$ . Jinými slovy, existují čísla $σ$ a $τ$ taková, že

{\ Displaystyle \ Gamma _ {\ text {right}} = \ sigma \ alpha +\ tau \ beta.}

Analogická identita levého GCD je téměř stejná:

{\ Displaystyle \ Gamma _ {\ text {left}} = \ alpha \ sigma +\ beta \ tau.}

Bézoutovu identitu lze použít k řešení diofantických rovnic. Například jeden ze standardních důkazů Lagrangeovy věty o čtyřech čtvercích , že každé kladné celé číslo může být reprezentováno jako součet čtyř čtverců, je tímto způsobem založen na kvartérních GCD.

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.
Cohn, H. (1962). Pokročilá teorie čísel . New York: Dover. ISBN 0-486-64023-X.
Cox, D .; Little, 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.
Crandall, R .; Pomerance, C. (2001). Prime Numbers: Výpočetní perspektiva (1. vyd.). New York: Springer-Verlag. ISBN 0-387-94777-9.
Lejeune Dirichlet, PG (1894). Dedekind, Richard (ed.). Vorlesungen über Zahlentheorie (Přednášky z teorie čísel) (v němčině). Braunschweig: Vieweg. LCCN 03005859 . OCLC 490186017 .. Viz také Vorlesungen über Zahlentheorie
Knuth, DE (1997). The Art of Computer Programming , Volume 2: Seminumerical Algorithms (3rd ed.). Addison – Wesley. ISBN 0-201-89684-2.
LeVeque, WJ (1996) [1977]. Základy teorie čísel . New York: Dover. ISBN 0-486-68906-9.
Mollin, RA (2008). Základní teorie čísel s aplikacemi (2. vyd.). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3.
Ore, O. (1948). Teorie čísel a její historie . New York: McGraw – Hill.
Rosen, KH (2000). Elementární teorie čísel a její aplikace (4. vyd.). Reading, MA: Addison – Wesley. ISBN 0-201-87073-8.
Schroeder, M. (2005). Teorie čísel ve vědě a komunikaci (4. vyd.). Springer-Verlag. ISBN 0-387-15800-6.
Stark, H. (1978). Úvod do teorie čísel . Stiskněte MIT. ISBN 0-262-69060-8.
Stillwell, J. (1997). Čísla a geometrie . New York: Springer-Verlag. ISBN 0-387-98289-2.
Stillwell, J. (2003). Prvky teorie čísel . New York: Springer-Verlag. ISBN 0-387-95587-9.
Tattersall, JJ (2005). Elementární teorie čísel v devíti kapitolách . Cambridge: Cambridge University Press . ISBN 978-0-521-85014-8.

externí odkazy

Demonstrace Euclidova algoritmu
Weisstein, Eric W. „Euklidovský algoritmus“ . MathWorld .
Euklidův algoritmus na hranici uzlu
Euclidův algoritmus na PlanetMath .
Euklidovský algoritmus na MathPages
Euclidova hra na hranici uzlu
Hudba a Euclidův algoritmus

Languages

In other projects