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

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

'''Největší společný dělitel''' (značený '''NSD''', '''D''', příp. '''gcd''' z [[angličtina|anglického]] ''greatest common divisor'') dvou [[celé číslo|celých čísel]] je největší číslo takové, že beze [[zbytek po dělení|zbytku]] [[dělení|dělí]] obě čísla, tzn. největší číslo, jímž jsou obě čísla [[dělitelnost|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žina|množiny]] čísel – tím je největší číslo takové, že beze zbytku dělí všechna čísla v množině. == Definice == :<big>\(\operatorname{NSD}(a, b) = \max \{ n \in \mathbb{N} : n \mid a \wedge n \mid b \}\)</big> == Vlastnosti == {{RIGHTTOC}} * Určení největšího společného dělitele je [[operace (matematika)|matematická operace]] ** [[idempotence|idempotentní]], *: <big>\(\operatorname{NSD}(a, a) = a\)</big> ** [[asociativita|asociativní]] i *: <big>\(\operatorname{NSD}(\operatorname{NSD}(a, b), c) = \operatorname{NSD}(a, (\operatorname{NSD}(b, c))\)</big> ** [[komutativita|komutativní]] *: <big>\(\operatorname{NSD}(a, b) = \operatorname{NSD}(b, a)\)</big> * [[Násobení|Součin]] největšího společného dělitele a [[nejmenší společný násobek|nejmenšího společného násobku]] dvou čísel se rovná součinu těchto dvou čísel: *: <big>\(\operatorname{NSD}(a, b) \operatorname{nsn}(a, b) = ab\)</big> * <big>\(\operatorname{NSD}(a, b) = \operatorname{NSD}(a, b-a)\)</big> (pro <big>\(b > a\)</big>). Této vlastnosti využívá [[Eukleidův algoritmus]]: *: Označme <big>\(D_1\)</big> množinu společných dělitelů čísel <big>\(a, b\)</big> a <big>\(D_2\)</big> množinu společných dělitelů čísel <big>\(a, b-a\)</big>. Uvědomíme si, že *:: <big>\(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\)</big> *:: <big>\(d \mid a \land d \mid b \Rightarrow d \mid a \land d \mid (b-a) \Rightarrow \operatorname{NSD}(a, b) \in D_2\)</big> *: Pokud by <big>\(\operatorname{NSD}(a, b) > \operatorname{NSD}(a, b-a)\)</big>, dostali bychom spor, protože v množině <big>\(D_2\)</big> by byl větší prvek než <big>\(\operatorname{NSD}(a, b-a)\)</big>. Podobný spor bychom dostali, pokud by <big>\(\operatorname{NSD}(a, b) < \operatorname{NSD}(a, b-a)\)</big>. Proto <big>\(\operatorname{NSD}(a, b) = \operatorname{NSD}(a, b-a)\)</big>. == 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číslo|prvočíselného]] [[prvočíselný rozklad|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ť <big>\(\prod_i p_i^{e_i}\)</big> je prvočíselný rozklad čísla <big>\(a\)</big> a <big>\(\prod_i p_i^{f_i}\)</big> prvočíselný rozklad čísla <big>\(b\)</big>. Potom: :<big>\(\operatorname{NSD}(a, b) = \prod_i p_i^{\min {(e_i, f_i)}}\)</big>. Například největšího společného dělitele čísel 136 a 204 lze nalézt tak, že zjistíme, že 136&nbsp;=&nbsp;2³×17 a 204&nbsp;=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. 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&nbsp;=&nbsp;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ší [[algoritmus|algoritmy]], hlavně tzv. [[Eukleidův algoritmus]]. == Související články == * [[Nejmenší společný násobek]] * [[Nesoudělná čísla]] == Externí odkazy == * [https://www.cuemath.com/numbers/greatest-common-divisor-gcd/ Cuemath.com – Greatest common divisor (anglicky)] * [https://artofproblemsolving.com/wiki/index.php/Greatest_common_divisor AoPS – Greatest common divisor (anglicky)] {{Commonscat|Greatest common divisor}}{{Článek z Wikipedie}} [[Kategorie:Teorie čísel]]

Návrat na stránku „Největší společný dělitel“.