cvičení 1

Najděte největší společný dělitel dvou čísel

Rozklad:
1856 = 2 . 2 . 2 . 2 . 2 . 2 . 29
984 = 2 . 2 . 2 . 3 . 41
2 . 2 . 2 = 8 - největší společný dělitel

Euklidův algoritmus

• mám zadaná dvě přirozená čísla
• první číslo dělím druhým číslem (dělení se zbytkem)
• druhé číslo (dělitele) dělím zbytkem po dělení 
• opakuji předchozí krok, dokud není zbytek roven nule
• poslední dělitel je hledaný NSD