Dělitelnost v oboru celých čísel I. Úvod, základní pojmy Definice. Říkáme, že celé číslo b dělí celé číslo a (nebo b je dělitelem a nebo a je dělitelné b nebo a je násobkem b), právě když existuje celé číslo x, pro které platí a = b . x. Zapisujeme b | a. Jestliže k číslům a, b Î Z neexistuje x Î Z takové, že a = b . x, říkáme, že b nedělí a a zapisujeme b ∤ a. Definice. Platí-li a = b . x, pak čísla b a x jsou dělitelé čísla a a nazývají se sdružení dělitelé čísla a. Dělitelé čísla a patřící do množiny přirozených čísel se nazývají přirození dělitelé čísla a. Poznámka. 1. Každé celé číslo a ¹ 0, 1, -1 má alespoň 4 celočíselné dělitele, a to čísla 1, a, -1, -a. Tyto dělitele nazýváme samozřejmými (triviálními) děliteli čísla a. (Ostatní dělitele čísla a, pokud existují, nazýváme nesamozřejmými nebo netriviálními děliteli čísla a.) 2. Čísla 1 a –1 mají právě dva dělitele v množině Z, a to 1, -1. 3. Číslo 0 má nekonečně mnoho dělitelů, a to každé celé číslo. 4. Číslo 0 není dělitelem žádného nenulového čísla a, protože neexistuje žádné celé číslo x tak, aby platilo 0 . x = a . 5. Číslo 0 je dělitelem sebe sama (0|0), neboť pro libovolné celé číslo x platí 0 . x = 0. Poznamenejme ještě, že tento poslední případ se v praxi nezavádí ani nevyužívá. Proto ve školské matematice říkáme, že podíl není definován (pouze v matematické analýze se předchozí zlomek řeší jako tzv. neurčitý výraz při počítání limit). Věta. Pro libovolná celá čísla a, b, c platí: a) (b| a Ù b| c) Þ (b| (a + c) Ù b| (a-c) , b) b| a Þ (-b)| a , c) b| a Þ b|(-a). Poznámka. Na základě části b) a c) věty 10.27. můžeme dále teorii dělitelnosti budovat jen v množině přirozených čísel. (Určíme-li přirozené dělitele přirozeného čísla a, umíme snadno určit všechny dělitele čísla a i čísla -a). Definice. Celé číslo, které je dělitelné dvěma se nazývá sudé číslo. Celé číslo, které není dělitelné dvěma (tj. při dělení dvěma dává zbytek 1) se nazývá liché číslo. II. Znaky dělitelnosti Znaky dělitelnosti jsou věty, které umožňují rozhodnout o dělitelnosti čísla jiným číslem bez provedení dělení, jen ze zápisu daného čísla. Ve všech dalších úvahách máme na mysli přirozená čísla zapsaná v desítkové soustavě. Věta. 1. 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. 2. Přirozené číslo a je dělitelné čtyřmi, právě když je čtyřmi dělitelné číslo zapsané jeho posledním dvojčíslím. 3. Přirozené číslo a je dělitelné osmi, právě když je osmi dělitelné číslo zapsané jeho posledním trojčíslím. 4. Přirozené číslo a je dělitelné třemi (devíti), právě když je třemi (devíti) dělitelný jeho ciferný součet. (Ciferný součet je součet všech čísel zapsaných jednotlivými číslicemi v zápisu čísla a) 5. Přirozené číslo a je dělitelné jedenácti, právě 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. Uvedené znaky dělitelnosti plynou z obecnější věty: Věta. I. 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. II. Dělíme-li přirozené číslo a (aspoň trojciferné) čtyřmi, dostaneme stejný zbytek, jako když dělíme čtyřmi číslo zapsané jeho posledním dvojčíslím. III. Dělíme-li přirozené číslo a (aspoň čtyřciferné) osmi, dostaneme stejný zbytek, jako když dělíme osmi číslo zapsané jeho posledním trojčíslím. IV. 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. V. 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 ciframi sudého řádu zmenšený o součet čísel zapsaných ciframi lichých řádů. Věta. Je-li celé číslo a součtem dvou celých čísel, z nichž jedno je násobkem celého čísla b, pak druhý sčítanec dává při dělení číslem b stejný zbytek jako číslo a. III. Největší společný dělitel Definice. 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. 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). Poznámka 10. 34. V množině přirozených čísel lze též říci, že největší společný dělitel je největší (maximální) číslo z množiny všech společných dělitelů. Poznámka 10. 35. Největší společný dělitel dvou čísel můžeme určit různými způsoby: a) využitím definice, b) pomocí tzv. Euklidova algoritmu (na základě následující věty), c) pomocí rozkladu daných čísel na součin prvočinitelů. Věta. 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 a platí nerovnost 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. Také 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 problém určení D(a, b) na určení D(b, z). Čísla b a z jsou menší než čísla a, b. Použití Euklidova algoritmu ukážeme na příkladě: Příklad. Určete D(600, 252) pomocí Euklidova algoritmu. Řešení: 600 : 252 = 2 neboli 600 = 252 . 2 + 96 96 252 : 96 = 2 252 = 96 . 2 + 60 60 96 : 60 = 1 96 = 60. 1 + 36 36 60 : 36 = 1 60 = 36 . 1 + 24 24 36 : 24 = 1 36 = 24 . 1 + 12 12 24 : 12 = 2 24 = 12 . 2 0 Největší společný dělitel čísel 600 a 252 je číslo 12, tj. poslední nenulový zbytek při postupném dělení. Definice. Přirozená čísla a, b se nazývají nesoudělná, právě když je jejich největší společný dělitel roven 1, tedy D(a, b) = 1. 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, tedy D(a, b) > 1. Definice. Nechť a[1], a[2 ],[, ]a[3 ], ..., a[n ], n > 2, jsou nesoudělná přirozená čísla (s vlastností D(a[1], a[2 ],[, ]a[3 ], ..., a[n]) = 1). Jestliže pro libovolnou dvojici indexů i, j Î {1, 2, ..., n} platí D(a[i ], a[j ]) = 1, pak říkáme, že [ ]čísla a[1], a[2 ],[, ]a[3 ], ..., a[n ]jsou po dvou nesoudělná. Jestliže naopak existuje dvojice indexů i, jÎ {1, 2, ..., n} s vlastností D(a[i ], a[j ]) > 1, pak říkáme, že čísla a[1], a[2 ],[, ]a[3 ], ..., a[n ]nejsou po dvou nesoudělná (jsou pouze nesoudělná podle předpokladu). Příklad. Čísla 7, 19, 31 jsou po dvou nesoudělná, zatímco čísla 6, 10, 15 jsou „pouze“ nesoudělná. IV. Nejmenší společný násobek Definice 10. 42. 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, tj. a│m a b│m. Nejmenší kladný 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. Zapisujeme n(a, b). Poznámka. V množině přirozených čísel lze též říci, že n(a, b) je nejmenší číslo z kladných společných násobků čísel a, b. Definici lze rozšířit na libovolný konečný počet přirozených čísel a[1], …, a[n]. Poznámka. Nejmenší společný násobek čísel a, b můžeme určit různými způsoby: a) využitím definice, b) pomocí vztahu mezi n(a, b) a D(a, b) c) pomocí rozkladu daných čísel na součin prvočinitelů Věta. Pro každá dvě přirozená čísla a, b platí a . b = n(a, b) . D(a, b). Poznámka. Tuto větu nelze rozšířit na více než dvě přirozená čísla. V. Obecná kritéria dělitelnosti: Věta: Je-li přirozené číslo dělitelné po dvou nesoudělnými čísly, je dělitelné i jejich součinem. Tuto větu lze také obrátit. Příklad. Platí 12 = 3 . 4, 18 = 2 . 9, 165 = 3 . 5 . 11. Proto lze dělitelnost číslem dvanáct odvodit ze současné dělitelnosti čísly 3 a 4, dělitelnost číslem 18 pomocí dělitelnosti čísly 2 a 9 a dělitelnost číslem 165 pomocí dělitelnosti čísly 3, 5 a 11. VI. Prvočísla, čísla složená Definice. 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. Poznámka. Číslo 1 podle definice není prvočíslo ani číslo složené. Věta. Každé přirozené číslo n > 1 má alespoň jednoho prvočíselného dělitele, menšího než . Důsledek. Jestliže přirozené číslo n není dělitelné žádným prvočíslem menším nebo rovným , pak n je prvočíslo. Věta.. Každé složené číslo a lze vyjádřit právě jedním způsobem ve tvaru součinu konečného počtu prvočísel [] kde p[1], p[2], ….., p[k] jsou prvočísla, e[1], e[2], …, e[k] jsou nenulová přirozená čísla. Tento zápis se nazývá prvočíselný (někdy též kanonický) rozklad přirozeného čísla a a p[1], p[2], ….., p[k][ ] jsou tzv. prvočinitelé rozkladu. Poznámka. Prvočíselný rozklad přirozeného čísla využíváme především a) k výpočtu největšího společného dělitele a nejmenšího kladného společného násobku daných čísel a, b b) k určení počtu všech přirozených dělitelů daného přirozeného čísla a c) k určení všech přirozených dělitelů daného přirozeného čísla a. ad a) 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ě. Příklad. Určete D(108, 90) a n(108, 90). Řešení: 108 = 2^2. 3^3 90 = 2 . 3^2 . 5 NSD(108, 90) = 2 . 3^2 = 18 NSN(108, 90) = 2^2. 3^3. 5 = 540 ad b) Určení počtu všech přirozených dělitelů daného přirozeného čísla: Věta. Je-li prvočíselný rozklad přirozeného čísla a > 1, pak počet všech přirozených dělitelů čísla a (ozn.t(a)) je určen takto: t(a) = (e[1] + 1).(e[2] + 1). … .(e[k] + 1) ad c) Všechny přirozené dělitele čísla a určíme jako všechny možné součiny všech prvočinitelů čísla a, přičemž každý prvočinitel je umocněn postupně na všechny mocniny od 0 až po tu, ve které se vyskytují v kanonickém rozkladu čísla a. Příklad. Zjistěte počet všech přirozených dělitelů čísla 648 a napište všechny přirozené dělitele čísla 648. Dále určete všechny dvojice sdružených dělitelů čísla 648. Řešení: 648 = 2^3 . 3^4, t(648) = (3+1) . (4+1) = 20, tzn. číslo 648 má 20 přirozených dělitelů. 3^0 3^1 3^2 3^3 3^4 2^0 1 3 9 27 81 2^1 2 6 18 54 162 2^2 4 12 36 108 324 2^3 8 24 72 216 648 Sdružené dvojice dělitelů: 1 . 648, 2 . 324, 3 . 216, 4 . 162, 6 . 108, 8 . 81, 9 . 72, 12 . 54, 18 . 36, 24 . 27. VII. Neurčité rovnice (někdy též diofantické nebo diofantovské) Neurčité rovnice jsou rovnice se dvěma nebo více neznámými, které se řeší v oboru všech celých čísel. Definice. Lineární neurčitá rovnice o dvou neznámých x, y je rovnice a . x + b . y = c, a ¹ 0, b ¹ 0 , a, b, c Î Q. Poznámka. Je-li alespoň jeden z koeficientů a, b, c racionální necelé číslo, vynásobíme rovnici vhodným číslem tak, aby všechny tři koeficienty nabyly celočíselných hodnot. Věta. (Řešitelnost lineární neurčité rovnice.) Neurčitá rovnice a . x+ b . y = c má řešení v případě, že největší společný dělitel koeficientů a, b je také dělitelem čísla c . Pak řešením je nekonečně mnoho dvojic celých čísel x , y. V případě, že největší společný dělitel čísel a, b není dělitelem koeficientu c, pak rovnice nemá řešení. Postup řešení neurčité rovnice: I. Nechť x[0] , y[0 ]je jedno pevné řešení neurčité rovnice. Potom obecné řešení je dáno vztahy x = x[0] + , y = y[0] - , t Î Z . Výchozí dvojice x[0] , y[0 ]se určí buďto úsudkem nebo se vypočte z podílů Eukleidova algoritmu při hledání NSD(a, b). II. Redukční metoda. Dělitelnost celých čísel – cvičení 1) Určete vlastnosti relace dělitelnosti v množině všech celých čísel. 2) Dokažte: a) Součet každých dvou sudých čísel je sudé číslo. b) Součet každých dvou lichých čísel je sudé číslo. c) Součet libovolného sudého a libovolného lichého čísla je liché číslo. d) Součin každých dvou sudých čísel je dělitelný čtyřmi. e) Součin každých dvou lichých čísel je liché číslo. f) Součin libovolného sudého a libovolného lichého čísla je sudé číslo. g) Součet tří po sobě jdoucích mocnin čísla 2 (počínaje mocninou 2^1) je dělitelný sedmi. 3) Dokažte: a) Druhá mocnina každého lichého čísla zmenšená o 1 je dělitelná osmi. b) Rozdíl druhých mocnin dvou libovolných lichých čísel je dělitelný osmi. c) Součet tří po sobě následujících čísel, z nichž prostřední je sudé, je dělitelný šesti. 4) Jsou dána celá čísla a a b, pro která platí, že a je dělitelné dvanácti a b je dělitelné patnácti. Dokažte, že jejich součin a.b je dělitelný čísly 36 a 20. 5) Nejsou-li čísla a, b dělitelná třemi, je vždy jedno z čísel a + b, a – b dělitelné třemi. Dokažte. 6) O pěticiferném čísle 448** , jehož poslední dvě cifry neznáme, víme, že je dělitelné 3 a 25. Doplňte chybějící cifry. 7) V číslech 437*, 32*, 4*54 nahraďte *, pokud je to možné, takovou cifrou, aby vzniklé číslo bylo dělitelné: a) čtyřmi, b) osmi, c) devíti, d) jedenácti. 8) Dokažte kritérium dělitelnosti čtyřmi, osmi a devíti. 9) Rozhodněte, zda čísla a) 4356, b) 8724 jsou dělitelná čísly 2, 3, 4, 5, 8, 9, 11. Pokud nejsou dělitelná uvažovaným číslem, určete zbytek, který vznikne při dělení tímto číslem. 10) Zjistěte, která z čísel 1007, 2487, 2771 jsou prvočísla. 11) Dokažte, že každé prvočíslo větší než 3 je možno vyjádřit buď ve tvaru 6k+1, nebo ve tvaru 6k+5, kde k je přirozené číslo. 12) Určete všechny společné dělitele čísel: a) 60, 36 b) 48, 72, 0 c) 24, -132, 54 13) Určete oběma způsoby: a) D(455, 273) c) D(90, 108, 84) b) D(360, 504) d) D(568, 426, 355) 14) K číslu a = 51 najděte číslo b tak, aby D(a,b) = 17. 15) Najděte dvě přirozená čísla, jejichž součet je 432 a největší společný dělitel je 36. 16) 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? 17) Napište libovolné tří společné násobky čísel: a) 5, 12 b) 17, 0 c) -6, 8, 17 18) Určete různými způsoby: a) n(222, 185) c) n(90, 108, 84) b) n(360, 504) d) n(156, 182, 208) 19) Zjistěte, zda platí: n[64, D(60,42)] = D[n(30,64), n(42,64)] 20) Najděte přirozená čísla a, b, je-li: a) D(a,b) =2, n(a,b) =12 b) D(a,b) =7, n(a,b) =22 21) Určete všechny přirozené dělitele čísel 68, 360, 504. 22) Určete počet všech přirozených dělitelů čísel 420, 824, 2047. 23) 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. 24) Připíšeme-li k libovolnému trojcifernému číslo totéž číslo zprava, dostaneme šesticiferné číslo, které je dělitelné sedmi, jedenácti a třinácti. Dokažte. 25) Dokažte, že čísla 353 535, 424 242, 666 666, tj čísla tvaru ababab, jsou dělitelná čísly 3, 7, 13 a 37. 26) 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? 27) 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 v krabici? 28) Kolik různých obdélníků lze vymodelovat z 60 shodných čtverců? (Vždy použijeme všechny.) 29) Řešte neurčité rovnice: a) -3x + 7y = 4 c) -14x - 3y = 10 b) 6x – 22y = 12 d) 5x – 3y = 15 30) Kolika způsoby můžeme vyplatit 69 Kč pouze dvoukorunami a pětikorunami? 31) Alena má 50 Kč a chce je utratit za lízátka a čokoládové tyčinky. Lízátko stojí 4 Kč a tyčinka 6 Kč. Kolik lízátek a kolik tyčinek si může Alenka koupit za 50 Kč? 32) Určete největší (nejmenší) trojciferné číslo, které při dělení třemi dává zbytek 2 a Při dělení sedmi dává zbytek 5. 33) Číslo 91 rozložte na součet dvou sčítanců, z nichž jeden je dělitelný pěti a druhý devíti. 34) Vytvoří-li žáci ve třídě čtveřice, jeden žák zbude, vytvoří-li trojice, zbudou dva žáci. Kolik žáků je ve třídě (ve třídě je více než 20 žáků a méně než 30)? 35) Rozdíl dvou přirozených čísel, z nichž první je dělitelné číslem 23, druhé číslem 29, je roven 1. Určete nejmenší taková kladná čísla. KONTROLNÍ PRÁCE - vzor zadání 1. Jsou dána dvě přirozená čísla a, b, pro která platí: a je dělitelné osmi, b je dělitelné devíti. Dokažte, že součin a.b těchto dvou čísel je dělitelný dvanácti. 2. Na místa symbolů x, y doplňte v čísle 38x7y takové cifry, aby vzniklé číslo bylo dělitelné číslem 36. Uveďte všechny možnosti. 3. Rozložte na prvočinitele číslo 2088 a určete počet všech jeho přirozených dělitelů. 4. Vypište pomocí tabulky všechny přirozené dělitele čísla 150. Dále zjistěte, kterým nejmenším nenulovým číslem je potřeba číslo 150 vynásobit, aby vznikla druhá mocnina přirozeného čísla. 5. Kolik různých obdélníků lze složit ze 150 shodných čtvercových dlaždic? 6. Rozhodněte a zdůvodněte, zda je číslo 667 prvočíslo nebo číslo složené. 7. Pomocí Eukleidova algoritmu určete D(a,b), kde a = 296, b = 492. Dále určete n(296, 492). 8. Vypočítejte: D[n(48, 72), D(126, 108)]. 9. Pomocí neurčité rovnice řešte úlohu: Rozložte číslo 115 na dva přirozené sčítance různé od nuly, z nichž jeden je dělitelný 7 a druhý dává při dělení 6 zbytek 1. Určete všechny možnosti. 10. Definujte pojmy: - číslo a je dělitelné číslem b - složené číslo - čísla a, b jsou soudělná - největší společný dělitel čísel a, b - rozklad přirozeného čísla a na součin prvočinitelů