DĚLITELNOST CELÝCH ČÍSEL Def. 1 Ří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. Symbolicky: b|a o (3 x e C)( a = b . x ) Jestliže k číslům a,b € C neexistuje x e C takové, že a - b . x, říkáme, že b nedělí a. b f a c'1 Platí-li, že a = b . x, pak čísla b a x jsou dělitelé čísla a a nazývají se sdružení dělitelé čísla a. Pozn. 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 děliteli čísla a. (Ostatní dělitele, pokud existují, nazýváme nesamozřejmými.) 2. Čísla 1 a -1 mají právě dva dělitele v množině C, 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. Cvičení: 1. Doplňte: Číslo 10 má 12 dělitelů, jsou to čísla: Dvojice sdružených dělitelů čísla 10: Samozřejmí dělitelé čísla 10: Přirození dělitelé čísla 10 (to jsou dělitele čísla 10 patřící do množiny přirozených čísel): 2. Zjistěte, jaké vlastnosti má binární relace „dělitelnost celých čísel", a tvrzení dokažte. Věta 1. Pro libovolná celá Čísla a, b, c platí a) (b|a a b|c) (bja+c a b|a-c) b) b|a => (-b)|a c) b|a b|(-a) Důkaz: Pozn. Na základě části b) a c) uvedené věty můžeme dále pracovat 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.). 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 čísla Ve všech dalších úvahách máme na mysli přirozená čísla zapsaná v desítkové soustavě. 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. Tyto znaky dělitelnosti plynou z obecnějších vět: 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 dvojčí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ů. Důkazy vět I. - V. provedeme s využitím následující věty. Věta 2. Je-li celé číslo a součtem dvou celých čísel, z nichž jedno je násobkem celého čísla b, pak druhé dává při dělení číslem b stejný zbytek jako číslo a. (Důkaz viz učebnice s. 185) Def. 2 Přirozené číslo p>l nazýváme prvočíslem, právě když má právě dva přirozené dělitele. Přirozené číslo a>l, které není prvočíslem (tj. má více než dva přirozené dělitele), nazýváme složeným číslem. O tom, zda dané číslo je prvočíslo nebo složené číslo, můžeme rozhodnout pomocí tzv. Eratosthenova síta nebo podle věty 3. Věta 3. Jestliže přirozené číslo a není dělitelné žádným prvočíslem menším nebo rovným -Ja , pak a je prvočíslo. Př. Zjistěte, zda 173 je prvočíslo nebo složené číslo. |l73< 14, 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. Věta 4. 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 pi, p2,....., pk jsou prvočísla, ei, ci, ■ ■., e^ jsou nenulová přirozená čísla. Tento zápis se nazývá prvočíselný rozklad přirozeného čísla a a pi, p2,....., Pk jsou tzv. prvočinitele rozkladu. Př. 600 = 23. 31. 52 Def. 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. Def. 4 Nej vě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. V množině přirozených čísel lze též říci, že největší společný dělitel je největší (maximální) číslo ze společných dělitelů. Def. 5 Přirozená čísla a, b se nazývají nesoudělná, právě když je jejich největší společný dělitel roven 1. D(a,b) = 1 Def. 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. D(a,b) > 1. Def. 7 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. Def. 8 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). Pozn. 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. Pozn. Definice 3 - 8 lze rozšířit na libovolný konečný počet přirozených čísel ai,..., an. Určování D(a,b) a n(a,b) 1) pomocí Euklidova algoritmu 2) z rozkladů čísel na součin prvočinitelů ad 1) Euklidův algoritmus vychází z věty 7.1 (uč. na str. 189). Podle této věty platí: Jestliže přirozené číslo a dává při dělení nenulovým přirozeným číslem b zbytek z, tj. a = b.q + z a z < b, pak 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. Př. Zjistěte D(268, 80) 268 : 80 = 3 neboli 268 = 80 . 3 + 28 28 80 : 28 = 2 80 = 28 . 2 + 24 24 28 : 24 = 1 28 = 24. 1 + 4 4 24 : 4 = 6 24 = 6 . 4 0 Největší společný dělitel čísel 268 a 80 je číslo 4, tj. poslední nenulový zbytek při postupném dělení. Nejmenší společný násobek čísel a, b pak lze vypočítat podle věty 8.2 v učebnici na str. 191. Věta 4: Pro každá dvě přirozená čísla a, b platí: n(a,b) . D(a,b) = a . b ad 2) Určení 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ě. Př. Zjistěte D(108, 90) a n(108, 90). 108 = 22. 33 90 = 2 . 32. 5 D(108,90) = 2.32= 18 n(108, 90) = 22. 33. 5 = 540 Určení počtu všech přirozených dělitelů daného přirozeného čísla: Věta 5: Je-li a = pel.pe2.....pek prvočíselný rozklad přirozeného čísla a > 1, pak počet všech přirozených dělitelů čísla a (ozn, # (a)) je určen takto: 5(a) = (ei + l).(e2+l).....(ek+l) Všechny přirozené dělitele čísla a určíme jako všechny možné součiny prvočinitelů, přičemž každý prvočinitel, probíhá všechny mocniny od 0. po tu, ve které se vyskytují v rozkladu. 2° .5° 1 3 9 90 - 2 . 32.5 2° 51 5 15 45 21 .5° 2 6 18 ,9 (90) = (1+1). (2+1). (2+1) =12 21 51 10 30 90 Kongruence, rozklad na zbytkové třídy. Věta: Nechť a, b jsou celá čísla taková, že b * 0. Potom existují celá čísla q, r splňující vztah: a-bq + r, 0 < r < | & |, přičemž toto vyjádření je jednoznačné. Poznámka: Je nutno si uvědomit, že zbytek r při dělení je vždy nezáporný, a to i při dělení záporným číslem. Např. a = -26, b = 8, q = -4, r = 6, protože -26 = 8 . (-4) + 6. Poznámka: Celá čísla a, b jsou nesoudělná, je-li jejich největší společný dělitel roven jedné. V opačném případě se nazývají soudělná. Největší společný dělitel čísel a, b budeme označovat NSD(a, b), nejmenší kladný společný násobek NSN(a, b). Eulerova funkce cp(n) vyjadřuje počet přirozených čísel menších nebo rovných číslu n, k y nesoudělných s n. Nechť n = p*' . ... pkat, pak platí q>(n) = n .TT(1--). Je-li 7=ľ Pi n prvočíslo, pak q>(n) - n -1. Kongruence: a, b e Z, m e N, m > 2. Platí a = b <=> m | (a - b). Čteme: Číslo a je kongruentní s číslem b podle modulu m. Dvě čísla kongruentní podle nějakého modulu m dávají při dělení tímto modulem m týž zbytek. Relace kongruence je ekvivalence na množině všech celých čísel (je reflexivní, symetrická a tranzitivní). Vlastnosti kongruenci: 1) p prvočíslo a = b (mod^n) => a = b (mod p) Platí-li kongruence podle modulu, který je mocninou prvočísla, platí i podle modulu rovného tomuto prvočíslu. 2) a = b (mod mj , í = 1,2,...,k => a = b (mod NSN(m/%)) Platí-li kongruence podle několika modulů, platí i podle modulu rovného nejmenšímu společnému násobku těchto modulů. k k k k 3) fl|5 bx (mod m), i- l,...,k=> ^Ta, = ^ž>(. (modm), Y\ai = IT^ (mod m). 1=1 í=l i=l i=l Kongruence podle téhož modulu lze sčítat i násobit. Nechť v dalším platí a = b (mod m): 4) a + x = b + x (mod m), a.y = b.y (mod m) K oběma stranám kongruence lze přičíst stejné celé číslo a obě strany kongruence lze vynásobit týmž celým číslem. Obecně ale nelze obě strany kongruence dělit týmž celým číslem, např. 24 s 40 (mod 8), ale po vydělení čtyřmi 6 # 10 (mod 8). 5) m |z => a + z = b (mod m) Celé Číslo, které je násobkem modulu, lze přičíst pouze k jedné straně kongraence. 6) a" s b" (mod m) Obě strany kongruence lze umocnit na libovolný přirozený exponent. 7) d la Ad lb a NSD(4m) = 1 => — s — (mod m) 1 d d Obě strany kongruence lze vydělit celým číslem nesoudělným, s modulem. 8) ac = bc (mod mc) Obě strany kongruence i modul lze vynásobit týmž celým kladným číslem. 9) e b a e\b a e\c =í> — = — (mod —) e e e Obě strany kongruence i modul lze vydělit týmž celým kladným číslem různým od nuly. 10) a s b (mod m) a á Im => a s £> (mod ď) Platí-li kongruence podle modulu m, platí i podle modulu rovného libovolnému kladnému děliteli čísla m, většímu než jedna. Eulerova věta: weN, m > 1, a e Z, D(a,m) = 1, pak ä | x = i (mod m) }, pro i — 0,1, ... , m—1. Ekvivalentnost vyjádření okamžitě plyne z věty ., uvědoiníme-li si zřejmý fakt, že číslo i, kde 0 < i < m—l, dává po dělení číslem m zbytek i. Z věty o dělení se zbytkem celých čísel plyne, že zbytkových tříd podle modulu rn musí být opravdu právě m (neboť zbytek po dělení každého celého čísla číslem m musí podle této věty nabývat právě jedné z hodnot 0,1,..., m—1). Dále, každá zbytková třída podle modulu m obsahuje zřejmě nekonečně mnoho celých čísel, lišících se o nějaký celočíselný násobek modulu rn. Pokusíme-li se schematicky zapsat jednotlivé zbytkové třídy podle modulu m, dostaneme f c() = {... i -2™ i —m , 0 , ~rn , 2m , } Cx = {... , -2m + 1 , —m + 1 , 1 , rn + 1 , 2m + 1 , •• } C2 « {... , -2rn + 2 , -m + 2 , 2 , m + 2 , 2m + 2 , •• } ''m-1 — {••• , -m - 1 , -1 , m — 1 , 2m - 1 , 3rn — 1 , ■■■:■} / VtílU / Důkaz. V EVU NetM m je pevné přirozené číslo. Pak množina Zm Viech zbytkových tříd podle, modulu m tvoří rozklad na množině Z všech celých čísel. / - Uvažme množinu zbytkových tříd Zm = {Co. Ci,..., Cm_i} . dokážeme, že Zm je rozklad na Z. 1. každá ze zbytkových tříd d je zřejmě neprázdnou podmnožinou v Z. 2. iiecuť d, Cj £ Z a C< n Cj # 0. Potom existuje číslo r e C\ n Cs , což znamená, že i dává po dělení číslem m zbytek t a Boučasiiô také zbytek j. Ale z věty o dělení celých čísel se zbytkem víme, že zbytek po delení je určen jednoznačně, tzn. i = j, odkud dostáváme, že d = Cj . 3. zřejmě platí, že sjednocení Co U Ci U • • • U Cm_i = Z. /WuvC ^LcL jctóbl at fKQ§.) = 2, n(a,£>) = 12 b) D(a,Z>) = 7, n(a,6) = 22 22) Určete nejmehší 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. 23) Připíšeme-li k libovolnému trojcifemému číslo totéž číslo zprava, dostaneme šesticiferné číslo, které je dělitelné sedmi, jedenácti a třinácti. Dokažte. 24) Dokažte, že čísla 353 535, 424 242, 666 666, tj čísla tvaru ababab, jsou dělitelná čísly 3,7, 13 a 37. 25) 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? 26) 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 v krabici tužek? 27) Řešte neurčité rovnice: a) -3x + 7y = 4 c)-14x-3y=10 b) 6x-22y=12 d) 5x-3y=15 28) Kolika způsoby můžeme vyplatit 69 Kč pouze dvoukorunovými a pětikorunovými mincemi? 29) 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. 30) Číslo 91 rozložte na součet dvou sčítanců, z nichž jeden je dělitelný pěti a druhý devíti. 31) Alenka si chce za 50 Kč koupit lízátka a žvýkačky. Lízátko stojí 4 Kč, žvýkačka 6 Kč. Kolik lízátek a kolik žvýkaček může Alenka koupit, chce-li utratit celou padesátikorunu? 32) Rozdíl dvou přirozených čísel, z nichž první je dělitelné čísle 23, druhé číslem 29, je roven 1. Určete nejmenší taková kladná čísla. 33) Ve třídě je více než 20 žáků a méně než 30 žáků. Vytvoří-li žáci ve třídě čtveřice, jeden žák zbude, vytvoří-li trojice, zbudou dva žáci. Kolik žáků je ve třídě? Poziční číselné soustavy - počítání pojedná ^xZáklad Číslo \^ 2 3' I 4. 5 6 7 8 9 10 11 12 13 14 15 16 0 0 0 i 0 • 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 i 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10 2 ; 2 2 2 2 2 2 2 2 2 2 2 . 2 2 3 11 ío ; 3 3 . 3 3 3 3 3 3 3 3 3 3 3. . 4 100 11 ■■ 10 4 4 4 4 4 4 4 4 4 4 4 4 5 101 12 11 10 5 5 :5 . 5 5 5 5 5 ■ 5 5 5 6 110 20 12 11 10 6 6 6 6 6 6 6 6 6 6 7 111 21 13 .. 12 11 10 7 7 ■7 ■7 7 7 7 : 7 7 8 1000 22 20 13 12 11 10 8 8 8 8 8 8 8 8 9 1001 100 21 14 13 12 11 10 9 9 9 9 9 9 9 10 1010 101 22 20 14 13 12 11 10 A A A A A A 11 1011 102 23 21 15 14 13 12 11 10 B B B B B 12 1100 110 30 22 20 15 14 13 12 11 10 C C C C 13 1101 111 31 23 21 16 15 14 13 12 11 .10 D D D 14 1110 112 32 24 22 ' 20 16 15 14 13 12 11 10 E E 15 1111 120 33 30 23 21 17 16 15 14 13 12 11 10 F 16 . 10000 121 100 31 24 22 20 17 16 15 14 13 12 11 10 17 10001 122 101 32 25 23 21 18 17 16 15 14. 13 12 11 18 10010 200 102 33 30 24 22 20 18 17 16 15 14 13 12 19 10011 201 103 34 31 25 23 21 19 18 17 16 15. 14 .13 20 10100 202 110 40 32 26 24 22 20 19 18 17 16 15 14 21 10101 210 111 41 33 30 25 23 21 1A 19 18 17 16 15 22 10110 211 112 42 34 31 26 24 22 20 1A 19 18 17 16 . 23 10111 212 113 43 35 32 27 25 23 21 1B 1A 19 18 17 24 11000 220 120 44 40 33 30 26 24 22 20 1B 1A 19 18 25 11001 221 121 100 41 34 31 27 25 23 21 1C 1B 1A 19 26 11010 222; 122 101 42 35 32 28 26 24 22. 20 1C 1B 1A 27 11011 1000 123 102 43 36 33 30 27 25 23' 21 ID 1C 1B 28 11100 1001 130 103 44 40 34 31 28 26 24 22 20 1D 1C 29 11101 1002 131 104. 45 41 .35 32 29 27 25 23 .21 1E 1D 30 11110 1010 132 110 50 42 36 33. 30 28 26 24 22 20 1E 31 11111 1011 133 111 51 43 37 34 31 29 27 25 23 21 1F 32 100000 1012 200 112 52 44 40 35 32 2A 28 26 24 22 20 33 100001 1020 201 113 53 45 41 36 33 30 29 27 25 23 21 34 100010 1021 202 1Í4 54 46 42 37 34 31 2A 28 26 24 22 35 100011 1022 203 120 55 50 43 38 35 32 2B 29 27 25 23 36 100100 1100 210 121 100 51 44 40 36 33: 3.0 2 A 28 26 24 37 100101 1101 211 122 101 52 45 41 37 34 32 2B 29 27 25 38 100110 1102 212 123 102 53 46 42 38 35 32 2C 2A 28 26 39 100111 1110 213 124 103 54 47 43 39 36 33 30 2B 29 27 40 101000 1111 220 130 104 55 50 44 40 37 34 31 2C 2A 28