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).
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:
€€ 3, 3, 3 €€Nyní tato prvočísla vynásobíme a dostaneme největší společný dělitel – číslo 27.
€€ \begin{align*} \mathrm{gcd}(135,216) &= 3 \cdot 3 \cdot 3 = 27 \\ 27 &| 135 \\ 27 &| 216 \\ \end{align*} €€