Vlastně už z úvodu článku byste mohli celkem bez problémů pochopit co se rozumí pod pojmem největší společný dělitel (dále již jen NSD). Ale ještě to pro jistotu trochu rozvedu. Pokud máme množinu čísel X a vypočítáme jejich NSD, určili jsme číslo, které je schopno vydělit každé číslo z množiny X beze zbytku.
Definice jsem nikdy neměl rád, vždy jsem všechno pochopil spíše z příkladů a proto jsem jich pro vás několik připravil. Určete NSD čísel 10, 8.
My máme určit číslo, které dokáže čísla 10, 8 vydělit. Tak určitě to není 7, 6, 5, 4 ani 3. Doufám, že je již každému jasné, že se jedná o číslo 2:
10:2=5 8:2=4
V předchozím příkladě jsme dokázali určit NSD z hlavy protože se jednalo o malá čísla. Ale pokud se bude jednat o velká čísla, měli bychom použít nějaký jiný způsob. V tomto článku vás seznámím s jedním způsobem jak určit NSD.
NSD pomocí prvočísel
V článku Nejmenší společný násobek jsme určovali nejmenší společný násobek pomocí prvočíselného rozkladu (přejít na článek Prvočíselný rozklad). Podobně tomu bude i při určování NSD. Ukážeme si to na příkladu. Určete NSD čísel 32, 54, 16.
Nejprve si opět napíšeme prvočíselný rozklad jednotlivých čísel v řadě pod sebou:
32=25 54=21*33 16=24
Nyní vybereme taková čísla, která se vyskytují ve všech řádcích a vybereme to číslo, které má nejmenší mocninu. NSD je součin těchto čísel:
NSD(32, 54, 16) = ? 32=25 54=21*33 16=24 NSD(32, 54, 16) = 21
K tomuto již není co dodat, snad jenom ještě pár příkladů:
NSD(84, 112, 168) = ? 84=22*31*71 112=24*71 168=23*31*71 NSD(84, 112, 168) = 22*71 = 28 NSD(158, 131, 257) = ? 158=21*711 131=1311 256=28 NSD(158, 131, 257) = 1
V posledním příkladě nastala prekérní situace. Žádné číslo nebylo na všech řádcích. V takovém případě je NSD rovno jedné.
Příklad použití
Možná si to ani neuvědomujete, ale při práci se zlomky je NSD velkým společníkem. Pomocí něj můžeme krátit zlomky:
NSD(56, 14) = 14
NSD pomocí NSN
Velmi lehká metoda jak vypočítat NSD je pomocí nejmenšího společného násobku (přejít na článek Nejmenší společný násobek). Vlastně se jedná pouze o dosazení do vzorečku:
Je trochu problém, že tento vzoreček platí pouze pro dvě čísla. Máme-li tedy touto metodou spočítat NSD tří čísel 32, 54, 16, budeme postupovat následovně:
NSD(32, 54, 16) = ? NSN(32, 54) = 864NSD(32, 54, 16) = NSD(2, 16) NSN(2,16) = 16
NSD čísel 32, 54, 16 je 2.
NSD pomocí Euklidova algoritmu
Tento algoritmus byl vymyšlen někdy 300 let před naším letopočtem. Je hodně jednoduchý ale velmi účinný. Pomocí rozkladu prvočísel se dá určit NSD menších čísel, ale u větších čísel bychom narazili na velký výpočetní čas. Pomocí Euklidova algoritmu dosáhneme rychlejšího výsledku. Euklidův algoritmus se dá popsat pomocí jednoduchého schématu.
Mějme dvě číslau,vz množiny přirozených čísel. Dokudvnení nulové, opakuj: Dorulož zbytek po dělení číslaučíslemvDouuložvDovuložrKonec algoritmu; vuje uložen největší společný dělitel původních čísel.
Ukážeme si jedno vzorové řešení, ve kterém budou vypsány všechny kroky. Určete NSD čísel 12, 16.
u=12
v=16
I) r=12, u=16, v=r=12
II) r=4, u=12, v=r=4
III) r=0, u=4, v=r=0
Konec algoritmu; NSD(12, 16) = u = 4
: