Bc. Vojtěch Hordějčuk / Wiki / Matematika / Největší společný dělitel

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

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.

$\begin{align*} a | B &\leftrightarrow B = n \cdot a \\ a,B,n &\in N \end{align*}$

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.

Největší společný dělitel se značí jako NSD (Nejvyšší Společný Dělitel) či anglicky jako GCD (Greatest Common Divisor).

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 je z tohoto rozkladu vytvoříme následujícím způsobem:

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:

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

$\begin{align*} gcd(135,216) &= 3 \cdot 3 \cdot 3 = 27 \\ 27 &| 135 \\ 27 &| 216 \\ \end{align*}$