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

umime.to/F2L

Největší společný dělitel (NSD) dvou celých čísel je největší číslo, které beze zbytku dělí obě čísla. Příklady: NSD(18, 24) = 6, NSD(12, 21) = 3, NSD(24, 35) = 1. Pojem největšího společného dělitele lze zobecnit i na větší počet vstupních čísel. Například NSD(30, 85, 90) = 5. Typickým využitím největšího společného dělitele je krácení zlomků.

Pokud největší společný dělitel dvou čísel je 1, nazýváme je nesoudělná. Například čísla 15 a 32 jsou nesoudělná.
Pokud je největší společný dělitel větší než 1, jde o čísla soudělná. Například čísla 20 a 24 mají největší společný dělitel 4, tedy jsou soudělná.

Pro malá čísla můžeme největšího společného dělitele určit tak, že si prostě vypíšeme všechny dělitele.

Příklad: NSD(18, 24) řešený výčtem dělitelů

Dělitelé čísla 18 jsou 1, 2, 3, 6, 9, 18.
Dělitelé čísla 24 jsou 1, 2, 3, 4, 6, 8, 12, 24.
Společní dělitelé čísel 18 a 24 jsou 1, 2, 3, 6.
Největší společný dělitel je 6.

Pro větší čísla můžeme největšího společného dělitele určit pomocí prvočíselného rozkladu. Obě čísla rozepíšeme jako součin prvočísel, výsledný NSD je součin prvočísel vyskytujících se v obou rozkladech umocněných na příslušné nejmenší exponenty.

Příklad NSD(18, 24) řešený pomocí rozkladu

18 = 2\cdot 3 \cdot 3 = 2\cdot3^2
24 = 2 \cdot 2 \cdot 2\cdot 3 = 2^3\cdot 3
Společná část prvočíselného rozkladu: 2, 3.
\mathit{NSD}(18, 24) = 2\cdot 3 = 6

Příklad NSD(540, 315) řešený pomocí rozkladu

540 = 2\cdot 2\cdot3\cdot 3\cdot 3\cdot 5 = 2^2\cdot3^3\cdot 5
315 = 3\cdot 3 \cdot 5\cdot 7 = 3^2 \cdot 5\cdot 7
Společná část prvočíselného rozkladu: 3, 3, 5
\mathit{NSD}(540, 315) = 3\cdot 3\cdot 5 = 3^2\cdot 5 = 45

Pro praktické výpočty se používají jiné algoritmy, především Euklidův algoritmus.

Rozhodovačka

Rychlé procvičování výběrem ze dvou možností.

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

Rozhodovačka • střední

Pexeso

Hledání dvojic, které k sobě patří.

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

Pexeso • střední

Krok po kroku

Doplňování jednotlivých kroků v rozsáhlejším postupu.

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

NSD bez použití mocnin

NSD s použitím mocnin

Krok po kroku • střední

Psaná odpověď

Cvičení, ve kterém píšete odpověď na klávesnici.

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

Psaná odpověď • střední

Předcházející

Navazující

Cvičení

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

umime.to/F2L

Rozhodovačka