Sysop: + NEW, Greatest common divisor

2025-04-22T10:06:37Z

+ NEW, Greatest common divisor

Nová stránka

'''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 = 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. 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ší [[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]]

Největší společný dělitel - Historie editací

Sysop: + NEW, Greatest common divisor