Euklidův algoritmus

Pojmenován podle Euklida. Slouží ke zjištění největšího společného dělitele dvou čísel a který byl zdokumentován ve 3. století před naším letopočtem v díle Euclid's Elements (Kniha 7, věta 1 a 2).

ZNAČENÍ: Největšího společného dělitele celých kladných čísel x a y budeme značit gcd(x, y) podle anglického Greatest Common Divisor.

Pseudokód

Vstup: jsou dvě čísla x, y ∈ ℕ.

a := x, b := y

Opakujeme:
    a < b, prohodíme a s b.
    Pokud b = 0, vyskočíme z cyklu.
    a := a mod b

Algoritmus využívá Větu: gcd(a + cb, b) = gcd(a, b) pro libovolné c ∈ ℤ

### Algoritmus

Vstupem jsou dvě přirozená čísla m, n ∈ ℕ, necházíme jejich největšího společného dělitele, tedy největší přirozené číslo, kterým jsou beze zbytku dělitelná čísla m i n.

  1. [Nalezení zbytku] Vydělte m číslem n a nechť r je zbytek. (Znamená to, že 0 < r < n).
  2. [Je zbytek roven nule?] Pokud r = 0, algoritmus končí a n je odpověď.
  3. [Redukce] Přiřaďte m = n, n = r, a vraťte se na krok 1.

Složitost

(Lamého věta) Nechť a < b ∈ N. Pak Eukleidův algoritmus pro gcd(a, b) vyžaduje nejvýše tolik kroků, kolik je pětkrát počet číslic v desítkovém zápisu čísla b.

Důkaz: viz Habala.

VĚTA: Euklidův algoritmus vypočte největšího společného dělitele čísel x a y. Provede přitom nejvýše c · (log2 x + log2 y + 1) aritmetických operací, kde c je konstanta.

Důkaz

m = qn + r,
pro nějaké celé číslo q. Pokud r = 0, je m násobkem čísla n a v takovém případě je samozřejmě zároveň největším společným dělitelem čísel man. Jestliže r ^ 0, pak jakékoli číslo, které je dělitelem m a n , musí beze zbytku dělit také m — qn = — r a jakékoli číslo, které je dělitelem n a r, musí beze zbytku dělit qn + r = m; množina společných dělitelů čísel {m, n} je tudíž stejná jako množina společných dělitelů čísel {n,r}. Zejména pak největší společný dělitel čísel {ra, n) je stejný jako největší společný dělitel čísel {n, r}.)

Poznamka: Euklides původně vytvořil nejen algoritmus výpočtu největšího společného dělitele dvou čísel, ale také velmi podobný geometrický postup pro konstrukci „největší společné míry" délek dvou úseček;

Důkaz

LEMMA zastavení: Algoritmus se vždy zastaví.

Důkaz: Sledujme, jak se vyvíjí součet a + b. Na počátku výpočtu je roven x + y, každým průchodem cyklem se sníží alespoň o 1. Přitom zůstává stále nezáporný, takže průchodů nastane nejvýše x + y.

Lemma S: Pokud se algoritmus zastaví, vydá správný výsledek.

Rozšířený eklidův algoritmus

Pro každé x a y existují celá čísla α a β taková, že gcd(x, y) = αx + βy. Těmto číslům se říká Bézoutovy koeficienty. Upravte Euklidův algoritmus, aby je vypočetl.

Související