Největší společný dělitel

Největší společný dělitel (značený NSD, D, příp. gcd z anglického greatest common divisor) dvou celých čísel je největší číslo takové, že beze zbytku dělí obě čísla, tzn. největší číslo, jímž jsou obě čísla dělitelná. Například největší společný dělitel čísel 15 a 20 je 5 (číslo 5 dělí obě čísla, žádné větší číslo s touto vlastností už neexistuje; např. číslo 10 dělí druhé číslo, ale ne první).

Obecněji je možno hovořit o největším společném děliteli celé množiny čísel - tím je největší číslo takové, že beze zbytku dělí všechna čísla v množině.

Definice

:\operatorname{NSD}(a, b) = \max \{ n \in \mathbb{N} : n \mid a \wedge n \mid b \}

Vlastnosti

Určení největšího společného dělitele je matematická operace ** idempotentní, *: \operatorname{NSD}(a, a) = a ** asociativní i *: \operatorname{NSD}(\operatorname{NSD}(a, b), c) = \operatorname{NSD}(a, (\operatorname{NSD}(b, c)) ** komutativní *: \operatorname{NSD}(a, b) = \operatorname{NSD}(b, a) * Součin největšího společného dělitele a nejmenšího společného násobku dvou čísel se rovná součinu těchto dvou čísel: *: \operatorname{NSD}(a, b) \operatorname{nsn}(a, b) = ab * \operatorname{NSD}(a, b) = \operatorname{NSD}(a, b-a) (pro b > a). Této vlastnosti využívá Eukleidův algoritmus: *: Označme D_1 množinu společných dělitelů čísel a, b a D_2 množinu společných dělitelů čísel a, b-a. +more Uvědomíme si, že *:: d \mid a \land d \mid (b-a) \Rightarrow d\mid a \land d \mid b \Rightarrow \operatorname{NSD}(a, b-a) \in D_1 *:: d \mid a \land d \mid b \Rightarrow d \mid a \land d \mid (b-a) \Rightarrow \operatorname{NSD}(a, b) \in D_2 *: Pokud by \operatorname{NSD}(a, b) > \operatorname{NSD}(a, b-a), dostali bychom spor, protože v množině D_2 by byl větší prvek než \operatorname{NSD}(a, b-a). Podobný spor bychom dostali, pokud by \operatorname{NSD}(a, b) . Proto \operatorname{NSD}(a, b) = \operatorname{NSD}(a, b-a).

Výpočet

Největšího společného dělitele dvou čísel (a díky asociativitě i libovolně mnoha) lze určit prostřednictvím prvočíselného rozkladu obou čísel, jako součin prvočísel umocněných na nejmenší z exponentů u příslušného prvočísla v rozkladech:

Nechť \prod_i p_i^{e_i} je prvočíselný rozklad čísla a a \prod_i p_i^{f_i} prvočíselný rozklad čísla b. Pak :\operatorname{NSD}(a, b) = \prod_i p_i^{\min {(e_i, f_i)}}.

Například největšího společného dělitele čísel 136 a 204 lze nalézt tak, že zjistíme, že 136 = 2³×17 a 204 =2²×3×17. V rozkladech se vyskytují prvočísla 2, 3 a 17 s exponenty 3, 0, 1 u menšího čísla a 2, 1, 1 u většího čísla. +more Výsledné NSD pak je součin prvočísel vyskytujících se v obou rozkladech umocněných na příslušné nejmenší exponenty, tedy 2²×17 = 68.

Tento výpočet je snadno pochopitelný, ale v praxi zcela nepoužitelný s výjimkou velice malých čísel, neboť získání rozkladu na prvočísla je extrémně náročná operace.

Pro praktické výpočty slouží výrazně rychlejší algoritmy, hlavně tzv. Eukleidův algoritmus.

Související články

Nejmenší společný násobek * Nesoudělná čísla

Externí odkazy

Kategorie:Teorie čísel Kategorie:Multiplikativní funkce