Ří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 C neexistuje x Z takové, že a = b . x, říkáme, že b nedělí a a zapisujeme b ∤ a. 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. Dělitelé čísla a patřící do množiny přirozených čísel se nazývají přirození dělitelé čísla a. 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 různé od nuly. 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. Věta 1. 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) 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. Na základě části b) a c) uvedené věty 1. 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.). 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 čí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. Uvedené 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 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ů. Důkazy vět I. – V. lze provést s využitím věty 2. 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. PRVOČÍSLA, SLOŽENÁ ČÍSLA 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 3. Každé přirozené číslo n > 1 má aspoň jednoho prvočíselného dělitele, menšího než . Věta 4. Jestliže přirozené číslo a není dělitelné žádným prvočíslem menším nebo rovným , pak a je prvočíslo. Věta 5. 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ý rozklad přirozeného čísla a a p[1], p[2], ….., p[k][ ] jsou tzv. prvočinitelé rozkladu. NEJVĚTŠÍ SPOLEČNÝ DĚLITEL 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 NSD(a, b). Poznámka. 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ů. Největší společný dělitel čísel můžeme určit různými způsoby: a) využitím definice, b) pomocí tzv. Euklidova algoritmu, c) pomocí rozkladu daných čísel na součin prvočinitelů. Věta 6. 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 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. NSD(a, b) = NSD(b, z). Tím převádíme problém určení NSD(a, b) na určení NSD(b, z). Čísla b a z jsou menší než čísla a, b. Na větě 6. je založen postup výpočtu největšího společného dělitele dvou přirozených čísel nazývaný Euklidův algoritmus. Použití Euklidova algoritmu ukážeme na příkladě: Příklad: Určete NSD(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 1. Přirozená čísla a, b se nazývají nesoudělná, právě když je jejich největší společný dělitel roven 1, tedy NSD(a, b) = 1 Definice 2 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 NSD(a, b) > 1. Definice 1. a 2. lze rozšířit na libovolný konečný počet přirozených čísel. Čísla po dvou nesoudělná. NEJMENŠÍ SPOLEČNÝ NÁSOBEK Definice 3 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. Definice 4. 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. Zapisujeme NSN(a, b). Poznámka: 1. V množině přirozených čísel lze těž říci, že NSN(a, b) je nejmenší číslo z kladných společných násobků čísel a,b. 2. Definice 3. a 4. lze rozšířit na libovolný konečný počet přirozených čísel a[1], …, a[n]. Nejmenší společný násobek čísel a, b můžeme určit různými způsoby: d) využitím definice, e) pomocí vztahu mezi NSN(a, b) a NSD(a, b) f) pomocí rozkladu daných čísel na součin prvočinitelů Věta 7. Pro každá dvě přirozená čísla a, b platí a . b = NSN(a, b) . NSD(a, b). Poznámka: Větu 7. nelze rozšířit na více než dvě přirozená čísla. ROZKLAD PŘIROZENÉHO ČÍSLA NA SOUČIN PRVOČIITELů - UŽITÍ 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 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. ad a) 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ě. Příklad: Zjistěte NSD(108, 90) a NSN(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 8: Je-li 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: (a) = (e[1] + 1).(e[2] + 1). … .(e[k] + 1) 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. 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í: 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 648 = 2^3 . 3^4 (648) = (3+1) . (4+1) = 20 Číslo 648 má 20 přirozených dělitelů. 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. NEURČITÉ ROVNICE 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 5 Lineární neurčitá rovnice o dvou neznámých x, y je rovnice a . x + b . y = c, a ¹ 0, b ¹ 0 . Poznámka. - Jsou-li koeficienty a, b, c racionální necelá čísla, vynásobíme rovnici vhodným číslem tak, aby nabyly celočíselných hodnot. - Neurčité rovnice se nazývají též diofantické , podle řeckého matematika Diofanta z Alexandrie, 3. století př.n.l., který se zabýval řešením těchto rovnic. Ř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í. Ř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.