Adobe Systems 1 IMAp01, IMAk01 – podzim 2021 Dělitelnost v oboru přirozených čísel Mgr. Helena Durnová, Ph.D. RNDr. Petra Bušková Adobe Systems 2 Relace dělitelnosti Adobe Systems 3 Relace dělitelnosti Adobe Systems 4 Relace dělitelnosti Adobe Systems 5 Relace dělitelnosti Adobe Systems 6 Relace dělitelnosti Adobe Systems 7 Adobe Systems 8 Relace dělitelnosti Definice 2 Celé číslo dělitelné dvěma se nazývá sudé číslo. Celé číslo, které není dělitelné dvěma (dává při dělení dvěma zbytek 1), se nazývá liché číslo. Adobe Systems 9 Relace dělitelnosti - příklady Příklad 2 Dokažte, že a)součet libovolného sudého čísla a libovolného lichého čísla je liché číslo; b)součin libovolných dvou lichých čísel je liché číslo; c)součin libovolného sudého čísla s libovolným lichým číslem je sudé číslo. Příklad 3 Určete vlastnosti relace „dělitelnost celých čísel“ a tvrzení zdůvodněte. Příklad 4 Jsou dána čísla a, b, pro která platí, že a je dělitelné osmi a b je dělitelné šesti. Dokažte, že jejich součin je dělitelný číslem 24. Adobe Systems 10 Relace dělitelnosti - příklady Adobe Systems 11 Výsledky příkladů 2-5 Adobe Systems 12 Znaky dělitelnost ̶Uvedeme zde věty, na základě nichž rozhodujeme o dělitelnosti čísla jiným číslem aniž bychom dělení provedli. ̶ ̶Pro zjednodušení zápisu ve všech větách uvažujme přirozená čísla zapsaná v desítkové soustavě. Na základě předchozí prezentace lze věty o dělitelnosti rozšířit i na celá čísla. Adobe Systems 13 ̶Přirozené číslo a je dělitelné dvěma (pěti, deseti) právě tehdy, když je dvěma (pěti, deseti) dělitelné číslo zapsané jeho cifrou nultého řádu. ̶Přirozené číslo a je dělitelné čtyřmi právě tehdy, když je čtyřmi dělitelné číslo zapsané jeho posledním dvojčíslím. ̶Přirozené číslo a je dělitelné osmi právě tehdy, když je osmi dělitelné číslo zapsané jeho posledním trojčíslím. ̶Přirozené číslo a je dělitelné třemi (devíti) právě tehdy, když je třemi (devíti) dělitelný jeho ciferný součet (tj. součet všech čísel zapsaných jednotlivými ciframi v zápisu čísla a). ̶Přirozené číslo a je dělitelné jedenácti právě tehdy, když je jedenácti dělitelný součet čísel zapsaných jednotlivými ciframi sudého řádu zmenšený o součet čísel zapsaných jednotlivými ciframi lichého řádu v zápisu čísla a. ̶ ̶ Adobe Systems 14 Znaky dělitelnosti Adobe Systems 15 ̶Všechny znaky dělitelnosti ze 3. slidu plynou z obecnějších vět: ̶ ̶Dělíme-li přirozené číslo a dvěma (pěti, deseti), dostaneme stejný zbytek, jako když dělíme dvěma (pěti, deseti) číslo zapsané cifrou nultého řádu v zápisu čísla a. ̶Dělíme-li přirozené číslo a čtyřmi, dostaneme stejný zbytek, jako když dělíme čtyřmi číslo zapsané jeho posledním dvojčíslím (u jednociferných čísel doplníme před cifru nulu). ̶Dělíme-li přirozené číslo a osmi, dostaneme stejný zbytek, jako když dělíme osmi číslo zapsané jeho posledním trojčíslím (u méně než trojciferných čísel doplníme před cifry nuly). ̶Dělíme-li přirozené číslo a třemi (devíti), dostaneme stejný zbytek, jako když dělíme třemi (devíti) jeho ciferný součet. ̶Dělíme-li přirozené číslo a jedenácti, dostaneme stejný zbytek, jako když dělíme jedenácti součet čísel zapsaných jednotlivými ciframi sudého řádu zmenšený o součet čísel zapsaných jednotlivými ciframi lichého řádu v zápisu čísla a. ̶ Adobe Systems 16 Adobe Systems 17 Příklady Příklad 6 Rozhodněte, zda je číslo 4 356 dělitelné čísly 2; 3; 4; 5; 8; 9 a 11. Pokud není některým z čísel dělitelné, určete zbytek po dělení. Příklad 7 V číslech 437*; 32* a 4*54 nahraďte symbol * takovou cifrou, aby vzniklé číslo bylo dělitelné a)čtyřmi; b)osmi; c)devíti; d)jedenácti. Uveďte vždy všechna řešení. Adobe Systems 18 Příklady Příklad 8 O pěticiferném čísle 448** víme, že je dělitelné čísly 3 a 25. Doplňte cifry na místa hvězdiček. Příklad 9 Z čísla 74 851 562 vyškrtněte čtyři cifry tak, aby vzniklé číslo bylo dělitelné pěti a třemi. Najděte všechny možnosti. Příklad 10 Doplňte rodné číslo 950324/**** tak, aby bylo platné. Stačí uvést jednu možnost. Příklad 11 Dokažte s využitím rozvinutého zápisu čísla kritérium dělitelnosti a)čtyřmi b)devíti c)jedenácti Adobe Systems 19 Výsledky příkladů Příklad 6: není dělitelné pěti (zb. 1) a osmi (zb. 4) Příklad 7: Příklad 8: 50 Příklad 9: pro dělitelnost pěti musíme škrtnout poslední dvě cifry, zbylé cifry škrtáme tak, abychom získali ciferný součet dělitelný třemi: 7485, 7515, 4815, 4515, 7815, 7455 Příklad 10: například 1000 a) b) c) d) 437* 2, 6 6 4 8 32* 0, 4, 8 0, 8 4 - 4*54 - - 5 5 Adobe Systems 20 Prvočísla a čísla složená ̶Rozdělíme přirozená čísla na dvě velké podmnožiny a jednu jednoprvkovou: ̶číslo 1 bude patřit do zvláštní podmnožiny ̶prvočísla (čísla, která mají právě dva různé dělitele) tvoří jednu velkou podmnožinu ̶čísla složená (čísla s alespoň třemi různými děliteli) tvoří druhou velkou podmnožinu ̶ ̶Podmnožina prvočísel a podmnožina čísel složených mají prázdný průnik (tj. číslo je buď prvočíslo, nebo číslo složené). Adobe Systems 21 Definice: prvočíslo, číslo složené Definice 3: Přirozené číslo p>1 nazýváme prvočíslem, právě když má právě dva různé přirozené dělitele (tj. čísla 1 a p). Přirozené číslo a>1, které není prvočíslem (tj. má více než dva přirozené dělitele), nazýváme složeným číslem. Adobe Systems 22 Příklady ̶Číslo 13 je prvočíslo, protože má právě dva přirozené dělitele, čísla 1 a 13. Jsou to samozřejmí dělitelé čísla 13. ̶Číslo 12 je složené číslo, protože má více než dva přirozené dělitele: 1, 2, 3, 4, 6, 12. ̶ ̶ Číslo 1 podle definice není prvočíslo ani číslo složené. Adobe Systems 23 Věta o existenci prvočíselného dělitele Věta 2: Každé přirozené číslo n > 1 má aspoň jednoho prvočíselného dělitele. Důkaz: Číslo n > 1 má alespoň jednoho dělitele, který je větší než 1. Z jeho dělitelů je jeden nejmenší, označme ho p. Tento nejmenší přirozený dělitel p > 1 musí být prvočíslem. Kdyby totiž p bylo složené číslo, tj. p = a.b, kde 1 < a < p , 1 < b < p , pak by ze vztahů a| p a p|n plynulo a| n, což by znamenalo, že existuje dělitel a < p čísla n, což by bylo v rozporu s naším předpokladem, že p je nejmenší z přirozených dělitelů čísla n. Číslo p je tedy prvočíslo. Adobe Systems 24 Jak rozhodneme, zda je dané číslo prvočíslo nebo číslo složené? Máme-li rozhodnout o tom, zda dané číslo a > 1 je prvočíslem nebo složeným číslem, můžeme postupovat tak, že zjišťujeme, zda je dané číslo dělitelné prvočísly menšími než toto číslo. Platí totiž věta: Existuje-li prvočíslo menší než číslo a, které dělí číslo a, pak a je složené číslo. Uvedený postup je však značně zdlouhavý. Proto budeme využívat následující věty: Věta 3. Jestliže přirozené číslo a není dělitelné žádným prvočíslem menším nebo rovným odmocnině z a, pak a je prvočíslo. Adobe Systems 25 Důkaz věty 3 Provedeme nepřímý důkaz, tj. přímý důkaz věty obměněné) Věta obměněná k větě 3: Není-li a prvočíslo, pak je dělitelné aspoň jedním prvočíslem p menším než odmocnina z a. Tedy předpokládejme, že číslo a není prvočíslo, pak podle věty 2. existuje prvočíslo p, které je nejmenším dělitelem čísla a. Můžeme psát: a = q . p a současně p < a; současně platí také: p je menší nebo rovno q . Je tedy a větší nebo rovno p2 a odtud plyne, že p musí být menší nebo rovno odmocnině z a. Adobe Systems 26 Jak zjistit, zda dané číslo je prvočíslo Příklad: Zjistěte, zda 173 je prvočíslo nebo složené číslo. Řešení: Odmocnina ze 173 je menší než 14 (druhá mocnina 14 je 196), proto budeme zjišťovat, zda číslo 173 je dělitelné některým z prvočísel 2, 3, 5, 7, 11, 13. Číslo 173 není dělitelné žádným z těchto prvočísel, proto je prvočíslem. ̶ Adobe Systems 27 Prvočíselný rozklad Adobe Systems 28 Příklady Příklad 12 Rozhodněte a zdůvodněte, zda jsou čísla 437, 593, 1007, 2771, 3012 prvočísla, nebo čísla složená. Příklad 13 Najděte alespoň tři prvočísla větší než 120 a zároveň menší než 150. Příklad 14 Najděte největší prvočíslo, kterým je dělitelné číslo a)1326 b)2406 c)4380 Adobe Systems 29 Příklady Příklad 15 Rozložte na součin prvočinitelů číslo a)500 b)2024 c)1326 Příklad 16 Najděte alespoň tři přirozená čísla, která jsou dělitelná a)všemi jednocifernými prvočísly, b)všemi přirozenými čísly od jedné do deseti. Určete v obou případech nejmenší přirozené číslo, které podmínkám vyhovuje. Adobe Systems 30 Výsledky příkladů Adobe Systems 31 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 4: 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 5: 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 32 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 33 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 34 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 35 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 36 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 37 Čí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 6. 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 7. 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 38 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 39 Příklady Příklad 17 Určete všechny přirozené společné dělitele čísel: a) 60, 36 b) 48, 72, 0 c) 24, -132, 54 Příklad 18 K číslu a = 51 najděte číslo b tak, aby D(a,b) = 17. Příklad 19 Najděte dvě přirozená čísla, jejichž součet je 432 a největší společný dělitel je 36. Adobe Systems 40 Příklady Příklad 20 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 21 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) Adobe Systems 41 Výsledky příkladů Příklad 17: a) 1, 2, 3, 4, 6, 12, b) 1, 2, 3, 4, 6, 8, 12, 24, c) 1, 2, 3, 6 Příklad 18: 51= 17.3, proto b musí být násobek 17,ale ne násobek 3, tomu vyhovuje např. 17, 34, 170 atd. Příklad 19: 36 a 396, 180 a 252 Příklad 20: 24 a 48 Příklad 21: a) 91, b) 72, c) 6, d) 71 Adobe Systems 42 Nejmenší společný násobek Podobně jako u největšího společného dělitele, i zde je pojem intuitivní. Ze všech společných násobků dvou čísel (kterých je ovšem nekonečně mnoho) vybíráme právě ten nejmenší. Např. čísla 15 a 6 mají následující násobky: 15 -> 15; 30; 45; 60; 75; 90; 105; 120; 135; 150; 165; 180 … 6 -> 6; 12; 18; 24; 30; 36; 42; 48; 54; 60; 66; 72; 78; 84; 90; 96 … Nejmenší společný násobek čísel 6 a 15 je číslo 30. Dalšími společnými násobky jsou čísla 60, 90, 120, 150 … Je vidět, že nejmenší společný násobek dělí všechny společné násobky daných dvou čísel. Adobe Systems 43 Definice n(a,b) Definice 8: Společný násobek přirozených čísel a, b je každé přirozené číslo m, které je dělitelné oběma čísly a, b, tedy a|m a b|m. Definice 9: Nejmenší společný násobek přirozených čísel a, b je ten ze společných násobků, který je dělitelem všech společných násobků čísel a, b. Označujeme n(a,b) Adobe Systems 44 Nejmenší společný násobek Adobe Systems 45 Hledání n(a,b) Adobe Systems 46 Příklad Adobe Systems 47 Příklady Příklad 22 Nalezněte alespoň tři přirozené společné násobky čísel a) 5, 12 b) 17, 0 c) - 6, 8, 17 Příklad 23 Určete všechny společné násobky čísel 60 a 144, které jsou větší než 1000 a menší než 2000. Příklad 24 Určete obecně a) n(a,1) c) n(a,ab) b) n(a,a) d) n(a,a+1) Adobe Systems 48 Příklady Příklad 25 Jak se změní nejmenší společný násobek dvou přirozených čísel, když každé z nich vynásobíme třemi? Příklad 25 Určete pomocí rozkladu na prvočinitele i pomocí vztahu mezi n(a,b) a D(a,b) a) n(222, 185) b) n(360, 504) c) n(90, 108, 84) d) n(156, 182, 208) Adobe Systems 49 Výsledky příkladů Příklad 22: a) 60, 120, 240, b) nelze, c) 408, 816, 1224 Příklad 23: 1440 Příklad 24: a) a, b) a, c) ab, d) a.(a+1) Příklad 25: třikrát se zvětší Příklad 26: a) 1110, b) 2520, c) 3780, d) 4368 Adobe Systems 50 Rozklad přirozeného čísla na součin prvočinitelů Prvočíselný rozklad přirozeného čísla využíváme především k výpočtu největšího společného dělitele a nejmenšího společného násobku daných čísel a k určení počtu všech přirozených dělitelů daného přirozeného čísla. Příklady - prvočíselný rozklad: 132 = 2 • 2 • 3 • 11 121 = 11 • 11 72 = 2 • 2 • 2 • 3 • 3 Adobe Systems 51 Výpočet největšího společného dělitele a nejmenšího společného násobku z rozkladu daných čísel na součin prvočinitelů. Největší společný dělitel daných přirozených čísel je součinem všech prvočinitelů, kteří se současně vyskytují v prvočíselných rozkladech všech daných čísel, a to s nejmenším s vyskytujících se exponentů. Nejmenší společný násobek daných čísel je součinem všech různých prvočinitelů, kteří se vyskytují v rozkladech daných čísel, a to v největší mocnině. Adobe Systems 52 Hledání D(a,b) a n(a,b) pomocí prvočíselného rozkladu Příklad: Zjistěte D(108, 90) a n(108, 90). Řešení: 108 = 22. 33 90 = 2 . 32 . 5 D(108, 90) = 2 . 32 = 18 n(108, 90) = 22. 33. 5 = 540 Adobe Systems 53 Určení počtu dělitelů Adobe Systems 54 Příklad Adobe Systems 55 Příklady Příklad 27. Vypočítejte a) D[n(84, 54), n(24, 132)] b) n[D(84, 132), n(24, 54)] b) Příklad 28. Zjistěte, zda platí: D[n(48, 72), n(48, 144)] = n [48, D(72, 144)] 1. Příklad 29. Určete nejmenší nenulové přirozené číslo, kterým je třeba násobit a) číslo 1224, abychom dostali druhou mocninu přirozeného čísla b) číslo 600, abychom dostali třetí mocninu přirozeného čísla. Adobe Systems 56 Příklady Příklad 30. Určete všechny přirozené dělitele čísel 68, 360, 504. Příklad 31. Určete počet všech přirozených dělitelů čísel 420, 824, 687. Příklad 32. Obdélník o rozměrech 56cm a 98cm se má rozdělit příčkami rovnoběžnými se stranami obdélníku na čtverce co možná největší. Kolik bude čtverců a jak velká bude jejich strana? Příklad 33. V krabici jsou tužky. Víme, že je jich více než 200 a méně než 300 a že se dají svázat do svazků po 10 a po 12. Kolik je tužek krabici? Adobe Systems 57 Výsledky příkladů Příklad 27: a) 12, b) 216 Příklad 28: ano, obě strany se rovnají 144 Příklad 29: a) 34, b) 45 Příklad 30: 68: 1, 2, 4, 17, 34, 68 360: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360 504: 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504 Příklad 31: 420 má 24 dělitelů, 824 má 8 dělitelů, 687 má 4 dělitele Příklad 32: 28 čtverců s hranou délky 14 cm Příklad 33: 240 tužek