Dělitel přirozeného čísla A je takové přirozené číslo b, které dělí číslo A beze zbytku. To znamená, že číslo A je celočíselný násobek čísla b. Největší společný dělitel dvou přirozených čísel a a b je největší přirozené číslo c, které dělí číslo a a zároveň dělí i číslo b, tedy platí, že € a | B \leftrightarrow B = n \cdot a €, kde € a,B,n \in N €. Největší společný dělitel se značí jako NSD (nejvyšší společný dělitel) či anglicky jako GCD (greatest common divisor).

Výpočet

Faktorizace na prvočísla

Každé přirozené číslo můžeme rozepsat jakou součin prvočísel.

£ \begin{align*} 5 &= 5 \\ 6 &= 2 \cdot 3 \\ 12 &= 2 \cdot 2 \cdot 3 \\ 55 &= 5 \cdot 11 \\ \end{align*} £

Největší společný dělitel z tohoto rozkladu vytvoříme následujícím způsobem:

  • každé prvočíslo, které se nachází v obou rozkladech, si zapíšeme
  • všechna zapsaná čísla vynásobíme
Příklad

Hledáme největší společný dělitel čísel 135 a 216. Nejprve je tedy rozepíšeme na prvočísla.

£ \begin{align*} 135 &= 3 \cdot 3 \cdot 3 \cdot 5 \\ 216 &= 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \\ \end{align*} £

Nyní najdeme společná prvočísla, které se vyskytují v obou rozkladech. Jsou to tato:

£ 3, 3, 3 £

Nyní tato prvočísla vynásobíme a dostaneme největší společný dělitel:

£ \mathrm{gcd}(135,216) = 3 \cdot 3 \cdot 3 = 27 £

Reference