Největší společný dělitel
Největší společný dělitel dvou celých čísel je takové číslo, které beze zbytku dělí obě čísla a přitom neexistuje žádné jiné větší číslo, které by také dělilo obě čísla beze zbytku.
Pro příklad si vezměme čísla 24 a 32. Jaký je jejich největší společný dělitel? Hledáme v prvé řadě číslo, které dělí obě čísla.
- Např. číslo 12 sice dělí číslo 24, ale nedělí číslo 32, protože 32 / 12 je rovno 2,666… což není celé číslo. Takže číslo 12 nemůže být největší společný dělitel čísel 24 a 32.
- Co třeba číslo 4? To dělí obě čísla, 24 / 4 je rovno 6 a 32 / 4 je rovno 8. Číslo 4 je tedy náš první kandidát. Neexistuje nějaké větší číslo, které by dělilo obě čísla?
- Číslo 8 dělí jak číslo 24, tak číslo 32 a zároveň je větší než číslo 4.
- Žádné jiné větší číslo než 8, které by dělilo obě čísla, neexistuje. Číslo 8 je tedy největší společný dělitel čísel 24 a 32.
Euklidův algoritmus nalezení největšího společného dělitele
Existuje poměrně jednoduchý způsob, jak najít největšího společného dělitele dvou čísel Euklidovým algoritmem. Mějme na začátku dvě čísla x a y, pro která chceme největšího společného dělitele najít. Pro příklad si to zkusíme na číslech x = 50 a y = 35 Potom budeme postupovat takto:
- Vydělíme x / y a zapamatujeme si zbytek po dělení. Tento zbytek si poznačíme jako z. Pro náš příklad dostaneme 50 / 35, což nám dá zbytek z = 15.
- Nyní prohodíme proměnné a do proměnné x uložíme hodnotu y a do y uložíme hodnotu z. Původní hodnotu x zahodíme. Po tomto kroku dostaneme x = 35 a y = 15.
- Nyní se podíváme, jestli je y rovno nule. Pokud ano, je největším společným dělitelem číslo x. Protože y není rovno nule, pokračujeme dále a opakujeme celý postup znova od prvního bodu.
- Znovu vydělíme x / y, tedy dělíme 35 / 15, což nám dá zbytek po dělení z = 5.
- Provedeme prohození proměnných, dostaneme tedy x = 15 a y = 5. Protože y není rovno nule, pokračujeme dále.
- Vydělíme x / y, tedy dělíme 15 / 5. Zbytek po dělení je z = 0.
- Prohodíme proměnné a dostaneme x = 5 a y = 0.
- V tuto chvíli je y = 0 a náš algoritmus končí. Největším společným dělitelem je číslo x = 5.
Důležité je, že na pořadí čísel nezáleží. Pokud bychom čísla z příkladu prohodili, získali bychom dvojici x = 35 a y = 50. Postup by byl stejný:
- Vydělíme x / y, tedy dělíme 35 / 50, což nám dá zbytek z = 35.
- Prohodíme proměnné x = 50 a y = 35.
- Vidíme, že po tomto kroku jsme akorát prohodili obsah proměnných x a y mezi sebou…
Kalkulačka
Tato kalkulačka vám spočítá největšího společného dělitele.