✖

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:

  1. 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.
  2. 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.
  3. 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.
  4. Znovu vydělíme x / y, tedy dělíme 35 / 15, což nám dá zbytek po dělení z = 5.
  5. Provedeme prohození proměnných, dostaneme tedy x = 15 a y = 5. Protože y není rovno nule, pokračujeme dále.
  6. Vydělíme x / y, tedy dělíme 15 / 5. Zbytek po dělení je z = 0.
  7. Prohodíme proměnné a dostaneme x = 5 a y = 0.
  8. 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ý:

  1. Vydělíme x / y, tedy dělíme 35 / 50, což nám dá zbytek z = 35.
  2. Prohodíme proměnné x = 50 a y = 35.
  3. 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.

Hledáme programátory!