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.