Přejít na matematické fórum Připravili jsme pro Vás zbrusu nové fórum a jsme připravení odpovídat na Vaše otázky!


Články » SŠ Matematika » Aritmetika

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

Vydáno dne v kategorii Aritmetika; Autor: ; Počet přečtení: 105 653

Největší společný dělitel dvou čísel je číslo takové, které je obě vydělí beze zbytku


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) = 864

NSD(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ě čísla u, v z množiny přirozených čísel.
Dokud v není nulové, opakuj:
  Do r ulož zbytek po dělení čísla u číslem v
  Do u ulož v
  Do v ulož r
Konec algoritmu; v u je 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

Tento clanek pro vas napsal Jakub Vojacek!

Test

Která z následujících funkcí nemá definiční obor ?


Hlavolam

Každý den přilétá ve 12:00 na letiště v Ruzyni letadlo se spěšnou zásilkou. Pro zásilku vyráží z Liberce auto a to tak, aby tam bylo přesně v poledne. Tam si jí vyzvedne a jede s ní zpět do Liberce (po tý rozkopaný dálnici už asi tak spěšná nebude ;-) Jednoho dne ale přistálo letadlo dříve a tak z letiště vypravili se zásilkou poslíčka na kole. Jel autu naproti a to 4x pomaleji než samotné auto. Když se za 20 minut setkali, předal zásilku a odjel kdovíkam. Nás ale zajímá, o kolik minut dřív přijelo tentokrát auto do Liberce.