Adobe Systems 1 Aritmetika 2 – jaro 2021 4. prezentace Mgr. Helena Durnová, Ph.D. RNDr. Petra Bušková Adobe Systems 2 Největší společný dělitel Jak už název napovídá, největší společný dělitel dvou přirozených čísel je ten největší ze všech společných dělitelů. Např. čísla 50 a 60 mají následující společné dělitele: 1, 2, 5, 10 Největší z těchto společných dělitelů je číslo 10. Formálně řečeno: Definice 3. Společný dělitel přirozených čísel a, b je každé přirozené číslo d, pro které platí d│a a d│b. Definice 4. Největší společný dělitel přirozených čísel a, b je ten ze společných dělitelů, který je dělitelný všemi společnými děliteli. Označujeme D(a,b). Adobe Systems 3 Hledání největšího společného dělitele Největšího společného dělitele dvou přirozených čísel lze najít třemi způsoby: (a) využitím definice; (b) pomocí tzv. Eukleidova algoritmu; (c) pomocí rozkladu na součin prvočinitelů. Hledání s využitím definice lze použít u malých čísel, u větších je spíše neobratné. Hledání pomocí rozkladu na prvočísla se učí na ZŠ. Eukleidův algoritmu nabízí silný nástroj pro hledání největšího společného dělitele. Adobe Systems 4 Příklad Příklad: Určete množinu všech společných dělitelů čísel 24 a 30 a největší společný dělitel čísel 24 a 30. Řešení: Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24. Číslo 30 je dělitelné čísly 1, 2, 3, 5, 6, 10, 15, 30. Množina všech společných dělitelů čísel 24 a 30 je průnik těchto dvou množin, tj. množina {1, 2, 3, 6} Největší společný dělitel D(24,30) = 6. Toto číslo je dělitelné všemi menšími společnými děliteli, tj. platí: 1 | 6 , 2 | 6 , 3 | 6 , 6 | 6 Adobe Systems 5 Věta (Eukleidův algoritmus) Věta 5. Jestliže přirozené číslo a dává při dělení nenulovým přirozeným číslem b nenulový zbytek z, tzn. a = b . q + z (přičemž z < b), pak platí, že množina všech společných dělitelů čísel a, b je množinou všech společných dělitelů čísel b, z. Dále platí: Největší společný dělitel čísel a, b je roven největšímu společnému děliteli čísel b, z, tj. D(a,b) = D(b,z). Tím převádíme úkol určit D(a,b) na určení D(b,z). To je výhodné, neboť čísla b a z jsou menší než čísla a, b. Důkaz je uveden v ZEA, s. 189. Na větě 5. je založen postup výpočtu největšího společného dělitele dvou přirozených čísel nazývaný Eukleidův algoritmus. Adobe Systems 6 Eukleidův algoritmus (řešený příklad) Příklad: Zjistěte D (268, 80), tj. největšího společného dělitele čísel 268 a 80, pomocí Eukleidova algoritmu. Řešení: 268 : 80 = 3 neboli 268 = 80 . 3 + 28 (zbytek 28) D (80, 28): 80 : 28 = 2 80 = 28 . 2 + 24 (zbytek 24) D (28, 24): 28 : 24 = 1 28 = 24. 1 + 4 (zbytek 4) D (24, 4): 24 : 4 = 6 24 = 6 . 4 (zbytek 0) Největší společný dělitel čísel 268 a 80 je číslo 4, tj. poslední nenulový zbytek při postupném dělení. Adobe Systems 7 Rozšíření definice (největšího) společného dělitele na tři a více čísel Definice 3 (společný dělitel dvou čísel) a Definici 4 (největší společný dělitel dvou čísel D (a, b)) lze rozšířit na libovolný konečný počet přirozených čísel. Příklad: Hledáme společné dělitele čísel 12, 27 a 36. Společnými děliteli čísel 12 a 27 jsou čísla 1 a 3; D (12, 27) = 3. Společnými děliteli čísel 27 a 36 jsou číslo 1, 3 a 9; D (27, 36) = 9. Společnými děliteli čísel 12 a 36 jsou číslo 1, 2, 3, 4, 6 a 12; D (12, 36) = 12. Tedy D (12, 27, 36) = 3. Adobe Systems 8 Čísla soudělná a nesoudělná Libovolná dvě čísla mají vždy alespoň jednoho společného dělitele. Tím je číslo 1. Pokud jiného společného dělitele nemají, nazývají se nesoudělná; v opačném případě se nazývají soudělná. Formálně: Definice 5. Přirozená čísla a, b se nazývají nesoudělná, právě když je jejich největší společný dělitel roven 1. Stručně píšeme: D(a,b) = 1 Definice 6. Přirozená čísla a, b se nazývají soudělná, právě když je jejich největší společný dělitel větší než 1. Stručně: D(a,b) > 1. Adobe Systems 9 Příklady: čísla soudělná a nesoudělná Podobně jako Definice 3 a 4 lze Definice 5 a 6 rozšířit na libovolný konečný počet přirozených čísel. Příklady: Čísla 4, 7, 6, 9 jsou nesoudělná, protože D(4,7,6,9) = 1 Čísla 8, 12, 32 jsou soudělná, protože D(8, 12, 32) = 4 ̶ Adobe Systems 10 Příklady Příklad 1 Určete všechny přirozené společné dělitele čísel: a) 60, 36 b) 48, 72, 0 c) 24, -132, 54 Příklad 2 K číslu a = 51 najděte číslo b tak, aby D(a,b) = 17. Příklad 3 Najděte dvě přirozená čísla, jejichž součet je 432 a největší společný dělitel je 36. Adobe Systems 11 Příklady Příklad 4 Největší společný dělitel dvou přirozených čísel je 24. Jedno z nich je dvojnásobkem druhého. Která jsou to čísla? Příklad 5 Určete pomocí rozkladu na prvočinitele i pomocí Eukleidova algoritmu: a) D(455, 273) b) D(360, 504) c) D(90, 108, 84) d) D(568, 426, 355)