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

Vydáno dne v kategorii Aritmetika; Autor: Jakub Vojáček; Počet přečtení: 119 501

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:

\frac{56}{14}
NSD(56, 14) = 14
\frac{56}{14}=\frac{4*14}{1*14}=\frac{4}{1} = 4

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:

NSD(a, b)=\frac{a*b}{NSN(a, b)}

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) = \frac{32*54}{NSN(32,54)} = \frac{1728}{864} = 2
NSD(32, 54, 16) = NSD(2, 16)
NSN(2,16) = 16
NSD(2, 16) = \frac{2*16}{NSN(2, 16)} = \frac{32}{16} = 2

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

Test

Určete asymptotu bez směrnice funkce f(x)=\frac{x^2+1}{x+3}


Hlavolam

Na křížovce je devět polí, kde čísla v řadě a sloupci mají součet 15. Jaká čísla se nacházejí na každém poli, pokud všechna čísla jsou jedinečná?