Největší společný dělitel ($D$)

Výpis dělitelů

• Vypíšeme si všechny dělitele každého z daných čísel.
• Najdeme největší číslo, které se vyskytuje ve výpisu dělitelů všech daných čísel.

Příklad: Najděte $D(12, 18)$.

• Dělitelé čísla 12: 1, 2, 3, 4, 6, 12
• Dělitelé čísla 18: 1, 2, 3, 6, 9, 18

Největší číslo, které se vyskytuje v obou seznamech, je 6. Proto $D(12, 18) = 6$.

Příklad: Najděte $D(16, 24, 40)$.

• Dělitelé čísla 16: 1, 2, 4, 8, 16
• Dělitelé čísla 24: 1, 2, 3, 4, 6, 8, 12, 24
• Dělitelé čísla 40: 1, 2, 4, 5, 8, 10, 20, 40

Největší číslo, které se vyskytuje ve všech třech seznamech, je 8. Proto $D(16, 24, 40) = 8$.

Tento způsob je vhodný pro menší čísla.

Pomocí prvočíselného rozkladu:

• Rozložíme každé z daných čísel na součin prvočísel.
• $D$ je součin všech společných prvočísel, která se vyskytují v rozkladech daných čísel, přičemž každé společné prvočíslo vezmeme s nejnižší mocninou, v jaké se v kterémkoli z rozkladů vyskytuje. Pokud čísla nemají žádné společné prvočíselné dělitele, pak je jejich $D$ roven 1.

Příklad: Najděte $D(12, 18)$.

• Prvočíselný rozklad čísla 12: $12 = 2^2 \cdot 3^1$
• Prvočíselný rozklad čísla 18: $18 = 2^1 \cdot 3^2$

Společná prvočísla jsou 2 a 3.

• Nejnižší mocnina prvočísla 2: $2^1$
• Nejnižší mocnina prvočísla 3: $3^1$

$D(12, 18) = 2^1 \cdot 3^1 = 2 \cdot 3 = 6$.

Příklad: Najděte $D(8, 12, 20)$.

• Prvočíselný rozklad čísla 8: $8 = 2^3$
• Prvočíselný rozklad čísla 12: $12 = 2^2 \cdot 3^1$
• Prvočíselný rozklad čísla 20: $20 = 2^2 \cdot 5^1$

Společné prvočíslo je pouze 2.

• Nejnižší mocnina prvočísla 2: $2^2$

$D(8, 12, 20) = 2^2 = 4$.

Tento způsob je obecnější a funguje i pro větší čísla.

Euklidův algoritmus:

Euklidův algoritmus je efektivní metoda pro nalezení $D$ dvou přirozených čísel. Je založen na opakovaném dělení se zbytkem.

• Nechť $a$ a $b$ jsou dvě přirozená čísla, kde $a \ge b$.
• Vydělíme $a$ číslem $b$ a dostaneme zbytek $r$.
• Pokud je $r = 0$, pak $D(a, b) = b$.
• Pokud $r \neq 0$, pak nahradíme $a$ číslem $b$ a $b$ číslem $r$ a opakujeme dělení.
• Pokračujeme, dokud nedostaneme zbytek 0. Poslední nenulový zbytek je $D(a, b)$.

Příklad: Najděte $D(48, 30)$ pomocí Euklidova algoritmu.

$48 = 1 \cdot 30 + 18$ (zbytek je 18)

$30 = 1 \cdot 18 + 12$ (zbytek je 12)

$18 = 1 \cdot 12 + 6$ (zbytek je 6)

$12 = 2 \cdot 6 + 0$ (zbytek je 0)

Poslední nenulový zbytek je 6. Proto $D(48, 30) = 6$.

Tento způsob je velmi efektivní pro velká čísla.