Články » SŠ Matematika » Aritmetika

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

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

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

Vypočítejte


Hlavolam

Jak to tak bývá, zlý čaroděj uvěznil mudrce. A kdo by to čekal, dal mu šanci se zachránit, pokud splní úkol. Na stole je kulatý tác, kterým lze volně otáčet, a na něm čtyři mince do čtverce. Mudrc má zavázané oči, nic nevidí. Jeho úkolem je otočit mince tak, že bude na všech panna. Nemá to však jednoduché. Otočí jistý počet mincí, pak černokněžník tácem zatočí. Opět otočí nějaké mince a znovu se tácem náhodně otočí. Toto se opakuje, dokud nejsou všechny mince správně. V tu chvíli je hra zlotřilým čarodějem ukončena. Mudrc nepozná podle hmatu pannu od orla. Musí vždy mince nechat na svém místě, ve čtverci. A hlavně - kvůli zlé magii - má strašnou smůlu a pokud bude spoléhat jen na náhodu, tak úkol nikdy nesplní.