Vybrané kapitoly z algebry Jaroslav Beránek Brno 2011 Obsah 1. Přirozená čísla ......................................................................................... 4 2. Celá čísla .................................................................................................. 9 3. Racionální čísla ....................................................................................... 13 4. Reálná čísla ............................................................................................. 17 5. Komplexní čísla ...................................................................................... 24 6. Cyklické grupy ....................................................................................... 27 7. Faktorové struktury ............................................................................... 29 8. Svazy a Booleovy algebry ....................................................................... 32 9. Číselné soustavy ...................................................................................... 34 10. Základní pojmy a tvrzení z teorie dělitelnosti ...................................... 38 11. Polynomy .................................................................................................. 51 12. Rozklady polynomů, algebraické rovnice a jejich řešení .................... 62 13. Literatura ................................................................................................ 70 Úvod Tento text je určen pro studenty pedagogického asistentství matematiky pro základní školy. Jedná se o přehledný studijní materiál doplňující základní studijní literaturu v disciplíně Algebra 3. Jelikož se jedná o text doplňující a osvětlující základní studijní literaturu ([2], [5], [6], [12], [15], [16] ), nejsou v tomto textu v zájmu zachování lepší čtivosti a plynulosti textu uváděny důkazy jednotlivých tvrzení. Všechny důkazy lze nalézt ve studijní literatuře. Text je psán pro přehlednost velmi stručně a často se (na rozdíl od základní studijní literatury) omezuje pouze na případy, s nimiž se může student v praxi setkat (např. kapitola o polynomech je omezena pouze na polynomy nad tělesem reálných čísel). Pro studium textu je nutno předpokládat znalosti základů algebry (množinové operace a jejich vlastnosti, binární relace a jejich vlastnosti, relace uspořádání a uspořádané množiny, relace ekvivalence a rozklad množiny, binární algebraické operace a jejich vlastnosti, algebraické struktury a jejich homomorfismy). Standardní je rovněž označení základních číselných množin: N – množina všech přirozených čísel (samozřejmě včetně čísla nula) Z – množina všech celých čísel Q – množina všech racionálních čísel R – množina všech reálných čísel C – množina všech komplexních čísel. U množin Z, Q, R budeme v případě potřeby užívat i označení Z^+, Q^+, R^+ a Z^-, Q^-, R^- , označující podmnožinu všech kladných, resp. záporných čísel daného číselného oboru. Bude-li do této podmnožiny zařazena i nula, doplníme označení indexem nula, např. . 1. Přirozená čísla Jednou ze základních charakteristik množiny všech přirozených čísel je to, že každé přirozené číslo má svého bezprostředního následovníka (pro každé nÎ N je to číslo n + 1). Tento „fakt“ znají už žáci na 1. stupni ZŠ a je často didakticky využíván při výuce. Existence následovníka využijeme při teoretickém zavedení množiny přirozených čísel. Nejprve axiomaticky definujeme tzv. Peanovu množinu a potom ukážeme, že tato množina je univerzálním modelem množiny všech přirozených čísel. Poznamenejme ještě, že většinu důkazů v částech 1 - 5 lze nalézt v publikacích [12], resp. [2], z nichž je převzata i podstatná část textu. Axiomy Peanovy množiny P^ (A1) Ke každému prvku x množiny P existuje jeho následovník, který budeme označovat x^\ . (A2) V množině P existuje prvek eÎ P, který není následovníkem žádného prvku množiny P. (A3) Různé prvky mají různé následovníky. (A4) Axiom úplné indukce. Nechť M Í P. Jestliže platí: a) eÎ M , b) (" xÎ P) xÎ M Þ x^\ Î M , pak M = P. Věta 1.1. Nechť xÎ P, pak platí: (1) x ¹ x^\ , (2) x ¹ e Þ ($ uÎ P) x = u^\. Část (1) předchozí věty říká, že každý prvek je různý od svého následovníka. Ze druhé části pak plyne, že každý prvek x Peanovy množiny s výjimkou prvku e je následovníkem nějakého prvku uÎ P. Tento prvek u budeme nazývat předchůdce prvku x a značit ^/x. Věta 1.2. Peanova množina je nekonečná množina. Definice 1.3: Nechť aÎ P je libovolný prvek. Nechť množina U(a) Í P je pro každý prvek aÎ P definována takto: (1) aÎ U(a), (2) xÎ U(a) Þ ^/xÎ U(a) (pokud ^/x existuje). Pak množinu U(a) budeme nazývat úsek Peanovy množiny příslušný k prvku a . Poznámka 1.4. Je zřejmé, že pro každé aÎ P je příslušný úsek U(a) konečná množina. Poznámka 1.5. Z předchozího plyne, že Peanovu množinu můžeme považovat za teoretický model množiny přirozených čísel. V tomto případě prvek e je roven číslu 1, následovník x^\ je roven číslu x + 1 a modely úseků příslušných ke každému přirozenému číslu chápanému jako prvek množiny P si lze představit takto: U(1) = {1}, U(2) = {1, 2}, U(3) = {1, 2, 3}, U(4) = {1, 2, 3, 4} atd. Je zřejmé, že počet prvků každého úseku je určen přirozeným číslem, jemuž daný úsek přísluší. Proto i v dalším textu je možné představit si porovnávání prvků Peanovy množiny (relaci uspořádání v množině P) a následně i operace sčítání a násobení v množině P pomocí množiny přirozených čísel. I když teoretický postup je opačný (z obecné teorie v množině P plynou speciální vlastnosti v množině přirozených čísel), je pro pochopení podstaty vhodné už na tomto místě využít množiny přirozených čísel jako modelu Peanovy množiny P. Poznamenejme dále, že existuje i možnost vybudovat axiomaticky Peanovu množinu tak, že prvek e je roven číslu 0 (viz např. [2]). V tom případě je samozřejmě nutné všechny definice a tvrzení přeformulovat. Protože ale číslo nula není prvkem množiny přirozených čísel, budeme se držet běžnější verze, v níž prvek e je roven číslu 1. Relace uspořádání v množině P Definice 1.6: Nechť a, b Î P. Pak platí: a £ b Û a Î U(b) . Poznámka 1.7. Je zřejmé, že relace £ z definice 1.6. je reflexivní, antisymetrická a tranzitivní, jedná se tedy skutečně o uspořádání v množině P. Pro každé dva různé prvky a, b množiny P vždy platí právě jeden ze vztahů aÎ U(b), bÎ U(a), proto je uspořádání £ lineární. Hasseovským diagramem lineárně uspořádané množiny (P, £ ) je řetězec s nejmenším prvkem e. Dále poznamenejme, že zápis a < b označuje tzv. ostré uspořádání, tedy a £ b a současně a ¹ b. Věta 1.8. Nechť a, b Î P. Pak platí: (1) (" a Î P) a < a^\; (2) Mezi prvky a, a^\ neexistuje žádný prvek x množiny P s vlastností a < x < a^\ ; (3) Množina (P, £ ) je dobře uspořádaná množina. Operace sčítání v množině P Věta 1.9. Na množině P existuje právě jedna operace + taková, že pro každou dvojici x, y prvků množiny P platí: (1) x + e = x^\ , (2) x + y^\ = (x + y)^\ . Definice 1.10. Operace + z předchozí věty se nazývá operace sčítání v množině P . Věta 1.11. Operace + je v množině P asociativní a komutativní. Věta 1.12. V grupoidu (P, +) platí zákony o odečítání, tj. pro každé tři prvky x, y, z množiny P platí implikace x + y = x + z Þ y = z . Věta 1.13. Nechť x, y Î P. Pak nastane právě jeden z následujících tří případů: (1) x = y , (2) existuje p Î P s vlastností x = y + p , (3) existuje q Î P s vlastností y = x + q . Operace sčítání je spojena s relací uspořádání řadou vztahů. Některé z nich jsou uvedeny v následující větě. Věta 1.14. Nechť x, y, z, u, v Î P. Pak platí: (1) x < y Û x + z < y + z , (2) x £ y Û x + z £ y + z , (3) x £ y, u £ v Þ x + u £ y + v, (4) x < y Þ x^\ £ y . Operace násobení v množině P Věta 1.15. Na množině P existuje právě jedna operace × taková, že pro každou dvojici x, y prvků množiny P platí: (1) x × e = x , (2) x × y^\ = x × y + x . Definice 1.16. Operace × z předchozí věty se nazývá operace násobení v množině P . Poznámka 1.17. Pokud v zápise početních operací v množině P nepoužijeme závorky, má operace násobení přednost před operací sčítání. Rovněž se v zápisech velmi často vynechává označení × operace násobení, tj. místo x × y píšeme jenom xy. Věta 1.18. Operace × je v množině P asociativní, komutativní, má neutrální prvek (prvek e) a s operací sčítání je svázána distributivním zákonem: x, y, z Î P: x × (y + z) = x × y + x × z . Operace násobení je spojena s relací uspořádání řadou vztahů. Některé z nich jsou uvedeny v následující větě (zajímavá je analogie s obdobnými vztahy pro sčítání). Poznamenejme ještě, že tvrzení (3) následující věty říká, že v grupoidu (P, ×) platí zákony o krácení. Věta 1.19. Nechť x, y, z, u, v Î P. Pak platí: (1) x < y Û x × z < y × z , (2) x £ y Û x × z £ y × z , (3) x × z = y × z Þ x = y (4) x £ y, u £ v Þ x × u £ y × v. Důsledek 1.20. Algebraická struktura (P, +, ×) je komutativní polookruh s jedničkou. Poznámka 1.21. Z definice množiny P a popsaných vlastností relace uspořádání a operací sčítání a násobení v této množině vyplývá, že polookruh všech přirozených čísel (N, +, ×) je jedním z možných modelů polookruhu (P, +, ×). Roli prvku e hraje číslo 1, následovníkem čísla x je číslo x + 1, úsek množiny N příslušný číslu n obsahuje všechna přirozená čísla od čísla 1 po číslo n atd. Poznámka 1.22. Jako problémová se jeví otázka, kolik modelů polookruhu (P, +, ×) existuje, tzn. zda jsou přirozená čísla určena jednoznačně, resp. zda vůbec nějaký model množiny P existuje. Existenci modelu množiny P a tím i existenci přirozených čísel lze snadno ukázat; jde o kardinální čísla konečných množin. Těm se budeme věnovat v dalším textu. Odpovědí na otázku počtu modelů Peanovy množiny je tvrzení, že těchto modelů je nekonečně mnoho, všechny jsou ale navzájem izomorfní. Proto lze tvrdit, že přirozená čísla lze definovat až na izomorfismus jediným možným způsobem. Důležitou větu o tomto izomorfismu nyní uvedeme: Věta 1.23. (O jednoznačnosti přirozených čísel) Nechť N[1], N[2 ]jsou dvě množiny přirozených čísel (dva modely Peanovy množiny). Pak existuje právě jedna bijekce f: N[1] ® N[2] s vlastností " x Î N[1] : f ( x^\ ) = [ f(x)] ^\ . Přirozená čísla jako kardinální čísla konečných množin V této části se omezíme pouze na konečné množiny. I když v obecné teorii množin jsou studována i kardinální čísla nekonečných množin, pro účely konstrukce oboru všech přirozených čísel se nekonečnými množinami nemusíme zabývat. Víme, že dvě množiny jsou ekvivalentní, jestliže existuje bijekce (vzájemně jednoznačné zobrazení) jedné na druhou. Tato relace ekvivalence na systému všech konečných množin ℳ (označujeme ji ∼) je ekvivalencí v relačním smyslu (zřejmě je reflexivní, symetrická a tranzitivní). Proto generuje jednoznačným způsobem rozklad ℳ|[∼] na systému všech konečných množin ℳ. Třídy rozkladu ℳ|[∼ ]se nazývají kardinální čísla. Kardinálním číslem konečné množiny M tedy rozumíme třídu rozkladu ℳ|[∼], která obsahuje množinu M. Místo označení kardinální číslo množiny M se často užívá též pojmu mohutnost množiny M (píšeme card M). Nyní definujeme přirozená čísla jako kardinální čísla konečných množin. Popíšeme-li výše uvedenou konstrukci populárně (a matematicky ne zcela přesně), pak kardinální číslo konečné množiny M je systém množin, který kromě dané množiny M obsahuje všechny množiny (nekonečně mnoho), které mají tentýž počet prvků jako množina M. Tato jediná společná vlastnost všech těchto množin, tj. stejný počet prvků, je vyjádřena přirozeným číslem, které je kardinálním číslem množiny M definováno. Ve školské matematice na ZŠ proto říkáme, že přirozená čísla vyjadřují počty prvků konečných množin. Přechod od struktury (P, +, ×) k jejímu modelu (N, +, ×) lze popsat takto: Nechť n Î P je libovolný prvek Peanovy množiny. Úsek množiny P příslušný k prvku n je množina U(n) = {e, e^\, e^\\, e^\\\, ... , ^/n, n}. Tato množina je konečná, proto jistě náleží do některé třídy rozkladu ℳ|[∼]. Tato třída rozkladu je kardinálním číslem konečné množiny U(n) a odpovídající přirozené číslo je číslo n. Lze tedy tvrdit, že úsek U(n) obsahuje právě n prvků. Odtud prvku e odpovídá číslo 1, prvku e^\ číslo 2, prvku e^\\ číslo 3 atd. Přirozené uspořádání množiny přirozených čísel lze pak definovat ve shodě s definicí porovnávání prvků Peanovy množiny (každé číslo náležející do U(n) je menší nebo rovno číslu n). Jiná situace je u definice obou základních operací sčítání a násobení. I když lze tyto operace definovat stejným způsobem jako v abstraktní Peanově množině, z metodických důvodů se obě operace zavádějí odlišně, na základě množinových operací. Definice 1.24. (Sčítání kardinálních čísel) Nechť A, B jsou konečné množiny, nechť platí A Ç B = . Pak definujeme card A + card B = card (A È B) . Definice 1.25. (Násobení kardinálních čísel) Nechť A, B jsou konečné množiny. Pak definujeme card A × card B = card (A ´ B) . Poznámka 1.26. Lze ukázat, že obě operace definované definicemi 1.24. a 1.25. mají všechny vlastnosti, které očekáváme od operací sčítání a násobení přirozených čísel. Povšimněme si nyní omezující podmínky A Ç B = v definici 1.24. V případě jejího vypuštění bude pro součet kardinálních čísel množin A, B platit vztah card A + card B ³ card (A È B) , přičemž číslo na levé straně této neostré nerovnosti je obecně větší než číslo na pravé straně o počet prvků průniku obou množin. Platí tedy rovnost card A + card B - card (A Ç B) = card (A È B) . Z teoretického hlediska se jedná o princip inkluze a exkluze pro n = 2. Pokud jsou tedy množiny A, B disjunktní, pak card (A Ç B) = 0 a předchozí rovnost přejde v definici sčítání kardinálních čísel podle definice 1.24. 2. Celá čísla Obecná teorie Definice 2.1. Nechť (G, ×), (H, ×) jsou grupoidy (dále budeme k označení grupoidů užívat pouze symbol nosné množiny). Řekneme, že grupoid G lze vnořit do grupoidu H, jestliže existuje injektivní homomorfismus f grupoidu G do grupoidu H. Věta 2.2. Nechť G je komutativní grupoid. Pak jsou následující výroky ekvivalentní: (1) Grupoid G je asociativní a platí v něm zákony o krácení. (2) Grupoid G lze vnořit do nějaké grupy. Poznámka 2.3. Důkaz této věty je konstruktivní, obsahuje konstrukci tzv. podílové grupy G grupoidu G. Tuto konstrukci nyní popíšeme: Vyjdeme z kartézského součinu G ´ G. Nechť na G ´ G je definována binární relace ∼ definovaná takto: [a, b] ∼ [c, d] Þ a × d = b × c pro každé dvě dvojice z G ´ G. (1) Tato relace ∼ je ekvivalence, existuje tedy rozklad G ´ G |[∼] . Množinu tříd rozkladu G ´ G |[∼ ]označme G. Na množinovém systému G definujme nyní binární operaci o následujícím způsobem. Nechť [a, b], [c, d] jsou reprezentanti dvou tříd systému G . Pak platí [a, b] o [c, d] = [a × c, b × d]. (2) Grupoid (G, o) je faktoroidem grupoidu (G, ×). Lze dokázat, že algebraická struktura (G, o) je dokonce grupa. Tato grupa se nazývá podílová grupa grupoidu (G, ×). Vnoření y : G ® G grupoidu G do grupy G je definováno pro každý prvek g Î G předpisem y (g) = {[g × x, x]; xÎ G}. (3) Je-li místo multiplikativního označení (operace × ) užito označení aditivního (operace +), pak definiční vztahy (1), (2), (3) přejdou do tvaru: [a, b] ∼ [c, d] Þ a + d = b + c pro každé dvě dvojice z G ´ G , (4) [a, b] o [c, d] = [a + c, b + d] , (5) y (g) = {[g + x, x]; xÎ G}. (6) Místo označení podílová grupa pak říkáme rozdílová grupa. Celá čísla Definice 2.4. Rozdílová grupa pologrupy (N, +) se nazývá aditivní grupa celých čísel (Z, +). Poznámka 2.5. Při konstrukci grupy (Z, +) postupujeme podle obecné konstrukce. Výchozím kartézským součinem je N ´ N, relace ∼ je definována vztahem (4) pro G = N; operace o, kterou budeme označovat symbolem +, tj. stejně jako sčítání čísel přirozených (zřejmě nebude docházet k nedorozumění), je pak definována pomocí vztahu (5), tedy [a, b] + [c, d] = [a + c, b + d]. (7) Celá čísla jsou podle této konstrukce třídami rozkladu N ´ N |[∼] . Vnoření y : N ® Z grupoidu N do grupy Z je definováno analogicky jako v (6), tedy pro každý prvek n Î N předpisem y (n) = {[n + x, x]; xÎ N}. Poznámka 2.6. V dalším textu o celých číslech je nutno rozlišovat mezi případem, kdy [a, b] bude označovat tuto jednu konkrétní uspořádanou dvojici přirozených čísel a případem, kdy bude hrát roli reprezentující dvojice nějakého celého čísla. V tomto druhém případě budeme užívat tučného označení [a, b]. Platí tedy např. [4, 2] = {[3, 1], [4, 2], [5, 3], [6, 4], ...}. Celé číslo je vždy reprezentováno nekonečnou množinou navzájem ekvivalentních uspořádaných dvojic přirozených čísel. Podle dohodnutého označení je nutno také rozlišovat následující vztahy: Např. pro uspořádané dvojice [5, 3], [6, 4] platí [5, 3] ¹ [6, 4], [5, 3] ∼ [6, 4], pro dvě celá čísla [5, 3], [6, 4] ale platí rovnost [5, 3] = [6, 4], protože obě tyto dvojice jsou reprezentanty téže třídy rozkladu systému N ´ N |[∼]. Poznamenejme, že v dalším textu budeme pro zjednodušení označovat celá čísla velkými tučnými písmeny, např. A, B, .... Toto označení není v rozporu s uvedenou konstrukcí; vždy lze přejít k reprezentaci pomocí uspořádaných dvojic, např. A = [a[1], a[2]], B = [b[1], b[2]], .... Operace s celými čísly a jejich vlastnosti Poznámka 2.7. Sčítání celých čísel je, jak již bylo zmíněno v poznámce 2.2., definováno předpisem [a, b] + [c, d] = [a + c, b + d]. Věta 2.8. Operace + z předchozí poznámky 2.7. je komutativní, asociativní, má neutrální prvek 0 reprezentovaný dvojicí [n, n] pro libovolné nÎ N a ke každému celému číslu A = [a, b] existuje právě jedno opačné číslo -A = [b, a]. Věta 2.9. Algebraická struktura (Z, +) je komutativní grupa, ve které platí zákony o dělení, tj rovnice A + X = B má vždy řešení v množině Z pro každá dvě celá čísla A, B. Důsledek 2.10. V grupě (Z, +) platí zákony o krácení (v aditivní symbolice zákony o odečítání) a existuje právě jedna inverzní operace k operaci sčítání. Tato operace se nazývá odčítání a je definována vztahem A - B = A + (-B). Poznámka 2.11. Z předchozí věty a věty 2.1. lze odvodit početní pravidlo pro operaci odčítání: [a, b] - [c, d] = [a + d, b + c]. Povšimněme si, že v definici odčítání vystupují na pravé straně pouze součty přirozených čísel, tzn. operace odčítání je neomezeně definovaná a tedy algebraická struktura (Z, -) je grupoid. Tento grupoid není pologrupou, protože operace odčítání zřejmě není asociativní ani komutativní. Definice 2.12. Na množině Z definujme binární operaci × následujícím způsobem: [a, b] × [c, d] = [ac + bd, ad + bc]. Tuto operaci nazveme násobením v množině celých čísel. Tato operace je v množině Z neomezeně definovaná, struktura (Z, ×) je tedy grupoid. Věta 2.13. Grupoid (Z, ×) je asociativní, komutativní a má neutrální prvek 1 reprezentovaný dvojicí [n+1, n] pro libovolné nÎ N . Věta 2.14. V grupoidu (Z, ×) platí omezený zákon o krácení, tzn. pro každá tři celá čísla x, y, z, x¹ 0 platí implikace x × y = x × z Þ y = z . Věta 2.15. Operace násobení je v množině celých čísel svázána s operací sčítání distributivním zákonem, tj. A, B, C Î Z: A × (B + C) = A × B + A × C. Důsledek 2.16. Algebraická struktura (Z,+,×) je komutativní okruh s jedničkou charakteristiky nula, který není tělesem. V tomto okruhu neexistují vlastní dělitelé nuly, je to tedy obor integrity. Poznámka 2.17. V oboru integrity všech celých čísel (Z, +, ×) platí řada tvrzení, běžně užívaných při výpočtech. Uveďme některé příklady. Věta 2.18. Nechť A, B, C Î Z. Pak platí: (1) -(-A) = A; (2) -(A + B) = (-A) + (-B); (3) -(A - B) = B - A; (4) (A - (B - C) = (A + C) - B; (5) (-A) × B = A × (-B) = -(A × B). Relace uspořádání v množině celých čísel Definice 2.19. Nechť A = [a, b] je celé číslo. Řekneme, že toto číslo je kladné a píšeme A > 0, právě když platí a > b. Je-li a = b, pak číslo A = 0 ; ve zbývajícím případě pro a < b říkáme, že celé číslo A je záporné a píšeme A < 0. Poznámka 2.20. Je zřejmé, že jeden z předchozích případů vždy musí nastat. Každé celé číslo je tedy buďto kladné nebo záporné nebo je rovno nule. Existuje tedy rozklad množiny všech celých čísel na čísla kladná, nulu a čísla záporná. Ve shodě s běžnou terminologií zavádíme i označení A £ 0 a říkáme, že číslo A je nekladné, resp. v případě A ³ 0 je toto číslo nezáporné. Definice 2.21. Nechť A, B jsou celá čísla. Řekneme, že A < B, právě když platí A - B < 0. Je-li A - B = 0, pak A = B ; ve zbývajícím případě pro A - B > 0 pak platí A > B. Poznámka 2.22. Je zřejmé, že i v předchozí definici jeden z případů vždy musí nastat. Relace uspořádání všech celých čísel je tedy lineární. I zde se běžně užívá i neostrá nerovnost A £ B pro případ A - B £ 0 a analogicky A ³ B pro případ A - B ³ 0. Věta 2.23. Nechť A je celé číslo. Pak platí: (1) A > 0 Þ -A < 0. (2) A < 0 Þ -A > 0. Věta 2.24. Nechť A, B jsou kladná celá čísla. Potom jejich součet A + B i součin A × B jsou také kladná celá čísla. Poznámka 2.25. Výše definovaná relace uspořádání v množině všech celých čísel je spojena s operacemi v této množině řadou vztahů. Uveďme alespoň některé. Věta 2.26. Nechť A, B, C, D jsou libovolná celá čísla. Pak platí: (1) Jestliže A > B a C < 0, potom AC < BC; (2) Jestliže A + C > B + C, potom A > B; (3) Jestliže AC > BC a C > 0, potom A > B; (4) Jestliže AC > BC a C < 0, potom A < B; (5) Jestliže A > B a C > D, potom A + C > B + D; (6) Jestliže A > B a C > D a C > 0 a B > 0, potom A × C > B × D . Věta 2.27. Nechť A, B jsou libovolná celá čísla, přičemž B ¹ 0. Pak existuje jednoznačně určená dvojice celých čísel Q, R (přičemž 0 £ R < çBç) s vlastností A = B × Q + R. Číslo A se nazývá dělenec, číslo B dělitel, číslo Q je podíl (někdy též neúplný podíl) a číslo R je zbytek. Proces nalezení čísel Q, R se nazývá dělení se zbytkem v množině celých čísel. Definice 2.28. Absolutní hodnotu çAç celého čísla A definujeme takto: (1) Je-li A ³ 0, pak çAç = A ; (2) Je-li A < 0, pak çAç = -A. Věta 2.29. Nechť A, B jsou libovolná celá čísla, pak platí: (1) çAç = ç-Aç; (2) A £ çAç; (3) çAç^2 = A^2; (4) çA × Bç = çAç× çBç; (5) çA + Bç £ çAç+ çBç; (6) çA - Bç ³ çAç- çBç. Poznámka 2.30. Vnoření y : N ® Z grupoidu N do grupy Z je definováno podle poznámky 2.2. pro každý prvek n Î N předpisem y (n) = {[n + x, x]; xÎ N}. Každé celé kladné (tj. přirozené) číslo n je tedy reprezentováno dvojicí [n + x, x], číslo nula je reprezentováno dvojicí [x, x] a každé celé záporné číslo -n je reprezentováno dvojicí [x, n + x]. 3. Racionální čísla Obecná teorie Definice 3.1. Nechť R = (R, +, ×), S = (S, +, ×) jsou okruhy. Řekneme, že okruh R lze vnořit do okruhu S, jestliže existuje injektivní homomorfismus f okruhu R do okruhu S. Věta 3.2. Nechť (R, +, ×) je komutativní okruh. Pak jsou následující výroky ekvivalentní: (1) V okruhu (R, +, ×) platí omezený zákon o krácení, tzn. "x, y, z Î R, x¹ 0: x × y = x × z Þ y = z . (2) Okruh R lze vnořit do tělesa. Poznámka 3.3. Důkaz této věty je konstruktivní, obsahuje konstrukci tzv. podílového tělesa T okruhu R. Tuto konstrukci nyní popíšeme: Vyjdeme z kartézského součinu R ´ R- {0}, který označíme M a budeme nazývat množina všech zlomků okruhu R. Nechť na M je definována binární relace ∼ definovaná takto: [a, b] ∼ [c, d] Þ a × d = b × c pro každé dvě dvojice z množiny M. (8) Tato relace ∼ je ekvivalence na M, existuje tedy rozklad M |[∼] . Množinu tříd rozkladu M |[∼ ]označme T. Na množinovém systému T definujme nyní binární operace sčítání a násobení následujícím způsobem. Nechť [a, b], [c, d] jsou reprezentanti dvou tříd systému T . Pak platí [a, b] + [c, d] = [ad + bc, bd], [a, b] × [c, d] = [ac, bd] (9) Lze dokázat, že algebraická struktura (T, +, ×) je těleso. Toto těleso se nazývá podílové těleso okruhu R. Nulou tohoto tělesa je třída {[0, r]; rÎ R}, jedničkou třída {[r, r]; rÎ R}. Vnoření y : R ® T okruhu R do tělesa T je definováno pro každý prvek r Î R předpisem y (r) = {[r × x, x]; xÎ R}. (10) Racionální čísla Definice 3.4. Podílové těleso okruhu (Z, +, ×) se nazývá těleso racionálních čísel (Q, +, ×). Poznámka 3.5. Při konstrukci tělesa (Q,+,×) postupujeme podle obecné konstrukce. Výchozím kartézským součinem je M = Z ´ Z- {0}, relace ∼ je definována vztahem (8) pro R = Z. Protože se podle obecné teorie jedná o zlomky, budeme uspořádané dvojice z množiny M zapisovat jako zlomky, tedy místo [a, b] budeme psát . Odtud je také zřejmé, proč se v množině M pro druhé složky všech dvojic nepřipouští číslo nula. Operace sčítání a násobení jsou definovány vztahy (9); po vyjádření pomocí zlomků tedy , . Racionální čísla jsou podle této konstrukce třídami rozkladu M |[∼] . Vnoření y : Z ® Q okruhu Z do tělesa Q je definováno analogicky jako v (10), tedy pro každý prvek z Î Z předpisem y (z) = { ; xÎ Z- {0}}. Analogicky jako u celých čísel budeme rozlišovat jeden konkrétní zlomek od racionálního čísla. Tučným označením budeme označovat stav, kdy tento zlomek bude reprezentovat racionální číslo, zatímco běžným způsobem budeme označovat tento jeden konkrétní zlomek. Platí tedy např. = { }. Poznamenejme, že v dalším textu budeme pro zjednodušení označovat racionální čísla velkými tučnými písmeny, např. A, B, .... Toto označení není, tak jako u celých čísel, v rozporu s uvedenou konstrukcí; vždy lze přejít k reprezentaci pomocí uspořádaných dvojic, např. A = , B = , .... Obě operace sčítání a násobení lze pak užitím tohoto označení psát jako , . Věta 3.6. Operace sčítání v množině všech racionálních čísel je komutativní, asociativní, má neutrální prvek, ke každému racionálnímu číslu existuje právě jedno číslo opačné a platí zákony o dělení. Algebraická struktura (Q, +) je tedy komutativní grupa. Poznámka 3.7. V grupě (Q, +) platí analogické vlastnosti a vztahy jako v grupě (Z, +), není tedy nutné je na tomto místě znovu uvádět. Poznamenejme jen, že neutrálním prvkem je číslo 0 reprezentované třídou a opačným racionálním číslem k číslu je číslo - , které lze reprezentovat buďto třídou nebo třídou . Poznámka 3.8. Analogicky jako pro celá čísla lze zavést operaci odčítání jako přičtení opačného prvku, tedy A - B = A + (-B). Takto lze snadno odvodit běžně užívaný vztah pro odčítání zlomků: . Poznámka 3.9. Operace odčítání má v množině všech racionálních čísel tytéž vlastnosti jako v množině celých čísel (tj. není komutativní ani asociativní). Poznámka 3.10. Nyní se budeme věnovat operaci násobení v množině všech racionálních čísel. Připomeneme definici: . Věta 3.11. Operace násobení v množině Q je komutativní, asociativní a má neutrální prvek. Tímto neutrálním prvkem je číslo 1 reprezentované třídou zlomků . Algebraická struktura (Q, ×) je komutativní monoid. Operace násobení je distributivní vzhledem k operaci sčítání v množině všech racionálních čísel. Poznámka 3.12. Budeme-li zkoumat i existenci inverzních prvků a platnost zákonů o dělení vzhledem k operaci násobení v množině Q, snadno zjistíme, že jediným prvkem, který neumožňuje obecnou platnost těchto vlastností, je číslo 0. Po jeho odstranění z množiny Q můžeme vyslovit následující větu. Věta 3.13. (1) Algebraická struktura (Q - {0}, ×) je komutativní grupa. (2) Algebraická struktura (Q ,+, ×) je komutativní těleso. Poznámka 3.14. Inverzním prvkem k racionálnímu číslu je číslo (předpokládáme, že a ¹ 0 ). Toto číslo vždy jednoznačně existuje (b ¹ 0 podle konstrukce racionálních čísel a a ¹ 0 podle předpokladu), nazývá se převrácené číslo k číslu a označuje . Při označení racionálního čísla A se převrácené číslo kromě zápisu A^-^1 zapisuje též . V množině Q - {0} jsme nyní připraveni k definici operace dělení. Definice 3.15. Dělení v množině Q - {0} je definováno jako násobení převráceným číslem, tj. A : B = A × B^-^1 . Vyjádřeno pomocí definice operace násobení a převráceného čísla dostáváme . Poznámka 3.16. Připomeňme znovu, že existence převráceného čísla i operace dělení jsou neomezeně definovány v množině Q - {0}, tedy že skutečně nemůže dojít k „dělení nulou“. Pro operace dělení a násobení platí rovněž řada vlastností, z nichž uvedeme např.: Věta 3.17. Nechť A, B, C Î Q. Pak platí: (1) (A^-^1)^-^1 = A; (2) (A × B)^-^1 = A^-^1 × B^-^1; (3) (A × B^-^1)^-^1 = B × A^-^1; (4) (A × B^-^1) × C ^-^1 = A × (B × C)^-^1; (5) A × (B × C ^-^1)^-^1 = (A × C) × B^-^1. Relace uspořádání v množině racionálních čísel Definice 3.18. Nechť A = je racionální číslo. Řekneme, že toto číslo je kladné a píšeme A > 0, právě když platí a i b jsou buďto obě současně kladná celá čísla nebo obě současně záporná celá čísla. . Je-li a = 0, pak číslo A = 0 ; ve zbývajícím případě (jedno z čísel a, b je kladné celé číslo a jedno záporné) říkáme, že racionální číslo A je záporné a píšeme A < 0. Poznámka 3.19. Je zřejmé, že jeden z předchozích případů vždy musí nastat. Každé racionální číslo je tedy buďto kladné nebo záporné nebo je rovno nule. Existuje tedy rozklad množiny všech racionálních čísel na čísla kladná, nulu a čísla záporná. Ve shodě s běžnou terminologií zavádíme i označení A £ 0 a říkáme, že číslo A je nekladné, resp. v případě A ³ 0 je toto číslo nezáporné. Definice 3.20. Nechť A, B jsou racionální čísla. Řekneme, že A < B, právě když platí A - B < 0. Je-li A - B = 0, pak A = B ; ve zbývajícím případě pro A - B > 0 pak platí A > B. Poznámka 3.21. Je zřejmé, že i v předchozí definici jeden z případů vždy musí nastat. Relace uspořádání všech racionálních čísel je tedy lineární. I zde se běžně užívá i neostrá nerovnost A £ B pro případ A - B £ 0 a analogicky A ³ B pro případ A - B ³ 0. Poznámka 3.22. Pro relaci uspořádání v množině racionálních čísel a její spojení s operacemi v množině Q platí analogické vztahy jako v množině celých čísel, stejně je definována i absolutní hodnota racionálního čísla. Vzhledem k tomu, že (Q ,+, ×) je komutativní těleso, nemá smysl v množině racionálních čísel zavádět dělení se zbytkem. Platí však zajímavá vlastnost relace uspořádání racionálních čísel, která v množinách přirozených ani celých čísel nemá analogii. Definice 3.23. Uspořádání v množině racionálních čísel je husté (tj. (Q,< ) je hustě uspořádaná množina), jestliže platí " x, y Î Q, x ¹ y; $ zÎ Q: x < z < y . Poznámka 3.24. Definice hustého uspořádání říká, že „mezi každá dvě různá racionální čísla lze vložit další racionální číslo“. Z teorie uspořádaných množin z toho plyne, že uspořádaná množina Q nemá skoky. Vysvětlení této skutečnosti ponecháme na teorii konstrukce reálných čísel. Desetinné rozvoje racionálních čísel Poznámka 3.25. Je zřejmé, že racionální čísla nevyjadřujeme výlučně ve tvaru zlomku, např. velmi často se setkáváme s jejich vyjádřením pomocí desetinných rozvojů. Věta 3.26. Každé racionální číslo lze vyjádřit pomocí desetinného rozvoje, přičemž tento desetinný rozvoj je buďto ukončený nebo je periodický. Ukončený je právě tehdy, je-li dané racionální číslo tvaru , tj. obsahuje-li rozklad jeho jmenovatele na prvočinitele pouze prvočísla 2 nebo 5. Nástin důkazu. Při dělení čitatele zlomku jeho jmenovatelem mohou nastat pouze dvě možnosti. Buďto je zbytek od jistého kroku dělení roven nule, pak je desetinný rozvoj ukončený. Nenastane-li tento případ, je rozvoj neukončený. Protože však počet všech možných nenulových zbytků musí být menší než jmenovatel zlomku, musí se nutně od jistého kroku zbytky opakovat. Definice 3.27. Zlomek, jehož jmenovatel je roven některé mocnině čísla deset, se nazývá desetinný zlomek. Racionální číslo, jehož desetinný rozvoj je ukončený, se nazývá v rozvinutém tvaru desetinné číslo. Poznámka 3.28. Převod zápisu racionálního čísla ze zlomku na desetinný rozvoj provádíme dělením čitatele jmenovatelem; opačný převod buďto přechodem na desetinný zlomek a úpravou (v případě konečného rozvoje) nebo užitím součtu konvergentní geometrické řady. 4. Reálná čísla Poznámka 4.1. Protože (Q ,+, ×) je komutativní těleso, tzn. ze strukturálního hlediska „nejbohatší“ strukturou, nelze již provést její „zlepšení“. Proto konstrukce reálných čísel nemůže být provedena pomocí podílových struktur; lze dokázat, že konstrukcí podílového tělesa racionálních čísel nedostaneme již nic nového. Těleso reálných čísel musí být konstruováno na jiné bázi. K tomu lze využít uspořádaných množin; buďto teorii řezů pocházející od R. Dedekinda nebo teorii úplných metrických prostorů. Zde využijeme Dedekindových řezů. Nejprve opět základní přehled teorie. Obecná teorie Definice 4.2. Nechť (E, £ ) je lineárně uspořádaná množina. Dvojice a = (A, B), A Í E, B Í E se nazývá řez v množině E, jestliže platí: (1) A È B = E , A ¹ ∅, B ¹ ∅, (2) xÎ A Ù yÎ B Þ x< y, (3) A Ç B = ∅. Poznámka 4.3. Systém {A, B} tvoří tedy rozklad množiny E; množina A je dolní skupina řezu a a množina B je horní skupina řezu a . Poznámka 4.4. (Typy řezů). Nechť a = (A, B) je řez v množině E. Pak mohou nastat následující čtyři případy. Řez 1. druhu: Množina A obsahuje největší prvek a množina B neobsahuje nejmenší prvek; Řez 2. druhu: Množina A neobsahuje největší prvek a množina B obsahuje nejmenší prvek; Řez 3. druhu: Množina A neobsahuje největší prvek a množina B neobsahuje nejmenší prvek; Řez 4. druhu: Množina A obsahuje největší prvek a množina B obsahuje nejmenší prvek. Protože řezy 1. a 2. druhu popisují v podstatě tutéž situaci, budeme je v dalším textu ztotožňovat. Každá lineárně uspořádaná množina proto může mít pouze řezy 1., 3. a 4. druhu. Definice 4.5. Řez 3. druhu z poznámky 4.4. se nazývá mezera v lineárně uspořádané množině, řez 4. druhu z poznámky 4.4. se nazývá skok v lineárně uspořádané množině. Věta 4.6. Lineárně uspořádaná množina, která obsahuje alespoň dva prvky, je hustě uspořádaná, právě když nemá skoky. Příklady: a) řez 1. druhu: E = Q; A = {xÎ Q: x £ 1}, B = {xÎ Q: x > 1} ; b) řez 3. druhu: E = Q; A = {xÎ Q: x^2 < 2}, B = {xÎ Q: x^2 > 2} ; c) řez 4. druhu: E = Z; A = {xÎ Z: x £ 1}, B = {xÎ Z: x ³ 2} . Definice 4.7. Lineárně uspořádaná množina se nazývá spojitě uspořádaná, právě když nemá skoky ani mezery. Definice 4.8. Nechť (R, £ ), (S, £ ) jsou lineárně uspořádané množiny. Zobrazení f : R ® S se nazývá vnoření (R, £ ) do (S, £ ), jestliže platí: (1) f je injektivní; (2) " x, y Î R: x £ y Þ f(x) £ f(y). Někdy se pro toto zobrazení f užívá též označení izotonní zobrazení. Věta 4.9. Každou lineárně uspořádanou množinu lze vnořit do lineárně uspořádané množiny bez mezer. Věta 4.10. Nechť (R, £ ) je lineárně uspořádaná množina. Označme S množinu všech řezů 1. a 3. druhu v množině R. Nechť na S je definováno uspořádání takto: a =(A, B), b =(C, D), a, b Î S: a £ b Û A Í C. Pak S je lineárně uspořádaná množina, která neobsahuje mezery. Definice 4.11. Lineárně uspořádaná množina (S, £ ) z předchozí věty se nazývá normální obal lineárně uspořádané množiny (R, £ ). Poznámka 4.12. Ztotožníme-li prvky množiny R s řezy 1. druhu v R, pak normální obal množiny R se skládá z prvků množiny R a mezer v R. Označení 4.13. Nechť (E, £ ) je lineárně uspořádaná množina. Pro každý prvek m Î E budeme její podmnožinu {xÎ E: x £ m} označovat (m]. Věta 4.14. Nechť (R, £ ) je lineárně uspořádaná množina a nechť (S, £ ) je její normální obal. Uvažujme všechny řezy 1. druhu v množině R (podle poznámky 4.4. je každému prvku rÎ R přiřazen právě jeden řez 1. druhu, kde prvek r je největším prvkem dolní skupiny příslušného řezu). Označme a = (A, B) libovolný řez 1. druhu v množině R, nechť r Î R je největší prvek množiny A. Definujme nyní zobrazení f : R ® S takto: Pro každý prvek rÎ R nechť je jeho obrazem řez f(r) v množině S definovaný takto: f(r) = ( (r], R - (r] ). Pak zobrazení f : R ® S je vnoření (R, £ ) do (S, £ ). Reálná čísla Poznámka 4.15. Z teorie racionálních čísel víme, že (Q, < ) je lineárně uspořádaná množina, která nemá skoky (uspořádání je husté). Lze však snadno dokázat, že obsahuje mezery, např. je zcela jistě číslo, které není racionální (nelze ho vyjádřit pomocí zlomku). Věta 4.16. V lineárně uspořádané množině (Q, < ) existují pouze řezy 1. a 3. druhu. Řezy 1. druhu odpovídají racionálním číslům a řezy 3. druhu mezerám v uspořádané množině (Q, < ). Definice 4.17. Normální obal lineárně uspořádané množiny (Q, < ) je lineárně uspořádaná množina (R, < ). Podle věty 4.10. lineárně uspořádaná množina (R, < ) neobsahuje mezery, existují v ní tedy pouze řezy 1. druhu. Věta 4.18. (1) Lineárně uspořádaná množina (R, < ) je spojitě uspořádaná (neobsahuje mezery). (2) " x, y Î R, x < y; $ zÎ Q: x < z < y . Definice 4.19. V uspořádané množině (Q, < ) odpovídají řezy 1. druhu racionálním číslům a řezy 3. druhu (tj. mezery) odpovídají číslům iracionálním. Každá mezera v uspořádané množině (Q, < ) tedy určuje právě jedno iracionální číslo. Označíme-li množinu všech iracionálních čísel I , pak platí R = Q È I . Poznámka 4.20. Protože lineárně uspořádaná množina (R, < ) neobsahuje mezery, lze konstatovat, že každý bod číselné osy je obrazem právě jednoho reálného čísla a naopak, každé reálné číslo lze jednoznačně znázornit na číselné ose. Uvedené skutečnosti plynou i z axiomů spojitosti, známých z axiomatické teorie výstavby geometrie. Tyto axiomy jsou dva, Archimédův a Cantorův. Zejména Cantorův axiom, podle něhož průnik do sebe zařazených úseček je neprázdný, podstatně přispívá k představě obrazů reálných čísel na číselné ose. Uspořádání v množině reálných čísel Poznámka 4.21. Připomeňme, že reálná čísla jsou sjednocením racionálních řezů 1. a 3. druhu, tj. každé reálné číslo je racionálním řezem. V případě řezu 1. druhu jde o číslo racionální, v případě řezu 3. druhu jde o číslo iracionální. Definice 4.22. Nechť a =(A, B), b =(C, D) jsou řezy v množině Q (tj. dvě reálná čísla). Pak platí: a £ b Û A Í C . Definice 4.23. Nechť Q^+ = {rÎ Q: r > 0}, tj. Q^+ označuje množinu všech kladných racionálních čísel. Pak řez (Q - Q^+, Q^+) je reálné číslo, které označíme symbolem 0 a nazýváme nulou. Číslo a Î R je kladné, je-li a > 0, číslo a Î R je záporné, je-li a < 0. Operace v množině reálných čísel Definice 4.24. Nechť a = (A, B), b = (C, D) jsou libovolná reálná čísla. Položme nyní C[2] = {a + b ; a Î B, b Î D}, C[1] = Q - C[2]. Pak C = (C[1], C[2]) je reálné číslo, které nazveme součtem reálných čísel a, b a značíme a + b. Věta 4.25. Nechť a, b, c, jsou libovolná reálná čísla. Nechť platí a < b. Potom platí také nerovnost a + c < b + c . (Uspořádání reálných čísel je monotonní vzhledem ke sčítání). Věta 4.26. Operace sčítání je v množině všech reálných čísel komutativní, asociativní, má neutrální prvek a platí zákony o dělení (rovnice a + x = b má řešení pro libovolná reálná čísla a, b). Algebraická struktura (R, +) je komutativní grupa. Definice 4.27. Z předchozí věty plyne, že rovnice a + x = b má řešení pro libovolná reálná čísla a, b. Toto řešení píšeme ve tvaru x = b - a a nazveme rozdílem reálných čísel a, b. příslušná operace se nazývá odčítání reálných čísel. Definice 4.28. Nechť a = (A, B), b = (C, D) jsou libovolná reálná čísla. Položme nyní: C[2] = {a ×b ; a Î B, b Î D}, C[1] = Q - C[2]. Pak C = (C[1], C[2]) je reálné číslo, které nazveme součinem reálných čísel a, b a značíme a ×b. Věta 4.29. Nechť a, b, c, jsou libovolná reálná čísla. Pak platí: (1) (- a) × b = a × (- b) = - (a × b); (2) (- a) × (- b) = a × b ; (3) a × b = 0 právě tehdy, je-li a = 0 nebo b = 0. Věta 4.30. (1) Algebraická struktura (R - {0}, ×) je komutativní grupa. (2) Algebraická struktura (R ,+, ×) je komutativní těleso. Věta 4.31. (Věta o supremu a infimu) Nechť M je libovolná neprázdná podmnožina množiny reálných čísel. Pak platí: (1) Je-li M zdola ohraničená, existuje inf[R ]M ; (2) Je-li M shora ohraničená, existuje sup[R ]M. Věta 4.32. (Vnoření racionálních čísel do čísel reálných) Nechť a Î Q. Označme R[a ] = {xÎ R: x £ a}. Pak zobrazení f: Q ® R definované předpisem f(a) = (R[a ], R - R[a] ) je izomorfní vnoření lineárně uspořádané množiny Q do lineárně uspořádané množiny R. Poznámka 4.33. Z matematické analýzy jsou známy následující definice: (1) Posloupnost je cauchyovská, jestliže ke každému e > 0 existuje přirozené číslo n[0] s vlastností, že pro každou dvojici přirozených čísel m, n > n[0] platí < e . (2) Posloupnost je konvergentní s limitou L, jestliže ke každému e > 0 existuje přirozené číslo n[0] s vlastností, že pro každé přirozené číslo n > n[0] platí < e . Je zřejmé, že každá konvergentní posloupnost je cauchyovská, opak obecně neplatí. V metrickém prostoru R je ale každá cauchyovská posloupnost konvergentní, to znamená, že R je úplným metrickým prostorem. Této teorie úplných prostorů lze využít též ke konstrukci tělesa reálných čísel místo teorie řezů. Nyní následuje několik didaktických poznámek. Následující poznámka je převzata z publikace [4], s. 90 – 92. Poznámka 4.34. Již na střední škole se setkají studenti s důkazem, že číslo nelze vyjádřit ve tvaru zlomku, tzn. že kromě čísel racionálních existují ještě čísla iracionální, přičemž iracionálními čísly jsou téměř všechny odmocniny, hodnoty goniometrických funkcí, logaritmů atd. Studentům však většinou chybí názorná geometrická představa; velmi těžko odlišují pojmy mezera a skok na číselné ose. Tyto pojmy, známé již ze starověké matematiky, jsou přitom ke správnému pochopení reálných čísel nezbytné. Nyní uvedeme dva modely reálných čísel, aritmetický a geometrický. S oběma se setká již žák základní školy. Aritmetickým modelem je pro něj množina všech čísel, geometrickým modelem číselná osa. Izomorfismus obou modelů umožňuje nerozlišovat mezi číslem a jeho obrazem na číselné ose. Aritmetický model je častější, geometrický model je přitom názornější a pro zavádění reálných čísel na školách vhodnější. Množina R je: · uspořádaná , tj. pro každá dvě x, y Î R nastane právě jeden z případů x< y, x = y, x > y; · hustá, tj. " x, y Î R, x < y, $ z Î R: x < z < y; · archimedovská, tj. " x, y Î R, 0 < x < y, $ n Î N: x(n - 1) £ y < xn; · spojitá, tj. každá neprázdná shora ohraničená množina M Ì R má supremum. V geometrickém modelu lze předchozí čtyři tvrzení formulovat názorněji: · Jsou-li X, Y dva body na ose o, nastává právě jeden z případů: X = Y, X leží vlevo od Y, Y leží vlevo od X. · Mezi každými dvěma různými body existuje bod. · Jestliže B je vnitřním bodem úsečky AX a jestliže na polopřímce AX sestrojíme posloupnost bodů B[1] = B, B[2], B[3], ... tak, že postupně nanášíme úsečku AB (tedy úsečka AB[n] je n-násobek úsečky AB), pak po jistém počtu kroků překročíme bod X (bod X bude prvkem jisté úsečky B[k-1]B[k]). · Na číselné ose nejsou skoky (díry). Aritmetický model množiny R je méně přehledný, lze v něm však uskutečňovat všechny aritmetické operace a dobře rozlišovat mezi racionálním a iracionálním číslem. Od historie k dnešku Poznámka 4.35. Problém důkazu existence iracionálních čísel je velmi starý. Již v antickém Řecku se objevila tzv. první krize matematického myšlení, která se týkala „nesouměřitelnosti úseček“. V tehdejší matematice byla známá racionální čísla i to, že jakékoliv racionální číslo lze přesnou geometrickou konstrukcí zobrazit na číselné ose. Společně se znalostí hustoty uspořádání racionálních čísel byl tehdy všeobecně přijímán názor, že jiná čísla než racionální neexistují, že každé číslo lze vyjádřit zlomkem a že každý bod číselné osy je obrazem nějakého racionálního čísla. Objev faktu, že v jakémkoliv čtverci jsou jeho strana a úhlopříčka tzv. nesouměřitelné a že délku úhlopříčky nelze vyjádřit zlomkem (má-li strana čtverce délku a, má úhlopříčka délku a), způsobil v tehdejší době doslova pozdvižení, neboť nebylo známo, jak vzniklý problém vyřešit. Z teorie už víme, že princip nesouměřitelnosti znamená to, že lineárně uspořádaná množina racionálních čísel obsahuje mezery. Vyřešení problému nesouměřitelnosti, tj. zavedení iracionálních čísel, mohlo být úspěšně teoreticky ukončeno až mnohem později, po uznání aktuálního nekonečna v díle Bernarda Bolzana. Připomeneme nyní Cantorův axiom spojitosti, známý z geometrie. Podle něj je průnik do sebe zařazených úseček neprázdný. Po uznání aktuálního nekonečna a s tím souvisejícím zavedení limitních procesů do matematiky lze dokázat, že při nekonečném počtu do sebe zařazených úseček je průnikem pouze jednoprvková množina. Při nekonečném počtu do sebe zařazených úseček na číselné ose je tedy průnikem jediné číslo. Proto je možné iracionální číslo, které je mezerou na číselné ose (racionálním řezem 3. druhu), definovat jako průnik nekonečně mnoha do sebe zařazených úseček na číselné ose. Levé krajní body těchto úseček tvoří rostoucí shora ohraničenou posloupnost racionálních čísel, která proto musí mít limitu. Analogicky pravé krajní body tvoří klesající zdola ohraničenou posloupnost racionálních čísel, která musí mít rovněž limitu. Obě tyto limity se rovnají a jejich hodnota je hledané iracionální číslo. Uvedeme dva příklady: a) Nechť (A, B), A = {xÎ Q: x^2 < 2}, B = {xÎ Q: x^2 > 2} je řez třetího druhu v množině Q. Budeme postupně volit čísla z množiny A i B tak, aby čísla množiny A tvořila rostoucí posloupnost a čísla z množiny B klesající posloupnost. Tyto dvojice čísel budou krajními body vnořených intervalů, kterými budeme postupně stále přesněji aproximovat hodnotu zvolené mezery (řezu 3. druhu). 1^2 = 1; 2^2 = 4, tedy 1 < < 2 (1,4)^2 = 1,96; (1,5)^2 = 2,25 , tedy 1,4 < < 1,5 (1,41)^2 = 1,9881; (1,42)^2 = 2,0164 , tedy 1,41 < < 1,42 (1,414)^2 = 1,999396; (1,415)^2 = 2,002225 , tedy 1,414 < < 1,415 (1,4141)^2 = 1,99967881; (1,4143)^2 = 2,00024449 , tedy 1,4141 < < 1,4143 atd. Uvedený proces aproximace je nekonečný a číslo je tak postupně určováno se stále větší přesností. Při praktickém počítání v praxi se spokojíme s přesností, která postačuje k řešení daného matematického problému. b) Proces postupné aproximace iracionálního čísla lze i programovat. Příkladem může být přibližné určení čísla Eulerova čísla e. Víme, že 2 < e < 4 . Dále z matematické analýzy víme, že platí: = e, = e, přičemž první z těchto posloupností je rostoucí s prvním členem 2, druhá z těchto posloupností je klesající s prvním členem 4. Obecně tedy můžeme Eulerovo číslo aproximovat pro n Î N pomocí nerovností < e < . Závěrečné poznámky k reálným číslům A) Surdické výrazy Poznámka 4.36. Surdické výrazy jsou reálná čísla tvaru a , kde a, b jsou nezáporná racionální čísla, b není druhou mocninou žádného racionálního čísla. Jedná o velmi starou problematiku - vzorce pro úpravu surdických výrazů znal již ve 12. století indický matematik Bháskara. Pro úpravu surdických výrazů platí vztahy: (předpokládáme, že a > ³ 0) , . Pomocí uvedených dvou vztahů se některé výrazy s odmocninami téměř „zázračně“ upraví, např. výraz . Zde a = 3, b = 8, podle prvního ze vzorců je výsledek roven 2. Takto lze upravovat i odmocniny z vyšších čísel, např. = - 7, = 5 + , . Poznámka 4.37. Nyní se budeme věnovat úpravám výrazu X = . Pokud je racionální číslo, pak lze po umocnění výrazu X na třetí a úpravě psát X^3=2b-3 X, což je rovnice, ze které lze hodnota X vypočítat. Např. ve výrazu je a = 5, b = 2. Rovnice je potom tvaru X^3 =4- 3X, odkud je jeden kořen X = 1 ihned patrný včetně toho, že další reálná řešení tato rovnice nemá. Dodejme ještě, že obdobný rozbor lze provést i v případě, kdy ve výrazu X je mezi odmocninami znaménko plus. B) Algebraická a transcendentní čísla Definice 4.38. Algebraické číslo je takové reálné číslo, které je kořenem nějakého polynomu s racionálními koeficienty. Z množiny všech polynomů, jejichž je dané algebraické číslo kořenem, vybereme polynom s nejnižším stupněm. Tento stupeň polynomu je také stupněm tohoto algebraického čísla. Poznámka 4.39. Každé racionální číslo je algebraické. Algebraická je však i řada iracionálních čísel. Např. číslo je algebraické, neboť je řešením rovnice x^2−2 = 0. Z poznatků algebry a geometrie plyne, že pomocí kružítka a pravítka (bez stupnice) lze sestrojit právě a jen ty úsečky, jejichž délky jsou algebraická čísla stupně mocniny dvou. Z toho plyne neřešitelnost některých geometrických úloh jako je kvadratura kruhu, trisekce úhlu či duplikace krychle (tři klasické problémy antické matematiky). Věta 4.40. (1) Označme A množinu všech algebraických čísel. Pak (A ,+, ×) je komutativní těleso. (2) Kořeny polynomu, jehož koeficienty jsou algebraická čísla, jsou opět algebraická čísla. Definice 4.41. Transcendentní číslo je takové reálné číslo, které není kořenem žádné algebraické rovnice s racionálními koeficienty. Poznámka 4.42. (Viz [3]) Důkaz existence transcendentních čísel přinesl v roce 1844 francouzský matematik Joseph Liouville. Je zřejmé, že transcendentní čísla musí být iracionální, jejich iracionalita je však „jiného typu“ než např. u surdických čísel, která jsou algebraická. I když od roku 1840 byla známa existence transcendentních čísel, po řadu let se nedařilo dokázat transcendentnost dvou významných iracionálních čísel π a e. Až v roce 1873 dokázal Hermite transcendentnost čísla e a v roce 1882 Ferdinand von Lindemann transcendentnost čísla π. Poznámka 4.43. Lze dokázat, že v jistém smyslu většina iracionálních čísel je transcendentních. Abychom si udělali alespoň obecnou představu o transcendentních číslech, uvedeme výsledek, který dokázali v roce 1934 Gelfand a Schneider. (Viz [3], s. 100). Věta 4.44. Nechť a , b jsou algebraická reálná čísla, nechť b je iracionální číslo a nechť a ¹ 0, a ¹ 1. Potom všechna čísla tvaru a ^b^ jsou transcendentní. Příklad 4.45. Podle předchozí věty 4.44. mezi transcendentní čísla patří například čísla . 5. Komplexní čísla Věta 5.1. Těleso reálných čísel lze vnořit do tělesa, ve kterém má rovnice x^2 + 1 = 0 řešení. Poznámka 5.2. Důkaz je konstruktivní. Konstrukci tohoto tělesa popíšeme. Označme C kartézský součin R ´ R , tzn. C = R ´ R = {[a, b]; a Î R, b Î R}. Na množině C definujme operace sčítání a násobení takto: [a, b] + [c, d] = [a + c, b + d] , [a, b] × [c, d] = [ac - bd, ad + bc]. Lze ukázat, že (C ,+, ×) je těleso. Neutrálním prvkem vzhledem operaci sčítání je [0, 0], neutrálním prvkem vzhledem operaci násobení je [1, 0]; opačným prvkem k prvku [a, b] je dvojice [-a, -b], převráceným prvkem k prvku [a, b], kde a^2 + b^2 ¹ 0, je uspořádaná dvojice . Platí [0, 1] ×[0, 1] = [- 1, 0], tj. [0, 1] ^2+ [1, 0] = [0, 0] . Nechť nyní f: R ® C je zobrazení definované pro každé reálné číslo r Î R předpisem f(r) = [r, 0]. Pak f je vnoření tělesa (R ,+, ×) do tělesa (C ,+, ×). Definice 5.3. Těleso (C ,+, ×) se nazývá těleso komplexních čísel. Poznámka 5.4. Z předchozí definice plyne, že rovnice A+ X = B má v oboru komplexních čísel vždy jednoznačné řešení X = B- A a také rovnice A ×X = B má za podmínky A ¹ [0, 0] v oboru komplexních čísel vždy jednoznačné řešení X = . V oboru komplexních čísel tedy lze neomezeně odčítat i dělit (kromě „dělení nulou“). Snadno lze odvodit příslušné vztahy: [a, b] - [c, d] = [a - c, b - d] , , [c, d] ¹ 0. ^ Poznámka 5.5. Ve smyslu poznámky 5.2. lze ztotožnit každé reálné číslo r s komplexním číslem [r, 0]. Zápis [0, 1] ^2+ [1, 0] = [0, 0] tedy skutečně znamená, že rovnice x^2 + 1 = 0 má v množině všech komplexních čísel řešení. Tímto řešením je komplexní číslo [0, 1]. Toto číslo ale nemůže být reálné; zavádíme pro něj označení i a nazýváme ho komplexní jednotka. Protože z definice obou operací sčítání a násobení lze psát každé komplexní číslo [a, b] ve tvaru [a, b] = [a, 0]+ [0, b] = [a, 0] + [b, 0] ×[0, 1] , lze při uvedeném ztotožnění a označení psát [a, b] = a + bi. Definice 5.6. Zápis a = a + bi se nazývá algebraický tvar komplexního čísla a = [a, b]. Číslo a se nazývá reálná část komplexního čísla a , číslo b se nazývá imaginární část komplexního čísla a. . Je-li a = 0, říkáme, že číslo a je ryze imaginární. Reálná část komplexního čísla a se někdy také označuje Rea, imaginární část komplexního čísla a se někdy také označuje Ima. Poznámka 5.7. Vzhledem k rovnosti i^2 = -1 platí pro mocniny čísla i následující vztahy: i ^n = i pro n º 1 (mod 4), i ^n = -1 pro n º 2 (mod 4), i ^n =- i pro n º 3 (mod 4), i ^n = 1 pro n º 0 (mod 4). V algebraickém tvaru lze potom zapsat všechny čtyři základní operace takto: (a + bi) + (c + di) = (a + c) + (b + d)i , (a + bi) - (c + di) = (a - c) + (b - d)i , (a + bi) × (c + di) = (ac - bd) + (ad + bc)i, . Věta 5.8. V množině všech komplexních čísel C neexistuje relace uspořádání. Definice 5.9. Nechť a = a + bi je komplexní číslo. Pak komplexní číslo = a - bi se nazývá komplexně sdružené číslo k číslu a . Nezáporné reálné číslo = se nazývá absolutní hodnota komplexního čísla a . Věta 5.10. Nechť a , b jsou komplexní čísla, pak platí: (1) = 0 Û a = 0; (2) = ; (3) £ + ; (4) = × ; (5) ³ ; (6) pro b ¹ 0 ; (7) ; (8) ; (9) ; (10) Rea = , Im a = . Poznámka 5.11. Víme už, že v oboru všech komplexních čísel lze provádět všechny čtyři základní operace sčítání, odčítání, násobení a dělení (kromě dělení nulou). Nyní se budeme zabývat mocninami a odmocninami komplexních čísel. K tomu ale musíme zavést vhodnější vyjádření komplexního čísla než je algebraický tvar. Znázorníme-li každé komplexní číslo a+ bi geometricky v tzv. Gaussově rovině, bude jeho obraz ležet v bodě s kartézskými souřadnicemi [a, b]. Z matematické analýzy je však známo ještě vyjádření polohy bodu pomocí polárních souřadnic. V těchto souřadnicích se kartézské průměty na osy x, y nahradí vzdáleností daného bodu od počátku soustavy souřadnic a orientovaným úhlem, který svírá průvodič spojující daný bod s počátkem soustavy souřadnic s polopřímkou vyjadřující kladný směr osy x. Např. bod [1, 1] má v polárních souřadnicích vyjádření (cos 45° + sin 45°), bod [ , 1] má v polárních souřadnicích vyjádření 2(cos 150° + sin 150°), atd. Vyjádříme-li tímto způsobem komplexní číslo, řekneme, že jsme ho vyjádřili v goniometrickém tvaru. Komplexní číslo a = a+ bi je tedy v goniometrickém tvaru a = r(cos j + i sin j). V tomto vyjádření r = a úhel j určíme pomocí znalostí a, b a znalostí zavedení goniometrických funkcí pomocí jednotkové kružnice. Věta 5.12. Nechť a = r(cos j + i sin j), b = s(cos y + i sin y), b ¹ 0 jsou komplexní čísla. Pak platí: (1) a × b = rs(cos (j +y) + i sin (j +y)), (2) . Poznámka 5.13. Pro libovolné komplexní číslo existuje jeho n-tá mocnina. Je-li dané číslo vyjádřeno v algebraickém tvaru, lze užít binomickou větu, kde mocniny čísla i převádíme podle poznámky 5.7. Je-li ve tvaru goniometrickém, užijeme tzv. Moivreovu větu. Tento postup bývá početně snazší. Věta 5.14. (Moivreova). Nechť a = r(cos j + i sin j) je libovolné komplexní číslo, nechť n Î N. Pak platí: a^n = r^n(cos nj + i sin nj). Poznámka 5.15. Nyní obrátíme pozornost k odmocninám komplexních čísel. Protože v oboru C neexistuje relace uspořádání, nemá smysl uvažovat o kladných či záporných komplexních číslech, a proto pro každé n Î N existuje n-tá odmocnina z komplexního čísla a. Označíme-li tuto odmocninu z , platí pro ni vztah z = , tedy z^n = a. Poslední rovnice je však rovnicí binomickou, jejíž řešení je z algebry známé. Víme dokonce, že tato rovnice má n řešení, protože těleso komplexních čísel je algebraicky uzavřené. Existuje tedy celkem n odmocnin n-tého řádu z komplexního čísla a. Věta 5.16. Nechť je dána binomická rovnice z^n = a.. Číslo a vyjádříme v goniometrickém tvaru jako a = r(cos j + i sin j), pak řešení dané rovnice je: , k = 0, 1, ..., n- 1. Poznámka 5.17. Postupným konstruováním jednotlivých číselných oborů od polookruhu čísel přirozených až k tělesu komplexních čísel jsme dospěli ke struktuře, která je z algebraického hlediska „nejbohatší“. I když v C neexistuje uspořádání, lze provádět všechny čtyři základní operace (kromě dělení nulou) a pro každé komplexní číslo existuje jeho mocnina i odmocnina libovolného řádu. Těleso komplexních čísel je algebraicky uzavřené, tedy každý polynom stupně n má v C právě n kořenů (počítáme-li každý tolikrát, kolik je jeho násobnost). Proto již z praktického hlediska nemá větší význam zkoumat další možnosti rozšíření tělesa komplexních čísel. I když existuje rozšíření na těleso kvaternionů, není účelné se na tomto místě touto problematikou zabývat. 6. Cyklické grupy Poznámka 6.1. V dalším textu budeme někdy (nebude-li možno dojít k nedorozumění) algebraické struktury označovat pouze symbolem jejich nosné množiny, tzn. např. místo označení grupy (G, +) budeme psát pouze G. Text této, 6. části, je volně zpracován podle publikací [9] a [11], v níž lze nalézt i důkazy jednotlivých tvrzení. Poznámka 6.2. Nechť G je grupa. Ze základního kurzu algebry víme, že průnik libovolného počtu podgrup grupy G je rovněž podgrupa grupy G . Věta 6.3. Nechť G je grupa, nechť M je libovolná podmnožina množiny G. Symbolem označme průnik všech podgrup v G, které obsahují množinu M. Pak je nejmenší podgrupa v G (z hlediska její mohutnosti), obsahující množinu M. Definice 6.4. Podgrupa se nazývá podgrupa generovaná množinou M. Je-li M = {a}, pak budeme psát a hovořit o podgrupě generované prvkem a . Příklad 6.5. G = {1, 2, 3}, S(G) = {e, a, b, c, d, f} je grupa všech permutací množiny G, kde: , , , , , . Sestavíme operační tabulku grupy (S(G), o), kde o je operace skládání permutací: o e a b c d f e a b c d f e a b c d f a e d f b c b c e a f d c b f d e a d f a e c b f d c b a e Grupa (S(G), ) má tyto podgrupy: H[1] = {e}, H[2] = {e, a}, H[3] = {e, b}, H[4] = {e, f}, H[5] = {e, c, d}, H[6] = S(G). Pak platí: = H[1], = H[2], = H[3], = = H[5], = H[4], = H[6 .] Věta 6.6. Nechť G je grupa, nechť a Î G. Potom = {a^k; k Î Z} . Definice 6.7. Grupa G, která je generovaná jedním prvkem, tj. G = , se nazývá cyklická grupa. Prvek a se nazývá základní prvek cyklické grupy. Příklad 6.8. a) Grupa G = {1, - 1, i, - i} čtvrtých odmocnin z jedné je cyklická, základními prvky jsou buď i nebo - i. b) Grupa (Z, +) je cyklická, základními prvky jsou buď 1 nebo - 1. c) Grupa (Z[m], +) je cyklická, základní prvek je C[1]. Definice 6.9. Nechť G je konečná grupa. Pak počet prvků této grupy se nazývá řád grupy G . Věta 6.10. (Lagrange) V libovolné konečné grupě G je řád této grupy G dělitelný řádem každé její podgrupy. Věta 6.11. Nechť G = je konečná cyklická grupa řádu n (tj. G = {e = a^0, a^1, a^2, ..., a^n^-^ 1}). Pak prvek a^k je základním prvkem grupy G Û NSD(k, n) = 1. Příklad 6.12. Grupa (Z[6 ],+) je cyklická grupa řádu 6, základními prvky jsou C[1] nebo C[5 ]. 7. Faktorové struktury Definice 7.1. Nechť (G, ×) je grupoid. Nechť X, Y Í G. Pak součinem množin X, Y rozumíme množinu X × Y = {z; z = x × y; x Î X, y Î Y}. Je-li jedna z množin X, Y jednoprvková, např. X = {x}, pak místo zápisu {x} × Y budeme psát pouze x × Y nebo stručně xY. Definice 7.2. Nechť (G, ×) je grupoid, nechť W je rozklad na množině G. Pak W nazveme vytvořující rozklad na grupoidu G, jestliže pro každé dvě třídy X, Y Î W existuje třída ZÎ W s vlastností X × Y Í Z. Položíme-li X Y = Z, pak (W , ) je grupoid, který nazýváme faktoroid grupoidu G (nebo krátce faktorgrupoid). Příklad 7.3. a) Nechť (G, ×) je libovolný grupoid. Pak nejhrubší rozklad W[1] = {G} i nejjemnější rozklad W = {{g}; g Î G} jsou vytvořující. b) Nechť m je pevné přirozené číslo větší než dvě. Nechť Z[m] = {C[0 ], ..., C[m][-][1]} je rozklad množiny Z na zbytkové třídy. Pak tento rozklad je vytvořující a (Z[m ],+) je faktorgrupoid grupoidu (Z[ ],+). Definice 7.4. Nechť (G, ×) je grupoid, nechť º je relace ekvivalence na G. Pak º je relace kongruence na grupoidu (G, ×), jestliže platí a º b Þ a × c º b × c, c × a º c × b pro libovolné a, b, c Î G . Věta 7.5. Nechť (G, ×) je grupoid, nechť º je relace ekvivalence na G. Pak jsou následující výroky ekvivalentní: (1) Relace º je kongruence na (G, ×); (2) a º b, c º d Þ a × c º b × d pro libovolné a, b, c, d Î G . Věta 7.6. Nechť (G, ×) je grupoid, nechť º je relace ekvivalence na G ,nechť W je rozklad na G příslušný ekvivalenci º . Pak relace º je kongruence na grupoidu (G, ×), právě když W je vytvořujícím rozkladem. Věta 7.7. Nechť (G, ×) je grupa, nechť (H, ×) je podgrupa grupy G. Pak {a × H; a Î G}, resp. {H × a; a Î G} jsou rozklady na G. Definice 7.8. Nechť H je podgrupa grupy G. Pak rozklad {a × H; a Î G}, resp. {H × a; a Î G} se nazývá levý, resp. pravý rozklad grupy G podle podgrupy H. Označení: G/[l ]H, G/[p ]H. Třída a × H, resp. H × a tohoto rozkladu se nazývá levá, resp. pravá třída prvku a vzhledem k podgrupě H. Poznámka 7.9. Z předchozího plynou následující důsledky: 1. a Î a × H, a Î H × a (neboť a = a × e = e × a, e Î H), 2. H Î G/[l ]H, H Î G/[p ]H (neboť H = e × H = H × e), 3. x Î a × H Û x × H = a × H (tedy každá levá třída je určena libovolným svým prvkem; podobně pro pravé třídy), 4. H × H = H. Věta 7.10. Nechť (G, ×) je grupa, nechť (H, ×) je podgrupa grupy G, nechť a, b Î G. Pak platí: (1) a, b patří do jedné třídy G/[l ]H Û a^-^ 1× b Î H, (2) a, b patří do jedné třídy G/[p ]H Û b × a^-^ 1Î H . Věta 7.11. Nechť (G, ×) je grupa, nechť (H, ×) je podgrupa grupy G, nechť a, b Î G jsou libovolné prvky. Pak existují následující bijektivní zobrazení f : a×H ® H×a, g: a×H ® b×H, h: G/[l] H ® G/[p ]H. Poznámka 7.12. Třídy rozkladu jsou stejně početné vzhledem k dané grupě. Všechny třídy rozkladu (pravé i levé) jsou stejně početné vzhledem k libovolnému prvku. Počet tříd v levém i pravém rozkladu vzhledem ke stejné podgrupě je stejný. Definice 7.13. Podgrupa H grupy G se nazývá invariantní podgrupa (někdy též normální dělitel), jestliže pro každý prvek a Î G platí a×H = H×a. Věta 7.14. Nechť (G, ×) je grupa, nechť (H, ×) je podgrupa grupy G. pak jsou následující výroky ekvivalentní: (1) H je normální dělitel, (2) h Î H, g Î G libovolně Þ g^-^ 1× h × g Î H, (3) g Î G libovolně Þ g^-^ 1× H × g = H , (4) G/[l] H = G/[p ]H, (5) G/[l] H, G/[p ]H jsou vytvořující rozklady na grupě G. Poznámka 7.15. Je-li H je normální dělitel v grupě G, pak G/[l] H = G/[p ]H. Proto se v tomto případě užívá pouze označení G/ H . Rozklad G/ H je vytvořujícím rozkladem na G. Poznamenejme ještě, že v komutativní grupě je každá podgrupa invariantní. Poznámka 7.16. Z teorie cyklických grup víme, že řádem konečné grupy je počet prvků této grupy. Dále je dokazována Lagrangeova věta, podle které v konečné grupě je její řád dělitelný řádem každé její podgrupy. Odtud mj. plyne, že konečná grupa, jejíž počet prvků je prvočíslo, má pouze dvě podgrupy: triviální a sebe samu. Pro každou (konečnou) podgrupu H konečné grupy G dále platí, že počet prvků ve všech třídách rozkladů G/[l] H, G/[p ]H je stejný a je roven počtu prvků podgrupy H, a že počet tříd rozkladů G/[l] H, G/[p ]H je rovněž stejný. Definice 7.17. Nechť H je podgrupa konečné grupy G. Pak systémy G/[l] H, G/[p ]H mají stejný počet tříd, který se nazývá index podgrupy H v grupě G. Věta 7.18. Nechť H je podgrupa konečné grupy G. Pak řád grupy G je součinem řádu podgrupy H a indexu podgrupy H v grupě G. (Důsledkem je Lagrangeova věta.) Věta 7.19. Nechť (H, ×) je invariantní podgrupa grupy (G, ×). Pak faktorgrupoid (G/ H , ) je grupa. Jednotkovým prvkem této grupy je třída H a pro libovolné x, y Î G platí: (x × H) ( y × H) = (x × y) × H , ( x × H)^-^ 1 = x^-^ 1 × H . Definice 7.20. Nechť (H, ×) je invariantní podgrupa grupy (G, ×). Pak faktorgrupoid (G/ H , ) se nazývá faktorgrupa grupy G podle normální podgrupy H. Věta 7.21. Všechny vytvořující rozklady na grupě jsou právě rozklady grupy vytvořené jejími invariantními podgrupami, tedy jediné faktorgrupoidy grupy jsou její faktorgrupy. Příklad 7.22. V příkladu 6.5. byla uvedena grupa (S(G), ) permutací tříprvkové množiny a všechny její podgrupy. Uvažujme dvě z nich, a to nejprve podgrupu H = {e, a} a potom podgrupu K = {e, c, d}. Platí: a) S(G)/[l] H = {{e, a}, {b, c}, {d, f}}, S(G)/[p ]H = {{e, a}, {b, d}, {c, f}}, tj. S(G)/[l] H ¹ S(G)/[p ]H. Podgrupa H není invariantní. Řád podgrupy H je 2, její index je 3. b) S(G)/[l] K = {{e, c, d}, {a, b, f}}, S(G)/[p ]K = {{e, c, d}, {a, b, f}}, tedy S(G)/[l] K = S(G)/[p ]K. Podgrupa K je tedy invariantní a platí S(G)/[ ]K = {{e, c, d}, {a, b, f}}. Řád podgrupy K je 3, její index je 2. Označme nyní třídy rozkladu S(G)/[ ]K, např. E = {e, c, d}, A = {a, b, f}, pak faktorgrupa (S(G)/ K , ) grupy (S(G), ) je určena operační tabulkou o E A E A E A A E Definice 7.23. Nechť (R ,+, ×) je okruh. Neprázdná množina I Í R se nazývá ideál okruhu R, jestliže platí: (1) i, j Î I Þ i - jÎ I, (2) i Î I, r Î R Þ i × r Î I, r × i Î I. Poznámka 7.24. Platí, že (I ,+, ×) je podokruh okruhu (R ,+, ×) a (I ,+) je invariantní podgrupa grupy (R ,+). Rozklad (R ,+)/[ ](I ,+) budeme značit pouze R/ I. Poznamenejme dále, že každý okruh obsahuje dva základní ideály, a to nulový ideál {0[R]} a nevlastní ideál R. Věta 7.25. Nechť R je okruh, I jeho ideál. Pak rozklad R/ I je vytvořující rozklad na grupoidu (R , ×). Věta 7.26. Nechť R je okruh, I jeho ideál. Pak (R/ I ,+, ×) je okruh, jehož operace jsou definovány následujícím způsobem: Nechť a, b jsou libovolné prvky množiny R. Pak platí (a + I) + (b + I) = (a + b) + I, (a + I) × (b + I) = (a × b) + I . Definice 7.27. Nechť R je okruh, I jeho ideál. Pak okruh (R/ I ,+, ×) se nazývá faktorokruh okruhu R podle ideálu I. Věta 7.28. Nechť (R ,+, ×) je okruh a W vytvořující rozklad na grupoidech (R ,+) i (R ,×), tentýž na obou těchto grupoidech. Nechť I Î W je ta třída, která obsahuje 0[R] . Pak I je ideál okruhu R a platí R/ I = W . Definice 7.29. Nechť R je okruh, I jeho ideál. Řekneme, že prvky a, b Î R jsou kongruentní podle ideálu I , jestliže platí a - bÎ I . Píšeme a º b (I). Věta 7.30. Nechť R je okruh, I jeho libovolný ideál. Kongruence podle ideálu I je kongruence na grupoidech (R ,+) i (R ,×), rozklad příslušný této kongruenci je R/ I . Věta 7.31. Nechť (R ,+, ×) je okruh. Pak všechny kongruence na grupoidech (R ,+) i (R ,×) jsou kongruencemi podle některého ideálu okruhu R. Každý faktorokruh okruhu R je tedy faktorokruhem podle některého ideálu. okruhu R. 8. Svazy a Booleovy algebry Definice 8.1. Svazem nazýváme algebraickou strukturu S = (S, Ù , Ú) se dvěma binárními operacemi průsek ( Ù) a spojení (Ú), které splňují pro každé tři prvky a, b, cÎ S následující podmínky: (1) a Ù (b Ù c) = (a Ù b) Ù c, a Ú (b Ú c) = (a Ú b) Ú c , (2) a Ù b = b Ù a , a Ú b = b Ú a , (3) a Ù a = a , a Ú a = a , (4) a Ù (a Ú b) = a , a Ú (a Ù b) = a . Poznámka 8.2. Svaz lze také definovat jako uspořádanou množinu (S, £ ), v níž pro každé dva prvky a, b existuje jejich infimum ( ozn. Ù) a supremum (ozn. Ú). Definice 8.3. Svaz (S, Ù , Ú) se nazývá: (1) distributivní, jestliže pro každé a, b, cÎ S platí a Ù (b Ú c) = (a Ù b) Ú (a Ù c) , a Ú (b Ù c) = (a Ú b) Ù (a Ú c); (2) modulární, jestliže pro každé a, b, cÎ S splňující a £ c platí a Ú (b Ù c) = (a Ú b) Ù c; (3) komplementární, jestliže má nejmenší prvek 0 a největší prvek 1 a ke každému prvku aÎ S existuje jeho komplement, tj. prvek bÎ S s vlastností a Ú b = 1, a Ù b = 0; (4) booleovský, je-li distributivní a komplementární (pak jsou komplementy určeny jednoznačně); (5) úplný, jestliže pro každou podmnožinu množiny S (i nekonečnou) existuje její supremum a infimum. Definice 8.4. Svaz, který je úplný, distributivní a komplementární (doplňkový), se nazývá Booleova algebra. Poznámka 8.5. Booleovu algebru je možno definovat přímo, bez využití svazové interpretace. To je obsahem následující definice. Definice 8.6. Nechť B je neprázdná množina, na níž jsou definovány dvě binární operace +, × a jedna unární operace ` (doplněk), splňující pro každé x, y, z Î B následující axiomy (symbol pro násobení × budeme bez újmy na srozumitelnosti často vynechávat): (1) x + y = y + x , x y = y x (2) x + (y + z) = (x + y)+ z, x(y z) = (x y) z (3) x× (y + z) =(x y) +( x z), x + (y z) = (x + y) × (x + z) (4) x + 0 = x , x × 1 = x (5) x + x` = 1 , x × x` = 0 . Pak algebraická struktura (B, +, × ) se nazývá Booleova algebra. Poznámka 8.7. V interpretaci Booleovy algebry pomocí svazů je operace sčítání (ozn.+) jiným označením operace spojení (ozn. Ú) a operace násobení (ozn. ×) jiným označením operace průsek (ozn. Ù). Pro „počítání“ v Booleově algebře platí kromě axiomů z definice řada zajímavých pravidel. Některé z nich jsou obsahem následující věty: Věta 8.8. Nechť (B, +, × ) je Booleova algebra, nechť x, yÎ B. Pak platí: (1) (x`)` = x , (2) 1` = 0 , 0` = 1, (3) x + x = x , x × x = x , (4) x + 1 = 1 , x × 0 = 0 , (5) (x + y) ` = x`× y` , (x× y) ` = x` + y` , (6) x + (x× y) = x , x × (x+ y) = x , (7) x + (x`× y) = x + y , x × (x`+ y) = x × y , (8) x + y = 0 Û x = 0 a y = 0 , x × y = 1 Û x = 1 a y = 1 , (9) x = y Û x y` + x`y = 0 , (10) x = y Û (x + y`) × ( x`+ y) = 1 . Poznámka 8.9. V Booleově algebře platí princip duality: Nechť j je platná formule Booleovy algebry. Jestliže v této formuli nahradíme operaci sčítání násobením a naopak, operaci násobení sčítáním, a dále zaměníme prvky 0, 1, dostaneme opět platnou formuli Booleovy algebry. Jako ilustrace může sloužit předchozí definice a věta. Poznámka 8.10. Existují dva nejvýznamnější modely Booleovy algebry, a to množinová algebra a algebra pravdivostních hodnot výroků. a) Množinová algebra. Nechť M je neprázdná množina. Nosičem B Booleovy algebry bude systém 2^M všech podmnožin množiny M, roli operace sčítání bude hrát operace sjednocení množin a roli operace násobení bude hrát operace průnik množin. Jako doplněk prvku Booleovy algebry bude vystupovat doplněk množiny v množině M. Prvkem 0 bude prázdná množina, prvkem 1 základní množina M. b) Algebra pravdivostních hodnot výroků. B = {0, 1}, jako operace sčítání bude figurovat disjunkce výroků, jako násobení bude figurovat konjunkce výroků. Roli doplňku bude hrát negace výroku, prvkem 0 bude nepravdivý výrok, prvkem 1 pravdivý výrok. V tomto smyslu lze konstatovat, že množinová algebra i algebra pravdivostních hodnot výroků mají tentýž matematický základ. Příklad 8.11. Zjednodušte zápis množiny: (A Ç E Ç C) È [(D Ç A) `È B] `È (E Ç C `Ç A) È [(B È D) `Ç A]^. . Řešení: Zadaný zápis množiny přepíšeme do Booleovy algebry. Dostaneme booleovský výraz, který upravíme: aec + [(da) `+ b] `+ ec`a + [(b + d) `a] = ae(c + c`) + dab`+ b`d`a = ae + ab`(d + d`) = ae + ab`= a(e + b`). Po zpětném přepisu do symboliky množinové algebry dostaneme hledané zjednodušení: A Ç (E È B`) . 9. Číselné soustavy Poznámka 9.1. Problematika zápisů čísel provází lidstvo už od starověku. Je známá řada poznatků o způsobech numerace během historického vývoje, např. numerace ve starém Egyptě a Mezopotámii, numerace antického Řecka a Říma nebo numerace starých Mayů. Jedná se o velmi zajímavé otázky, kterými se však na tomto místě nemůžeme zabývat. Konstatujme pouze, že během vývoje se vykrystalizovaly dva typy číselných soustav, a to poziční a nepoziční. Základní rozdíl je v tom, že nepoziční soustavy nerozlišují řád číslice v zápisu čísla, kdežto poziční soustavy ano. Většina numeračních soustav v dávné historii byla nepoziční (Egypt, Mezopotámie, Řecko, Řím), zatímco v dnešní době se užívají výhradně poziční soustavy. Jediná nepoziční soustava, se kterou se ještě dnes můžeme setkat, jsou římské číslice. Uvědomme si ovšem, že s římskými číslicemi nepočítáme (neprovádíme žádné početní výkony), slouží pouze jako zápisy letopočtů atp. Poziční soustavy, jak už bylo řečeno, rozlišují řád číslice. Proto je potřeba mít určen tzv. základ poziční číselné soustavy. Dnes se užívá pro běžné počítání výhradně soustava se základem deset (desítková soustava). Ve výpočetní technice se můžeme setkat ještě se soustavami, jejichž základem jsou některé mocniny čísla dvě (soustava dvojková, čtyřková, osmičková a šestnáctková). Pozičním číselným soustavám bude věnována tato kapitola. Budeme se zabývat převody zápisů čísel a početními výkony v nedesítkových číselných soustavách. Zřejmě se můžeme omezit pouze na kladná čísla; začneme čísly přirozenými a následně si uvedeme i převody zápisů čísel racionálních. Příklad 9. 2. Nepoziční soustavy nerozlišují řád číslice, zatímco poziční soustavy ano. Tedy např. v zápise římskými číslicemi je číslo I I I rovno třem, zatímco v desítkové soustavě je číslo 111 rovno sto jedenácti. Nepoziční soustavy nemají symbol pro nulu, který je naopak v pozičních soustavách nutný. Např. čísla stojedna, tisíc jedna jsou zapsána v desítkové soustavě 101, 1001, zatímco pomocí římských číslic C I, M I. Věta 9. 3. Nechť z je pevně zvolené přirozené číslo větší než jedna, nechť a je libovolné přirozené číslo. Pak platí: (1) Existuje přirozené číslo n s vlastností z^n £ a < z^n+1. (2) Číslo a lze vyjádřit právě jedním způsobem ve tvaru a = a[n ]z^n + a[n][-][1 ]z^n^-^1 + a[n][-][2 ]z^n^-^2 + ... + a[2 ]z^2 + a[1] z + a[0] , (⋆) kde a[i] , i = 0, 1, 2, ..., n jsou nezáporná celá čísla menší než z. Definice 9. 4. Nechť platí označení předchozí věty a pro čísla a, n platí vyjádření (⋆). Pak říkáme, že jsme číslo a vyjádřili v číselné soustavě o základu z. Zkráceně píšeme a = (a[n]a[n][-][1]...a[0])[z ], přičemž závorky lze v zápisu vynechat. Číslo z nazýváme základ číselné soustavy, symboly a[i] , i = 0, ..., n se nazývají číslice (cifry). O číslici a[i] říkáme, že je řádu i, číslo z^i se nazývá jednotka řádu i pro i = 0, ..., n. Poznámka 9. 5. Je-li z > 10, plyne z předchozí věty, že v soustavě o základu z musí existovat právě z různých cifer 0, 1, ..., z - 1. Protože v běžně užívané desítkové soustavě máme k dispozici pouze deset cifer 0, ..., 9, je nutno doplnit další symboly. Podle mezinárodní konvence se užívá A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Soustavy o základu větším než 16 se již nepoužívají, proto není potřeba zavádět další symboly. Poznámka 9. 6. (Porovnávání čísel). V každé poziční číselné soustavě platí stejná pravidla pro porovnávání čísel jako v soustavě desítkové (obecně není problém ověřit). Konkrétně tedy platí: Obsahuje-li zápis přirozeného čísla a v číselné soustavě o základu z právě n číslic (číslice nejvyššího řádu je nenulová), pak z^n^-^1 £ a < z^n. Jsou.li zapsána dvě přirozená čísla a, b v číselné soustavě o stejném základu (číslice nejvyššího řádu jsou nenulové), pak platí: 1. To číslo, v jehož zápisu je více číslic, je větší. 2. Mají-li zápisy obou čísel stejný počet číslic, pak je větší to číslo, v jehož zápisu číslice nejvyššího řádu označuje větší přirozené číslo. 3. Nechť dvě různá čísla a, b jsou zapsána v téže soustavě zápisem o stejném počtu číslic, tj. (a[n]a[n][-][1]...a[0])[z ], (b[n]b[n][-][1]...b[0])[z]. Existuje-li číslo k (0 £ k < n) s vlastností a[i] = b[i] pro i = n, n-1, ..., k+1, a[k] ¹ b[k] , pak větší je to číslo, v jehož zápise číslice řádu k označuje větší přirozené číslo. Poznámka 9. 7. (Převádění zápisů přirozených čísel) Při převádění zápisu přirozeného čísla a z desítkové soustavy do číselné soustavy o základu z postupujeme tak, že číslo a vydělíme číslem z se zbytkem. V dalším kroku vezmeme neúplný podíl předchozího dělení a opět dělíme základem soustavy. Takto pokračujeme tak dlouho, dokud není neúplný podíl roven nule (po konečném počtu dělení tento případ musí nastat). Hledaný ^ zápis čísla a v soustavě o základu z je určen všemi zbytky po všech provedených děleních, které napíšeme vedle sebe počínaje od posledního k prvnímu. Při praktickém převádění využíváme nejčastěji jednoduché schéma o dvou sloupcích, které si ilustrujeme nejprve pro a = 986, z = 4, pak pro a = 2507, z = 16. Do prvního řádku zapíšeme do záhlaví čísla a, z, do levého sloupce píšeme neúplné podíly a do pravého sloupce zbytky. Výsledný zápis pak získáme zapsáním zbytků „odspodu nahoru“. Obrácený převod z nedesítkové do desítkové soustavy se provádí rozvojem v nedesítkové soustavě. Příklad 9. 8. 986 4 246 61 15 3 0 2 2 1 3 3 986 = 33122[4 ]. Zkouška: 3122[4 ] = 3 . 4^4 + 3 . 4^3 + 1 . 4^2 + 2 . 4 + 2 = 3 . 256 + 3 . 64 + 16 + 8 + 2 = 986. Příklad 9. 9. 2507 16 156 9 0 11 12 9 2057 = 9CB[16] . Zkouška: 9CB[16] = 9 . 16^2 + 12 . 16 + 11 = 9 . 256 + 12 . 16 + 11 = 2304 + 192 + 11 = 2507. Povšimněme si, že v případě z > 10 přepisujeme dvouciferné zbytky pomocí písmen a opačně, při rozvoji čísla místo písmene použijeme příslušné dvouciferné číslo. Poznámka 9. 10. Na základě poznámky 9.7. lze nyní převést zápis jakéhokoliv přirozeného čísla z desítkové soustavy do nedesítkové a naopak. V případě, že chceme převést zápis přirozeného čísla zapsaného v nedesítkové soustavě do jiné nedesítkové soustavy, je nejvýhodnější přechod přes desítkovou soustavu. Existují ovšem případy (a jsou hojně využívány zejména v informatice), kdy lze takový převod mezi dvěma nedesítkovými soustavami provést přímo. To lze provést tehdy, jestliže pro dva základy soustav z[1] , z[2 ] platí vztah z[1 ]= z[2]^n pro nějaké přirozené číslo n. S ohledem na praktické využití jsou důležité zejména přímé převody mezi soustavou dvojkovou a čtyřkovou, dvojkovou a osmičkovou, dvojkovou a šestnáctkovou, resp. mezi čtyřkovou a šestnáctkovou. Převody se provádí na základě následující věty: Věta 9. 11. Nechť pro dva základy soustav z[1] , z[2 ] platí vztah z[1 ]= z[2]^n pro nějaké přirozené číslo n. Pak číslo zapsané n ciframi v číselné soustavě o základu z[2] lze zapsat jedinou cifrou v číselné soustavě o základu z[1] . Příklad 9. 12. Převeďte číslo 110110010110[2] do soustavy se základem 8. Víme, že 8 = 2^3. Platí : 110101010110[2 ]= 1 . 2^11 + 1 . 2^10 + 0 . 2^9 + 1 . 2^8 + 0 . 2^7 + 1 . 2^6 + 0 . 2^5 + 1 . 2^4 + 0 . 2^3 + 1 . 2^2 + 1 . 2 + 0 = (1 . 2^2 + 1 . 2 + 0) . (2^3)^3 + (1 . 2^2 + 0 . 2 + 1) . (2^3)^2 + (0 . 2^2 + 1 . 2 + 0) . 2^3 + (1 . 2^2 + 1 . 2 + 0) = 6 . 8^3 + 5 . 8^2 + 2 . 8 + 6 = 6526[8] . Poznámka 9. 13. Postup uvedený v předchozím příkladu je těžkopádný a nepřehledný. V praxi postupujeme tak, že při převodu zápisu přirozeného čísla ze základu z[2] na základ z[1] = z[2]^n zapíšeme dané číslo ve zkráceném tvaru v soustavě z[2], rozdělíme zprava na n-ciferné skupiny, přičemž každá taková skupina n cifer dá podle věty 9. 11. jednu cifru v soustavě z[1]. Příklad 9.12. lze pak psát takto: 110110010110[2] = 110| 110| 010| 110[2 ]= 6526[8 ]. Při opačném převodu postupujeme analogicky. Musíme si však uvědomit, že vždy vytváříme z každé cifry v soustavě z[1] skupinu n cifer v soustavě z[2], tedy např. 301[4] = 110001[2], 301[8] = 011000001[2] , tzn. např. číslo nula je zapsáno v prvním případě dvěma nulami, zatímco ve druhém případě třemi nulami. Poznámka 9. 14. Nyní se budeme zabývat převody zápisů reálných čísel. Bez újmy na obecnosti se můžeme omezit na kladná reálná čísla. Připomeneme potřebné označení. Nechť a je kladné reálné číslo. Pak největší celé číslo, nepřevyšující číslo a , označíme [a] a budeme nazývat celá část čísla a . Číslo a - [a] se označuje áa ñ a nazývá se necelá část reálného čísla a . Platí tedy: a = [a] + áa ñ , [a] £ a < [a] + 1, 0 £ áa ñ < 1, [a] Î Z . V případě a > 0 je dokonce [a] Î N . Převod zápisu kladného reálného čísla a provádíme následujícím způsobem. Platí a = [a] + áa ñ . Protože [a] Î N, lze zápis čísla [a] převést do soustavy o základu z metodami popsanými výše pro převod zápisů přirozených čísel. Zbývá převést do soustavy o základu z i necelou část čísla a , tedy áa ñ,. Platí 0 £ áa ñ < 1, přičemž případ áa ñ = 0 je triviální a budeme ho z úvah vylučovat (číslo a by bylo v tomto případě přirozené). Uvažujeme tedy pouze případ 0 < áa ñ < 1. Převody zápisů takových čísel se nyní budeme zabývat. Protože nemůže dojít k nedorozumění, můžeme místo áa ñ psát pouze a . Věta 9. 15. Nechť a je kladné reálné číslo s vlastností 0 < a < 1, nechť z je přirozené číslo větší než jedna. Položme a[0 ]= 0, a[0 = ]a[ ]. Pro n = 1, 2, ... nyní položíme a[n] = [z . a[n][-][1]], a[n = ] áz . a[n][-][1] ñ . Pak číslo a lze vyjádřit ve tvaru a = a[0] , a[1]a[2]a[3]...., přičemž toto vyjádření je jednoznačné. Poznámka 9. 16. Jak jsme již uvedli v kapitole o tělese racionálních a reálných čísel, rozvoj čísla a je buďto ukončený nebo periodický pro a racionální, zatímco pro a iracionální je rozvoj nekonečný a neperiodický. Typ rozvoje však nemusí být tentýž jako v desítkové soustavě, což ukážeme na příkladech. Příklad 9. 17. a) a = 0,5, z = 3. Položíme a[0 ]= 0, a[0 = ]0, 5. Vypočteme 3 . 0,5 = 1,5 a dostáváme a[1] = 1, a[1 ]= 0,5. Opět vypočteme 3 . 0,5 = 1,5 a obdržíme stejné hodnoty a[2] = 1, a[2 ]= 0,5. Takto lze pokračovat do nekonečna, tedy platí 0,5 = 0,1111....[3 ]. Číslo 0,5 je tedy ve trojkové soustavě číslem periodickým. Správnost výpočtu snadno ověříme: 0,1111....[3 ]= 1 . 3^-^1 + 1 . 3^-^2 + 1 . 3^-^3 + ... = = 0,5 (jedná se o konvergentní geometrickou řadu). b) a = 7,65, z = 4. Podle úmluvy a = 0,65. Položíme a[0 ]= 0, a[0 = ]0,65. Vypočteme 4 . 0,65 = 2,6 a dostáváme a[1] = 2, a[1 ]= 0,6. Opět vypočteme 4 . 0,6 = 2,4 a obdržíme hodnoty a[2] = 2, a[2 ]= 0,4. Dále již bez komentáře: 4 . 0,4 = 1,6 , a[3] = 1, a[3 ]= 0,6 ; 4 . 0,6 = 2,4 , a[2] = 2, a[2 ]= 0,4 ; 4 . 0,4 = 1,6 , a[3] = 1, a[3 ]= 0,6 atd. Platí tedy 0,65 = 0,2 [4] . Protože podle zadání jsme měli převést zápis čísla a = 7,65 , stačí doplnit převod celé části tohoto čísla, tzn. čísla 7. Snadno zjistíme, že 7 = 13[4 ], dohromady tedy máme 7, 65 = 13, 2 [4] . 10. Základní pojmy a tvrzení z teorie dělitelnosti Obecná teorie dělitelnosti v okruhu Poznámka 10. 1. Všude v dalším budeme předpokládat, že okruh R má jedničku, kterou označíme 1[R ] (existence nulového prvku 0[R ]je samozřejmá). Dále poznamenejme, že tato část o obecné teorii dělitelnosti v okruhu, včetně důkazů tvrzení, je převzata z publikace [5]. Definice 10. 2. Nechť R je okruh, nechť a, b Î R . Jestliže existuje prvek r Î R takový, že a = b . r , pak říkáme, že b dělí a (prvek a je dělitelný prvkem b) a píšeme b | a . V opačném případě říkáme, že prvek a není dělitelný prvkem b a píšeme b ∤ a. Relace | se nazývá relace dělitelnosti na okruhu R . Poznámka 10. 3. Slovních formulací předchozí definice existuje celá řada. Lze např. říci, že prvek a je násobkem prvku b , prvek b je dělitelem prvku a atd. Prvek 0[R]^ je dělitelný všemi prvky okruhu R (ve vztahu 0[R] = b . r stačí položit r = 0[R]), naproti tomu prvkem 0[R ]je dělitelný právě jen prvek 0[R ] (vztah a = 0[R] . r je splněn jedině v případě a = 0[R]). Velmi často se v teorii dělitelnosti prvek 0[R ]z úvah vylučuje a omezujeme se pouze na nenulové prvky okruhu. Věta 10. 4. Nechť R je okruh, pak platí: 1. Relace dělitelnosti na R je reflexivní a tranzitivní. 2. Nechť a[1], a[2], ..., a[k ], b jsou takové prvky okruhu R , pro které platí b | a[i ] pro i = 1, 2, ..., k. Nechť t[1], t[2], ..., t[k ]jsou libovolné prvky z R. Pak . Definice 10. 5. Nechť e Î R je prvek s vlastností e |1[R ]. Pak prvek e se nazývá jednotka okruhu R . Poznámka 10. 6. Jednotka okruhu R je zřejmě takový prvek, k němuž existuje inverzní prvek vzhledem k operaci násobení. Lze dokázat, že množina J(R) všech jednotek okruhu R tvoří vzhledem k operaci násobení grupu. Definice 10. 7. Nechť R je okruh. Jestliže pro prvky a, b Î R existuje jednotka e Î J(R) s vlastností a = b . e, pak říkáme, že prvek a je asociován s prvkem b. Věta 10. 8. Relace asociovanosti z definice 10. 7. je relace ekvivalence na množině R . Poznámka 10. 9. Vzhledem k předchozí větě platí, že je-li prvek a je asociován s prvkem b, pak je také prvek b asociován s prvkem a. Můžeme tedy říkat, že prvky a, b jsou v R asociovány a píšeme a ∼ b. Poznámka 10. 10. Relace asociovanosti je ekvivalence na množině R . Existuje tedy rozklad množiny R , který je touto ekvivalencí určen. Třídy tohoto rozkladu jsou tvořeny navzájem asociovanými prvky. Jednou třídou je vždy množina {0[R]}, další třídou je vždy množina J(R), protože všechny jednotky jsou asociovány s jedničkou 1[R]. Dále již obecně nelze říci nic, snad s výjimkou případu, kdy R je těleso. V tělese je každý nenulový prvek jednotkou, a proto rozklad R| [∼] má právě dvě třídy {0[R]} a J(R) = R - {0[R]}. Z hlediska dělitelnosti je proto těleso nezajímavé (také proto se v matematice nezkoumá dělitelnost v oboru racionálních nebo reálných čísel). Poznámka 10. 11. Nyní se zaměříme na případ, kdy R bude oborem integrity. Všude v dalším budeme tedy v R kromě existence jedničky předpokládat neexistenci vlastních dělitelů nuly. Věta 10. 12. Nechť R je obor integrity. pak platí: a ∼ b Û a | b Ù b | a . Věta 10. 13. Nechť R je obor integrity, nechť a, b, a[0], b[0 ] Î R. Pak platí: 1. Pro každou jednotku e Î J(R) a každý prvek r Î R platí e | r . 2. Jestliže platí a[0] ∼ a, b[0] ∼ b, pak a | b Û a[0] | b[0] . Důsledek 10. 14. Každý prvek oboru integrity R je dělitelný všemi jednotkami z R a všemi s ním asociovanými prvky v R . Definice 10. 15. Nechť R je obor integrity, nechť r Î R. Pak všechny jednotky z R a všechny prvky asociované s prvkem r se nazývají nevlastní dělitelé prvku r (někdy též triviální dělitelé). Ostatní dělitelé prvku r (pokud existují), se nazývají vlastní dělitelé. Definice 10. 16. Nechť r Î R je nenulový prvek, který není jednotkou v R . Pak prvek r se nazývá reducibilní (rozložitelný) v R , jestliže má v R vlastní dělitele. v opačném případě se tento prvek nazývá ireducibilní (nerozložitelný). Poznámka 10. 17. Prvek r Î R se tedy nazývá reducibilní, jestliže jej lze vyjádřit jako součin dvou takových prvků oboru integrity R, z nichž žádný není v R jednotkou ani není s prvkem r asociován. Pokud takové vyjádření neexistuje, je prvek r ireducibilní. Odtud dále plyne, že v tělese, kde každý nenulový prvek je jednotkou a všechny nenulové prvky jsou navzájem asociovány, nemá otázka reducibility a ireducibility opodstatnění (všechny nenulové prvky tělesa jsou ireducibilní). Věta 10. 18. Nechť R je obor integrity, nechť r, s Î R , nechť platí r ∼ s . Potom platí: r je ireducibilní v R Û s je ireducibilní v R . Definice 10. 19. Nechť R je obor integrity, nechť M je neprázdná podmnožina R . Pak prvek t Î R se nazývá společný dělitel množiny M v R , jestliže pro každý prvek m Î M platí t | m. Píšeme t | M. Definice 10. 20. Nechť R je obor integrity, nechť M je neprázdná podmnožina R . Pak prvek d Î R se nazývá největší společný dělitel množiny M v R , jestliže platí: 1. d | M 2. Pro každé t Î R platí: t | M Þ t | d . Poznámka 10. 21. Je-li M konečná množina, např. M = {a[1], ..., a[k]} , pak hovoříme o společném děliteli (největším společném děliteli) prvků a[1], ..., a[k] . Poznamenejme ještě, že obecně v oboru integrity z definice 10. 20. neplyne existence největšího společného dělitele množiny M. O jeho jednoznačnosti však obecné tvrzení vyslovit lze. Věta 10. 22. Nechť R je obor integrity a nechť existuje největší společný dělitel d množiny M v R. Pak D = { r Î R ; r ∼ d } je množina všech největších společných dělitelů množiny M v R. Dělitelnost v oboru celých čísel I. Úvod, základní pojmy Poznámka 10. 23. Z algebry víme, že množina všech celých čísel s operacemi sčítání a násobení tvoří obor integrity. Proto lze dělitelnost v množině všech celých čísel chápat jako speciální případ výše popsané obecné teorie dělitelnosti v oboru integrity. Jednotky oboru integrity Z jsou čísla 1, -1, s každým celým číslem z je asociováno pouze opačné celé číslo -z. Protože víme, že každé celé číslo je dělitelné všemi jednotkami v Z a všemi celými čísly s ním asociovanými, plyne odtud, že každé celé číslo z má čtyři triviální dělitele: 1, -1, z, -z. Ireducibilními prvky v oboru integrity Z jsou právě všechna prvočísla, reducibilními prvky jsou čísla složená. Do oboru integrity Z lze přímo přenést i definici největšího společného dělitele. Protože však teorie dělitelnosti v množině celých čísel patří mezi základní učivo při výuce matematiky na všech stupních škol, uvedeme dále tuto teorii přímo, bez odkazu na obecnou teorii dělitelnosti v okruhu. Budeme postupovat velmi stručně, zájemce lze odkázat na publikaci [2] a elektronický učební kurz [17]. Definice 10. 24. Ří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 10. 25. 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 10. 26. 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 10. 27. 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 10. 28. 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 10. 29. 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 10. 30. 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 10. 31. 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 10. 32. 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 10. 33. 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 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 10. 36.), c) pomocí rozkladu daných čísel na součin prvočinitelů. Věta 10. 36. 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. 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ě 10. 36. 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 10. 37. 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 10.38. 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. 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. Poznámka 10. 39. Definice 10. 33. a 10. 38. lze rozšířit na libovolný konečný počet přirozených čísel. V případě, že počet těchto čísel je větší než dvě, je ale nutno pojem nesoudělnosti upřesnit. Definice 10. 40. Nechť a[1], a[2 ],[, ]a[3 ], ..., a[n ], n > 2, jsou nesoudělná přirozená čísla (s vlastností NSD(a[1], a[2 ],[, ]a[3 ], ..., a[n]) = 1). Jestliže pro libovolnou dvojici indexů i, j Î {1, 2, ..., n} platí NSD(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í NSD(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 10. 41. Čí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 NSN(a, b). Poznámka 10. 43. 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. Definici 10. 42. lze rozšířit na libovolný konečný počet přirozených čísel a[1], …, a[n]. Poznámka 10. 44. 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 NSN(a, b) a NSD(a, b) c) pomocí rozkladu daných čísel na součin prvočinitelů Věta 10. 45. Pro každá dvě přirozená čísla a, b platí a . b = NSN(a, b) . NSD(a, b). Poznámka 10. 46. Větu 10. 45. nelze rozšířit na více než dvě přirozená čísla. V. Obecná kritéria dělitelnosti: Věta 10.47: 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 10. 48. 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. Věta 10. 49. (Obecné kritérium dělitelnosti přirozeného čísla a = a[0] +10a[1] +10 ^2a[2] +10 ^3a[3]+ …+10 ^ma[m] přirozeným číslem n): Pro dané přirozené číslo a vypočteme jeho ciferný součet c s vahami jednotlivých cifer takto: Pro každé k = 0, ..., m označíme b[k][ ] zbytek po dělení čísla 10^k číslem n (platí tedy b[k ]º 10^k(mod n)). Potom c = a[0] b[0] + a[1] b[1] + a[2] b[2] + …+ a[m] b[m] . Podle pravidel pro počítání s kongruencemi (bude uvedeno dále) dává číslo c při dělení číslem n stejný zbytek, jako číslo a. Odtud plyne tvrzení: Číslo a je dělitelné číslem n, právě když číslo c je dělitelné číslem n . Poznámka 10. 50. Poznamenejme, že posloupnost čísel b[k ]je vždy konečná a počet jejích prvků nemůže být větší než číslo n-1 (počet možných nenulových zbytků při dělení číslem n). V opačném případě, pokud by některá mocnina deseti byla dělitelná číslem n, nepoužili bychom toto obecné kritérium. Kritérium dělitelnosti číslem n by potom bylo analogické kritériu dělitelnosti číslem 4, 8, 25,...). Příklad 10. 51. a) Dělitelnost čísla 5894 sedmi. Platí: 1[ ]º 1(mod 7), 10[ ]º 3(mod 7n), 100[ ]º 2^k(mod 7), 1000[ ]º 6(mod 7), 10^4[ ]º 4(mod 7), 10^4[ ]º 5(mod 7), 10^6[ ]º 1(mod 7), 10^7[ ]º 3(mod 7), 10^8[ ]º 2(mod 7) atd. Induktivním postupem jsme zjistili, že posloupnost zbytků 1, 3, 2, 6, 4, 5 se neustále opakuje. Proto b[0] = 1, b[1] = 3, b[2] = 2, b[3] = 6, b[4] = 4, b[5] = 5, b[6] = 1, b[7] = 3, b[8] = 2 atd. Nyní vypočteme c = 4 . 1 + 9 . 3 + 8 . 2 + 5 . 6 = 77, což je číslo dělitelné sedmi. Proto i číslo 5894 je dělitelné sedmi. Poznamenejme, že s ohledem na vlastnosti kongruencí lze v posloupnosti čísel b[k ]nehradit kterékoliv z nich číslem kongruentním s n, tedy posloupnost 1, 3, 2, 6, 4, 5 lze nahradit posloupností 1, 3, 2, -1, -3, -2, která je lépe zapamatovatelná a při výpočtech vhodnější (vypočtená čísla c jsou menší než pro původní hodnoty). Např. pro číslo 5894 by bylo c = 4 . 1 + 9 . 3 + 8 . 2 + 5 . (-1) = 42. b) Dělitelnost čísla a =548 893 672 185 729 643 číslem 17. Vypočteme posloupnost zbytků b[k ](podrobnosti si již odpustíme): 1, -7, -2, -3, 4, 6, -8, 5, -1, 7, 2, 3, -4, -6, 8, -5. Nyní určíme ciferný součet c čísla a s vahami cifer: c = 3.1 - 4.7 - 6.2 - 9.3 + 2.4 + 7.6 -5.8 + 8.5 - 1.1 + 2.7 + 7.2 + 6.3 - 3.4 - 9.6 + 8.8 - 8.5 + 4.1 - 5.7 = -42. Číslo c dává po dělení číslem 17 zbytek 9, tj. také zadané číslo a dává při dělení sedmnácti zbytek 9, není tedy číslem 17 dělitelné. VI. Prvočísla, čísla složená Definice 10. 52. 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 10. 53. Číslo 1 podle definice není prvočíslo ani číslo složené. Věta 10. 53. Každé složené přirozené číslo n > 1 má alespoň jednoho prvočíselného dělitele, menšího než . Důsledek 10. 54. 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 10. 55.. 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 10. 56. 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 10. 57. Určete 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 10. 58. 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 10. 59. 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 10. 60. 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 10. 61. 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 10. 62. (Ř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. VIII. Kongruence, rozklad na zbytkové třídy. Poznámka 10. 63. Problematika kongruencí a zbytkových tříd je důležitou součástí moderní algebry. Lze ji rozdělit na dvě součásti, které jsou obě založené na relaci kongruence v oboru všech celých čísel. V první části se budeme nejprve věnovat samotné relaci kongruence a jejím důležitým vlastnostem (podobným vlastnostem rovnic). Jejich význam a užití poznáte ve cvičeních. V následující části se pak stručně dotkneme i rozkladu na zbytkové třídy a vlastnostem algebraických struktur definovaných na systémech zbytkových tříd. I když jste se těmto strukturám již věnovali dříve, do kapitoly o dělitelnosti organicky patří také. Věta 10. 64. 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 <ôbô, 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. Definice 10. 65. Eulerova funkce j(n) vyjadřuje počet přirozených čísel menších nebo rovných číslu n, nesoudělných s n. Nechť n = p[1]^a^ . ... p[k]^a^ , pak platí j(n) = n . . Je-li n prvočíslo, pak j(n) = n - 1. Definice 10. 66. (Kongruence) Nechť a, b Î Z, m Î N, m ³ 2. Pak říkáme, že číslo a je kongruentní s číslem b podle modulu m a píšeme a º b (mod m), právě když mú (a - b). Dvě čísla kongruentní podle nějakého modulu m dávají při dělení tímto modulem m týž zbytek. Věta 10. 67. Relace kongruence je ekvivalence na množině všech celých čísel (je reflexivní, symetrická a tranzitivní). Věta 10. 68. Vlastnosti kongruencí: 1) Nechť p je prvočíslo, pak a º b (mod p^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 m[i]) , i = 1,2,...,k Þ a º b (mod NSN(m[1],...,m[k])) Platí-li kongruence podle několika modulů, platí i podle modulu rovného nejmenšímu společnému násobku těchto modulů. 3) a[i ]º b[i] (mod m), i = 1,...,k Þ º (mod m), º (mod m). 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 º 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ě kongruence. 6) a^n º b^n (mod m) Obě strany kongruence lze umocnit na libovolný přirozený exponent. 7) d÷ a Ù d÷ b Ù NSD(d, m) = 1 Þ º (mod m) 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÷ a Ù e÷ b Ù e÷ c Þ º (mod ) Obě strany kongruence i modul lze vydělit týmž celým kladným číslem různým od nuly. 10) a º b (mod m) Ù d÷ m Þ a º b (mod d) Platí-li kongruence podle modulu m, platí i podle modulu rovnému libovolnému kladnému děliteli čísla m, většímu než jedna. Věta 10. 69. (Eulerova věta) Nechť m Î N, m > 1, a Î Z, NSD(a, m) = 1, pak platí: a^j^(m) º 1 (mod m). Je-li specielně p prvočíslo, které není dělitelem čísla a, pak platí a^p^-^1 º 1 (mod p) (tzv. malá Fermatova věta). Definice 10. 70. Nechť m je pevné přirozené číslo větší než jedna. Označme C[i ]= { x Î Z; x dává po dělení číslem m zbytek i } , pro i = 0, 1, …, m - 1. Pak množina C[i] se nazývá zbytková třída podle modulu m. Symbolem Z[m] pak označíme množinu všech zbytkových tříd podle modulu m , tj. Z[m] = {C[0] , C[1] , …, C[m][-][1]} . Poznámka 10. 71. Protože při dělení číslem m jsou možné zbytky 0, 1, …, m - 1, je počet zbytkových tříd podle modulu m roven číslu m. Každá zbytková třída podle modulu m obsahuje nekonečně mnoho celých čísel, která dávají při dělení modulem m týž zbytek (tzn. liší se o nějaký celočíselný násobek modulu m). Příklad 10. 72. a) m = 4 C[0] = {… ,-8, -4, 0, 4, 8, … } C[1] = {… ,-7, -3, 1, 5, 9, … } C[2] = {… ,-6, -2, 2, 6, 10, …} C[3] = {… ,-5, -1, 3, 7, 11, …} b) m = 5 C[0] = {…,-10, -5, 0, 5, 10, …} C[1] = {… ,-9, -4, 1, 6, 11, … } C[2] = {… ,-8, -3, 2, 7, 12, …} C[3] = {… ,-7, -2, 3, 8, 13, …} C[4] = {… ,-6, -1, 4, 9, 14, …} Věta 10. 73. Nechť m je pevné přirozené číslo větší než jedna. Pak množina Z[m ]všech zbytkových tříd podle modulu m tvoří rozklad množiny Z všech celých čísel. Poznámka 10. 74. Nyní se budeme zabývat binárními operacemi sčítání a násobení definovanými na množině Z[m ] pro různé moduly m. Obě operace na systému všech zbytkových tříd budeme chápat následujícím způsobem: Nechť např. m = 5. Zápis součtu C[3] + C[4] = C[2] znamená, že sečtením libovolného celého čísla dávajícího při dělení pěti zbytek 3 s libovolným celým číslem dávajícím při dělení pěti zbytek 4 dostaneme vždy celé číslo, které při dělené pěti dává zbytek 2. Analogicky zápis spoje násobení C[2] . C[4] = C[3] znamená, že vynásobením libovolného celého čísla dávajícího při dělení pěti zbytek 2 s libovolným celým číslem dávajícím při dělení pěti zbytek 4 dostaneme vždy celé číslo, které při dělené pěti dává zbytek 3. Populárně řečeno, výsledek sčítání či násobení zbytkových tříd podle modulu m získáme tak, že sečteme nebo vynásobíme indexy zbytkových tříd ze zadání úlohy, zjistíme zbytek součtu či součinu při dělení číslem m a tento zbytek je indexem zbytkové třídy hledaného součtu nebo součinu. Jinými slovy, rozklad Z[m] množiny Z je vytvořující vzhledem k operaci sčítání i operaci násobení. Poznámka 10. 75. V následujících tvrzeních se budeme zabývat typy algebraických struktur definovaných na množinách zbytkových tříd. Tvrzení opět nebudeme dokazovat, vždy uvedeme jen ilustraci dané struktury pomocí tabulky. Kvůli zjednodušení zápisů rovněž budeme místo třídy C[i] uvádět pouze index i (zřejmě nebude moci dojít k nedorozumění). Věta 10. 76: Nechť m je pevné přirozené číslo větší než jedna. Pak algebraická struktura (Z[m] , +) je komutativní grupa s neutrálním prvkem C[0 ]. Ilustrace (Z[4] , +): + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Věta 10. 77. Nechť m je pevné přirozené číslo větší než jedna. Pak algebraická struktura (Z[m] , . ) je komutativní pologrupa s neutrálním prvkem C[1 ]a agresivním prvkem C[0]. Ilustrace (Z[4] , .): . 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 Ilustrace (Z[5] , .): . 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Poznámka 10. 78. Prohlédneme-li si pozorně obě tabulky v ilustraci předchozí věty, vidíme, že při operaci násobení zřejmě podstatně závisí na modulu. Odstraníme-li z obou těchto tabulek první řádek a první sloupec, odpovídající třídě C[0], dostáváme následující tabulky struktur (Z[4 ]- {C[0]} , .) a (Z[5 ]- {C[0]} , .): Ilustrace (Z[4 ]- {C[0]} , .): . 1 2 3 1 1 2 3 2 2 0 2 3 3 2 1 Ilustrace (Z[5 ]- {C[0]} , .): . 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 Struktura (Z[4 ]- {C[0]} , .) nyní již není ani grupoid, neboť obsahuje v tabulce prvek 0 , který nepatří do nosné množiny (není v záhlaví tabulky). Oproti tomu, struktura (Z[5 ]- {C[0]} , .) se ještě „zlepšila, nyní jde již o komutativní grupu. Který případ nastane, závisí na modulu. Věta 10. 79. Nechť modul m je prvočíslo. Pak algebraická struktura (Z[m ]- {C[0]} , .) je komutativní grupa. Je-li modul m číslo složené, pak (Z[m ]- {C[0]} , .) není ani grupoidem. Důsledek 10. 80. Nechť modul m je prvočíslo. Pak algebraická struktura se dvěma operacemi (Z[m ]- {C[0]} ,+, .) je komutativní těleso. Poznámka 10. 81. Podle předchozího tvrzení není (Z[m ]- {C[0]} , .) pro složený modul ani grupoidem. Protože je však potřeba popsat i struktury zbytkových tříd se dvěma operacemi pro složený modul m, musíme nějak „ošetřit“ situaci nul vyskytujících se v tabulkách (např. (Z[4 ]- {C[0]} , .)). Definice 10. 82. Nechť modul m je složené číslo, nechť pro dvě zbytkové třídy C[u ], C[v] podle modulu m platí C[u ]¹ C[0 ], C[v ]¹ C[0 ]. Jestliže C[u ]. C[v] = C[0], pak obě třídy C[u ], C[v ]se nazývají vlastní dělitelé nulového prvku C[0] . Poznámka 10. 83. Definice vlastních dělitelů nulového prvku (stručně jen dělitelů nuly) je samozřejmě obecnější. Struktury zbytkových tříd však poskytují užitečnou ilustraci tohoto pojmu. Současně ve shodě s obecnou teorií algebraických struktur se dvěma operacemi umožňuje existence dělitelů nuly popsat i struktury (Z[m ],+, .) pro složený modul m. Věta 10. 84. Nechť modul m je složené číslo. Pak algebraická struktura se dvěma operacemi (Z[m],+, .) je komutativní okruh, který nikdy není oborem integrity (obsahuje dělitele nuly). Příklad 10. 85. V okruhu (Z[4],+, .) je dělitelem nuly C[2] ; v okruhu (Z[6 ],+, .) jsou dělitelé nuly C[2][, ]C[3] ; v okruhu (Z[8 ] ,+, .) jsou dělitelé nuly C[2][, ]C[4], C[6 ]. 11. Polynomy Poznámka 11. 1. Tato kapitola 11 o polynomech i kapitola následující, věnovaná řešení algebraických rovnic, je převzata (volně zpracována) z publikace [5]. Poznámka 11. 2. Nebude-li výslovně řečeno jinak, budeme se zabývat pouze polynomy s reálnými koeficienty. Definice 11. 3. Polynomem f jedné proměnné nad tělesem reálných čísel budeme nazývat algebraický výraz tvaru f = a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0] . (1) Reálná čísla a[i] pro i = 0, ..., n se nazývají koeficienty polynomu f, x označuje proměnnou. Koeficient a[n] se nazývá vedoucí koeficient polynomu f, koeficient a[0] se nazývá absolutní člen polynomu f. Stupeň polynomu je vždy určen nejvyšší mocninou u proměnné x; při označení polynomu (1) je stupeň polynomu f roven n , píšeme st(f) = n. Je-li a[n] = 1, říkáme, že polynom f je normovaný. Množinu všech polynomů jedné proměnné x nad tělesem reálných čísel budeme označovat R[x]. Polynom f budeme někdy označovat též f(x). Poznámka 11. 4. Je-li stupeň polynomu roven nule, neobsahuje výraz (1) proměnnou x. To ovšem znamená, že každé reálné číslo lze chápat také jako polynom nad tělesem reálných čísel. Definice 11. 5. Nechť f = r, r Î R, r ¹ 0. Pak říkáme, že polynom f je konstantní polynom a platí st(f) = 0. Je-li f = 0, pak říkáme, že f je nulový polynom (označujeme 0) a definitoricky klademe stupeň takového polynomu roven . Nulový polynom není tedy totéž jako polynom stupně nula. Je-li f = 1, pak říkáme, že f je jednotkový polynom (označujeme 1). Polynomy stupně jedna nazýváme též lineární polynomy, polynomy stupně dva nazýváme kvadratické polynomy a polynomy stupně tři kubické polynomy. Pro polynomy vyšších stupňů se zvláštní označení běžně nezavádí. Poznámka 11. 6. Přesná formální matematická definice polynomu je složitější. Polynom nad okruhem R je obecně definován jako jistá nekonečná posloupnost prvků z R. Tímto se zde nebudeme zabývat, zájemce může podrobné informace nalézt v publikaci [5], s. 15 – 18. Poznámka 11. 7. Pro operace sčítání a násobení polynomů platí pravidla, běžně známá už ze základní školy. Jejich znalost nadále předpokládáme. Věta 11. 8. Algebraická struktura (R[x], +, .) je obor integrity, který není tělesem. Nulovým prvkem je nulový polynom 0 , jedničkou je jednotkový polynom 1. Tento okruh budeme krátce značit jen R[x]. Důkaz: Operace sčítání polynomů je zřejmě komutativní a asociativní, neutrálním prvkem je 0. Ke každému polynomu f existuje opačný polynom -f, tedy (R[x], +) je komutativní grupa. Operace násobení polynomů je rovněž komutativní a asociativní s neutrálním prvkem 1 . Inverzní prvek (převrácený polynom) však obecně neexistuje (pouze pro polynomy 1 a -1). Distributivnost operace násobení k operaci sčítání je zřejmá, proto (R[x], +, .) je okruh, který není tělesem. Neexistence dělitelů nuly v (R[x], +, .) plyne z obecné věty 1. 3. a jejího důsledku ([5], s. 20 – 21). Poznámka 11. 9. Z obecné teorie dělitelnosti v oboru integrity plyne, že jednotkami okruhu R[x] jsou právě všechny nenulové konstantní polynomy (nenulová reálná čísla, viz též [5], věta 1. 4. s. 21) a s každým polynomem f Î R[x] jsou asociovány všechny jeho násobky nenulovým reálným číslem. Poznamenejme dále, že z předchozí věty plyne existence neomezeně definované operace odčítání polynomů v R[x] (převádí se na přičítání opačného polynomu), zatímco operace dělení polynomů v R[x] není obecně definována. Tomu se budeme dále věnovat. Pro operace sčítání a násobení polynomů v R[x] platí řada zřejmých vztahů, z nichž některé nyní uvedeme (předpokládáme, že f, g Î R[x]): st(f + g) £ max {st(f), st(g)}, st (f . g) = st (f) + st(g) , platí zákony o krácení (f ¹ 0, f . g = f . h Þ g = h ). Poznámka 11. 10. Vlastnosti polynomů nad R[x] nejsou v obecném případě tak samozřejmé, jak se zdá na první pohled. Např. u polynomů nad okruhem Z[4] platí pro f = 2x, g = 2x^2 vztah st(f . g) = st (0 x^3) = st(0) = < 3 = st(f) + st(g), v Z[4][x] dále platí (1 + 2x) . (1 + 2x) = 1, tzn. jednotkou v Z[4][x] může být i lineární polynom. Těmito případy se však nebudeme zabývat (podle poznámky 11. 2. se omezujeme pouze na polynomy s reálnými koeficienty). Definice 11. 11. Nechť f, g Î R[x]. Existuje-li polynom h Î R[x] s vlastností f = g . h, pak říkáme, že polynom g dělí polynom f a píšeme g | f . V opačném případě říkáme, že polynom g nedělí polynom f a píšeme g ∤ f. Poznámka 11. 12. Analogicky jako v obecné teorii je nulový polynom v R[x] dělitelný každým polynomem z R[x], zatímco vztah 0 | f platí jedině v případě, že f = 0 . Protože R[x] je obor integrity (a R je dokonce těleso), lze na dělitelnost v R[x] převést všechny pojmy a tvrzení z obecné teorie dělitelnosti v oboru integrity. Definice 11. 13. Nechť f, g Î R[x] jsou dva reálné polynomy, g ¹ 0. Jestliže existují polynomy q, r Î R[x] s následujícími vlastnostmi 1. f = g . q + r, 2. st (r) < st (g), pak říkáme, že lze provést dělení se zbytkem polynomu f polynomem g . Polynom q se nazývá podíl a polynom r zbytek tohoto dělení. Věta 11. 14. Dělení se zbytkem polynomu f polynomem g lze provést pro libovolnou dvojici reálných polynomů f, g Î R[x], g ¹ 0, přičemž podíl i zbytek jsou určeny jednoznačně. Poznámka 11. 15. V obecném případě polynomů f, g nad libovolným okruhem se může stát, že dělení se zbytkem nelze vůbec provést, případně že podíl a zbytek nejsou určeny jednoznačně. S těmito případy se ale ve školské praxi běžně nesetkáváme, proto se jimi nebudeme zabývat. Podrobnosti lze nalézt v [5] na s.23 – 25. Poznámka 11. 16. Známe těleso reálných čísel R i těleso komplexních čísel C , přičemž víme, že těleso C je nadtělesem tělesa R . Proto lze všechny polynomy s reálnými koeficienty chápat současně jako polynomy v C[x], tj. polynomy s komplexními koeficienty. Pro libovolnou dvojici takových komplexních polynomů f, g Î C[x], g ¹ 0, které mají všechny koeficienty reálné, vždy ale dostaneme jako podíl i zbytek opět polynomy se všemi reálnými koeficienty. Definice 11. 17. Nechť f Î R[x] je polynom tvaru (1), nechť c Î R je pevně zvolené reálné číslo. Pak reálné číslo a[n ]c^n + a[n][-][1 ]c^n^-^1 + ... + a[2] c^2 + a[1] c + a[0] se nazývá hodnota polynomu f v bodě c a označuje f(c). Je-li f(c) = 0, pak číslo c nazýváme kořen polynomu f . Poznámka 11. 18. Kořenem nulového polynomu je každé reálné číslo, naopak každý polynom stupně nula nemá nikdy žádný kořen. Pro polynomy z R[x] platí následující fakta: - Lineární polynom má vždy právě jeden kořen. - Polynomy vyšších stupňů kořeny mít mohou, ale také nemusí. - Neexistuje obecný algoritmus pro určení kořenů polynomu. V dalším textu se k problematice určování kořenů ještě vrátíme. Věta 11. 19. Nechť f, g Î R[x]. Pak platí: 1. f = g Þ " cÎ R ; f(c) = g(c) . 2. " cÎ R ; (f + g)(c) = f(c) + g(c) (f - g) (c) = f(c) - g(c) (f . g) (c) = f(c) . g(c) Věta 11. 20. Reálné číslo c je kořenem polynomu fÎ R[x], právě když polynom (x - c) dělí polynom f. Pro polynom (x - c) se v tomto případě užívá název kořenový činitel. Definice 11. 21. Nechť R je těleso všech reálných čísel, nechť k je přirozené číslo. Prvek cÎ R se nazývá k – násobný kořen (kořen násobnosti k) polynomu fÎ R[x], jestliže platí: 1. (x - c) ^k | f . 2. (x - c) ^k+1∤ f. Pro k = 1 budeme užívat názvu jednoduchý kořen. Poznámka 11. 22. Jestliže platí podle předchozí definice (x - c) ^k | f, pak také samozřejmě platí (x - c) ^m | f pro všechna přirozená čísla m = 1, 2, ..., k. Proto je k – násobný kořen podle věty 11. 20. kořenem ve smyslu definice 11. 17. Věta 11. 23. Nechť fÎ R[x] je polynom s reálnými koeficienty, f ¹ 0 . Jsou-li reálná čísla c[1], c[2], ..., c[n] navzájem různé kořeny polynomu f o násobnostech k[1], k[2], ..., k[n] , pak polynom f je dělitelný polynomem . Důsledek 11. 24. Nechť fÎ R[x] je reálný polynom stupně m ³ 0. Pak platí: Jsou-li reálná čísla c[1], c[2], ..., c[n] navzájem různé kořeny polynomu f o násobnostech k[1], k[2], ..., k[n] , pak platí nerovnost k[1] + k[2] + ... + k[n] £ m. Každý reálný polynom stupně m ³ 0 má tedy nejvýše m reálných kořenů . Poznámka 11. 25. Až doposud jsme chápali reálné polynomy ve smyslu definice 11. 3. jako algebraické výrazy. Z matematické analýzy však víme, že reálný polynom lze současně chápat jako předpis jisté reálné funkce s velmi „sympatickými“ vlastnostmi (je definovaná a spojitá na celé reálné ose, v každém bodě má derivaci, snadno se integruje atd.). Tuto možnost nyní teoreticky popíšeme. Definice 11. 26. Nechť fÎ R[x] je reálný polynom. Pak zobrazení F[f] : R ® R, definované vztahem F[f] (r) = f(r) pro libovolné reálné číslo r, se nazývá polynomiální funkce polynomu f . Je-li Y: R ® R nějaké zobrazení, pak Y se nazývá polynomiální funkce, je-li polynomiální funkcí nějakého reálného polynomu z R[x]. Definice 11. 27. Řekneme, že dva reálné polynomy f, g Î R[x] jsou funkčně rovné, platí-li F[f ]= F[g] , tzn. pro libovolné reálné číslo r platí f(r) = g(r). Věta 11. 28. Dva reálné polynomy f, g Î R[x] jsou rovné, právě když jsou funkčně rovné. Poznámka 11. 29. Předchozí věta 11. 28. platí obecně nejen pro polynomy nad tělesem reálných čísel, ale nad libovolným nekonečným oborem integrity (viz [5], s. 31.). Obecně tedy není možné z funkční rovnosti dvou polynomů nad libovolným okruhem usuzovat na jejich rovnost (opačná implikace plyne z věty 11. 19.). S touto situací se však běžně v praxi nesetkáte (příklad viz [5], s. 31.). Proto je možné (a v matematické analýze běžně využívané) ztotožnit polynom s jeho polynomiální funkcí (někdy se užívá i názvu polynomická funkce). Poznámka 11. 30. Nyní se budeme zabývat problematikou dělitelnosti v oboru integrity R[x], tj. dělitelností reálných polynomů. Můžeme využít všech pojmů a tvrzení, které jsme uvedli v kapitole o obecné teorii dělitelnosti v oboru integrity. Věta 11. 31. Nechť f, g Î R[x] jsou dva reálné polynomy takové, že f ¹ 0 a g | f. Pak platí: st(g) £ st(f). Věta 11. 32. Nechť f, g Î R[x] jsou dva reálné polynomy. Pak jsou následující výroky ekvivalentní: 1. f ∼ g 2. f | g Ù g | f 3. Existuje nenulové reálné číslo c s vlastností f = c . g Poznámka 11. 33. Připomeňme, že jednotkami okruhu R[x] jsou právě všechny nenulové konstantní polynomy (nenulová reálná čísla, viz též [5], věta 1. 4. s. 21). Podle předchozí věty jsou s každým polynomem f Î R[x] asociovány všechny jeho násobky nenulovým reálným číslem. Věta 11. 33. Nechť pro polynomy z R[x] platí: g | f[1], g | f[2], ..., g | f[k] (kde k je pevné přirozené číslo) , nechť h[1], h[2], ..., h[k] jsou libovolné reálné polynomy z R[x]. Pak g | . Definice 11. 34. Nechť h, f[1], f[2], ..., f[k] Î R[x]. Platí-li h | f[i ]pro i = 1, 2, ..., k, pak polynom h se nazývá společný dělitel polynomů f[1], f[2], ..., f[k ] . Definice 11. 35. Nechť f[1], f[2], ..., f[k] Î R[x]. Pak největším společným dělitelem polynomů f[1], f[2], ..., f[k] nazýváme polynom dÎ R[x], pro který platí: 1. d je společným dělitelem polynomů f[1], f[2], ..., f[k ], 2. je-li hÎ R[x] společným dělitelem polynomů f[1], f[2], ..., f[k ], pak je h | d. Označujeme d = NSD (f[1], f[2], ..., f[k]). Věta 11. 36. K libovolným polynomům f[1], f[2], ..., f[k] Î R[x] (k Î N) existuje největší společný dělitel. Věta 11. 37. Množinu všech největších společných dělitelů polynomů f[1], f[2], ..., f[k] Î R[x] obdržíme jako množinu všech nenulových konstantních násobků jednoho (libovolného) největšího společného dělitele polynomů f[1], f[2], ..., f[k] Î R[x]. Poznámka 11. 38. V množině všech největších společných dělitelů polynomů f[1], f[2], ..., f[k] Î R[x] existuje vždy jeden, který je normovaný. Ten budeme označovat pouze (f[1], f[2], ..., f[k]). Poznámka 11. 39. Důležitou otázkou je nyní způsob výpočtu největšího společného dělitele reálných polynomů. Nejvýhodnější metodou je Eukleidův algoritmus postupného dělení, jehož princip již byl uveden v kapitole o dělitelnosti v oboru celých čísel. Ukázka praktického výpočtu je uvedena v [5], s. 36 – 39. Věta 11. 40. Nechť f, gÎ R[x] jsou reálné polynomy, z nichž alespoň jeden je nenulový. Potom platí: 1. Existují polynomy u, vÎ R[x] s vlastností f . u + g . v = (f, g) 2.Je-li navíc st(f), st(g) ³ 1, pak lze polynomy u, v z části 1. vybrat tak, že platí nerovnosti st(f) > st(v) , st(g) > st(u). Definice 11. 41. Polynomy f, gÎ R[x] nazýváme nesoudělné, je-li (f, g) = 1. Věta 11. 42. Nechť f, gÎ R[x]; pak polynomy f, g jsou nesoudělné, právě když existují polynomy u, vÎ R[x] s vlastností f . u + g . v = 1. Věta 11. 43. Nechť f, g, h Î R[x], pak platí: 1. (f, g) = 1 Ù (f, h) = 1 Þ (f, g.h) = 1 2. h | (f.g) Ù (h, f) = 1 Þ h | g 3. g | f Ù h | f Ù (g, h) = 1 Þ ( g.h) | f Poznámka 11. 44. Nyní následuje stručné pojednání o rozkladu polynomů nad tělesem reálných čísel. Protože víme, že v tomto případě často hraje důležitou roli i těleso čísel komplexních (např. polynom x^2 + 1 nelze rozložit v oboru reálných čísel, ale je možno ho rozložit v oboru čísel komplexních), budeme od nynějška do svých úvah zahrnovat i těleso komplexních čísel. Jak víme, jedná se o nadtěleso tělesa všech reálných čísel. Množinu všech polynomů nad tělesem komplexních čísel budeme označovat C[x]. Definice 11. 45. Nechť fÎ R[x], st (f) ³ 1. Řekneme, že polynom f je reducibilní (rozložitelný) v R[x] (nebo též nad tělesem R), jestliže existují polynomy g, hÎ R[x], 1£ st(g), st(h)< st(f) takové, že platí f = g . h V opačném případě říkáme, že polynom f je v R[x] ireducibilní (nerozložitelný). Věta 11. 46. Nechť fÎ R[x]. Pak platí: 1. Je-li f reducibilní v R[x], pak je reducibilní v C[x]. 2. Je-li f ireducibilní v C[x], pak je ireducibilní v R[x]. Poznámka 11. 47. Každý lineární polynom je vždy ireducibilní (jak v R[x], tak v C[x]). Věta 11. 48. Nechť f, gÎ R[x], nechť f je ireducibilní nad R . Pak platí: (f, g) = 1 Ú f | g . Věta 11. 49. Nechť fÎ R[x]; pak jsou následující výroky ekvivalentní: a) f je ireducibilní v R[x] b) je-li f | (g . h), kde g, hÎ R[x], pak f | g nebo f | h . Poznámka 11. 50. Část b) předchozí věty lze matematickou indukcí rozšířit pro libovolný konečný součin polynomů. Vyjádřeno slovy: Jestliže ireducibilní polynom dělí součin konečně mnoha polynomů , potom musí dělit alespoň jednoho z nich. Věta 11. 51. Nechť fÎ R[x], st (f) ³ 1. Pak platí: 1. Polynom f lze vyjádřit jako součin konečného počtu ireducibilních polynomů nad R 2. Toto vyjádření je jednoznačné až na pořadí a asociovanost. Příklad 11. 52. Část 2. předchozí věty lze ilustrovat takto: Zřejmě platí x^2 - 1 = (x + 1)(x - 1), ale také např. x^2 - 1 = (4 x + 4) nebo také x^2 - 1 = (3x + 3) atd. Podle části 2. předchozí věty se jedná o tentýž rozklad polynomu x^2 - 1 . Definice 11. 53. Nechť (M, +, .) je libovolné těleso. Řekneme, že toto těleso je algebraicky uzavřené, jestliže každý polynom fÎ M[x], st (f) ³ 1, má v M alespoň jeden kořen. Věta 11. 54. Nechť (M, +, .) je libovolné těleso. Pak následující výroky jsou ekvivalentní: 1. Těleso M je algebraicky uzavřené. 2. Každý polynom fÎ M[x], st (f) ³ 1 lze vyjádřit ve tvaru součinu lineárních polynomů z M[x]. 3. Ireducibilní polynomy v M[x] jsou právě všechny lineární polynomy. Věta 11. 55. Nechť M je algebraicky uzavřené těleso. Pak každý polynom fÎ M[x], st (f )= n ³ 1 má v M právě n kořenů, počítáme-li každý kořen tolikrát, kolik je jeho násobnost. Poznámka 11. 56. Vlastnost algebraické uzavřenosti jsme definovali obecně pro libovolná tělesa. Vrátíme-li se k našemu předpokládanému omezení na těleso R a jeho nadtěleso C, je zřejmý rozdíl mezi nimi. I když se řešením algebraických rovnic budeme ještě v dalším zabývat, již na tomto místě si připomeneme to, co je intuitivně známé z dřívějšího studia: Těleso R není algebraicky uzavřené (jistě si každý sám sestaví rovnici, která nemá reálné kořeny), zatímco těleso C algebraicky uzavřené je. Dokázat přesně formálně tuto skutečnost je ale velmi obtížné. Proto následující větu (nazývanou „Základní věta algebry“) uvedeme stejně jako ostatní tvrzení bez důkazu i bez odkazu na něj. Možná se zdá formulace základní věty algebry zbytečná (sám fakt je intuitivně jasný), ale z historického hlediska má tato věta značný význam. Věta 11. 57. Těleso C všech komplexních čísel je algebraicky uzavřené. Poznámka 11. 58. Protože těleso C je algebraicky uzavřené, platí pro něj všechno to, co jsme uvedli obecně pro algebraicky uzavřená tělesa (věty 11. 54. a 11. 55.). Stačí ve tvrzeních těchto vět nahradit označení M písmenem C . Definice 11. 59. Nechť fÎ R[x] je reálný polynom, kde f = a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0] . (2) Pak derivací polynomu f rozumíme polynom f´Î R[x] definovaný vztahem: . Poznámka 11. 60. I když jsme (na rozdíl od matematické analýzy) definovali derivaci polynomu čistě formálně, lze snadno rozepsáním dokázat, že její vlastnosti jsou analogické jako v matematické analýze. Uveďme některé z nich: - nechť st (f) = n, pak st (f´) = n - 1 ; - (f + g)´ = f´ + g´ ; - (f . g)´ = f´g + f g´ ; - (f ^k)´ = k . f^ k^-^1 . f´ . Analogicky se zavádí rovněž derivace vyšších řádů pomocí vztahu f ^(k+1) = ( f ^(k))´ , pro k Î N[0] , f ^(0) = f . Definice 11. 61. Nechť fÎ R[x] je reálný polynom tvaru (2), nechť c Î R je pevně zvolené reálné číslo. Je-li f(x) = a[0] + a[1 ](x - c) + a[2 ](x - c)^2 + ... + a[n ](x - c)^n ; a[i] Î R pak pravou stranu nazýváme Taylorův rozvoj polynomu f o středu c . Věta 11. 62. Nechť fÎ R[x], st (f) = n ³ 1, nechť c Î R. Pak existuje právě jeden Taylorův rozvoj polynomu f o středu c , který je tvaru f(x) = f(c) + (x - c) + (x - c)^2 + ... + [ ](x - c)^n . Poznámka 11. 63. a) Pozorný čtenář si jistě povšimnul, že Taylorův rozvoj polynomu f o středu c je jeho přesné vyjádření, proto v něm nevystupuje žádný zbytek (jako při rozvojích funkcí e^x, sin x, cos x apod.). b) Pro výpočet koeficientů Taylorova rozvoje polynomu f o středu c (a obecně pro dělení polynomu lineárním polynomem) existuje algoritmus, zvaný Hornerovo schéma. Jeho princip poznáte dále, zdůvodnění viz [5], s. 51 – 52. c) Význam derivace polynomu v algebře při hledání kořenů polynomu bude ukázán v kapitole o algebraických rovnicích. Poznámka 11. 64. Užití Hornerova schématu: 1. Dělení polynomu lineárním normovaným polynomem. 2. Výpočet koeficientů Taylorova rozvoje. 3. Zjištění hodnoty polynomu v daném bodě. 4. Zjištění, zda dané číslo je kořenem polynomu (řešením příslušné algebraické rovnice. Příklad 11. 65. Ukázka Hornerova schématu. Základní funkcí Hornerova schématu je dělení polynomu f lineárním normovaným polynomem g. Není-li g normovaný polynom, tj. je tvaru ax + b, a ¹ 0, a ¹ 1, pak nejprve dělence f i dělitele g vydělíme číslem a. Polynom g tím normujeme a upravíme na tvar x - c. . Nechť tedy jsou oba polynomy vyjádřeny takto: f = a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0] , g = x - c. Hornerovo schéma je tabulka, obsahující dva řádky a dva sloupce. Levé horní záhlaví nevyplňujeme, do pravého horního záhlaví vypíšeme všechny koeficienty dělence f (včetně nulových). Do levé spodní části napíšeme číslo c z dělitele a jsme připraveni počítat hodnoty v pravé spodní části. Koeficient a[n] sepíšeme o řádek níž. Potom číslem c vynásobíme toto číslo a[n ]a přičteme číslo a[n][-][1 ]z horního řádku. Vypočtené číslo zapíšeme pod koeficient a[n][-][1. ]Vynásobíme jím číslo c, přičteme a[n][-][2 ]a výsledek napíšeme pod a[n][-][1 ]. Takto postupujeme, dokud nejsou v pravé horní části [ ]vyčerpány všechny koeficienty dělence. Poslední číslo napravo v dolním řádku oddělíme. Toto oddělené číslo je zbytkem při dělení, kdežto čísla neoddělená v pravé dolní části označují koeficienty podílu. Postup ilustrujeme na příkladu: f = 3[ ]x^5 - 2[ ]x^3 - 7 x^2 + 4 x - 8 , g = x - 2 . 3 0 -2 -7 4 -8 2 3 6 10 13 30 52 Platí tedy: 3[ ]x^5 - 2[ ]x^3 - 7 x^2 + 4 x - 8 : x - 2 = 3[ ]x^4 + 6[ ]x^3 +10 x^2 + 13 x + 30, zbytek je 52. Současně jsme ověřili, že číslo 2 není kořenem polynomu f, protože f(2) = 52. Poznámka 11. 66. V poslední části kapitoly o polynomech se krátce dotkneme i problematiky interpolačních polynomů a polynomů více proměnných. Věta 11. 67. Nechť f, g Î R[x] jsou reálné polynomy, st (f), st (g) ³ n, kde n je pevné přirozené číslo. Jestliže oba polynomy f, g nabývají stejných hodnot v alespoň (n + 1) různých bodech, pak platí f = g. Věta 11. 68. Nechť c[1] , c[2] , ..., c[n+1 ]jsou navzájem různá reálná čísla, nechť y[1] , y[2] , ..., y[n+1 ]jsou libovolná reálná čísla. Pak existuje právě jeden reálný polynom fÎ R[x] takový, že st (f) £ n a platí f(c[i]) = y[i] pro i = 1, 2, ..., n + 1. Poznámka 11. 69. Lagrangeův tvar interpolačního polynomu. Nechť platí předpoklady a označení věty 11. 68. Pak hledaný polynom f(x) je tvaru + y[2] + ... + . Polynomy více proměnných Poznámka 11. 70. Polynomy více proměnných jsou formálně definovány analogicky jako polynomy jedné proměnné pomocí nekonečných posloupností. Tímto se zde nebudeme zabývat (podrobnosti viz [5]). Pro naše účely postačí intuitivní představa, podle níž mají polynomy více proměnných tvar analogický polynomům jedné proměnné s tím rozdílem, že obsahují další proměnné (obecně značené x[1] , x[2] , ..., x[n] , v případě nejvýše tří proměnných bývá běžnější označení x, y, z). Polynomy více proměnných jsou tedy např. polynomy f = 6 x^3 y z^2 + 2 x z^3 - 5 y^4z + 1, g = x^3 + y^3 + z^3, atd. I z našeho intuitivního pohledu je ale zřejmé, že na polynomy více proměnných nelze mechanicky přenést některé pojmy z teorie polynomů jedné proměnné, např. stupeň polynomu. Tím se nyní budeme zabývat. Množinu všech polynomů n proměnných nad tělesem reálných čísel budeme označovat R[x[1] , ..., x[n]]. Polynomům více proměnných nad jinými okruhy se opět nebudeme věnovat. Poznamenejme ještě, že analogicky jako u polynomů jedné proměnné jsou definovány operace sčítání, odčítání a násobení polynomů více proměnných. Věta 11. 71. R[x[1] , ..., x[n]] s operacemi sčítání a násobení je obor integrity. Definice 11. 72. Nechť R[x[1] , ..., x[n]] je obor integrity polynomů n proměnných nad tělesem reálných čísel. Nechť i[1] , ..., i[n ]jsou nezáporná celá čísla. Pak výraz (●) nazýváme členem o n proměnných, nebo stručně členem. Je-li f = Î R[x[1] , ..., x[n]] , pak (●) nazýváme členem polynomu f . Reálné číslo a nazýváme koeficientem členu (●). Stupněm členu nazýváme číslo i[1] + ... + i[n] . Definice 11. 73. Stupeň nenulového polynomu f Î R[x[1] , ..., x[n]] je roven maximálnímu ze stupňů jeho členů s nenulovými koeficienty. Polynom, jehož všechny členy mají stejný stupeň s, nazýváme homogenní polynom (stupně s). Věta 11. 74. Každý polynom f Î R[x[1] , ..., x[n]] lze napsat ve tvaru součtu homogenních polynomů navzájem různých stupňů, přičemž toto vyjádření je jednoznačné (až na pořadí). Definice 11. 75. Nechť f = Î R[x[1] , ..., x[n]] a nechť (c[1], ..., c[n]) je uspořádaná n-tice reálných čísel. Pak reálné číslo se nazývá hodnota polynomu f v bodě (c[1], ..., c[n]) a označuje se f(c[1], ..., c[n]). Je-li f(c[1], ..., c[n]) = 0, říkáme, že (c[1], ..., c[n]) je kořenem polynomu f. Poznámka 11. 76. Otázky hledání kořenů, reducibility a ireducibility v R[x[1] , ..., x[n]] jsou poměrně komplikované, proto je zde řešit nebudeme. Povšimneme si pouze možnosti ztotožnění polynomu více proměnných s jeho polynomiální funkcí (je definována analogicky jako u polynomů jedné proměnné). Věta 11. 77. Nechť f, g Î R[x[1] , ..., x[n]]. Pak platí: f = g Û " (c[1], ..., c[n])Î R ^n; f(c[1], ..., c[n]) = g(c[1], ..., c[n]) . Dva polynomy z R[x[1] , ..., x[n]] jsou tedy rovné, právě když jsou funkčně rovné. Poznámka 11. 78. Při studiu polynomů jedné proměnné jsme využívali toho, že jeho členy bylo možno seřadit sestupně nebo vzestupně. Tuto metodu však u polynomů více proměnných nelze použít. Musíme proto definovat jiný postup. Definice 11. 79. Nechť A = , B = jsou dva členy o n proměnných. Řekneme, že člen A je před členem B, existuje-li index i, 1 £ i £ n, splňující k[1] = s[1 ], ... , k[i][-][1 ]= s[i][-][1 ], k[i] > s[i] . Jestliže člen A je před členem B nebo A = B , píšeme A ≫ B. Věta 11. 80. Relace ≫ je relace lineárního uspořádání na množině všech členů o n proměnných. Definice 11. 81. Relaci ≫ nazýváme relací lexikografického uspořádání členů o n proměnných. Jsou-li členy polynomu f Î R[x[1] , ..., x[n]] uspořádány pomocí této relace, říkáme, že jsme členy polynomu f uspořádali lexikograficky. Člen, který je před všemi ostatními členy tohoto polynomu f , nazýváme vedoucí člen polynomu f. Věta 11. 82. Nechť f, g Î R[x[1] , ..., x[n]] jsou libovolné dva reálné nenulové polynomy n proměnných. Pak součin vedoucích členů polynomů f a g je vedoucím členem součinu f .g. Definice 11. 83. Polynom f(x[1], ..., x[n]) Î R[x[1] , ..., x[n]] se nazývá symetrický, jestliže se nezmění žádnou permutací proměnných, tzn. pro libovolnou permutaci (a[1], ..., a[n]) indexů 1, 2, ..., n platí: = f(x[1], ..., x[n]) . Množinu všech symetrických polynomů n proměnných nad tělesem reálných čísel budeme označovat R[s][x[1] , ..., x[n]]. Věta 11. 84. R[s][x[1] , ..., x[n]] je podobor integrity oboru integrity R[x[1] , ..., x[n]]. Věta 11. 85. Nechť A = je vedoucí člen symetrického polynomu f(x[1], ..., x[n]). Pak platí k[1] ³ k[2] ³ ... ³ k[n] . Věta 11. 86. Nechť A = je člen o n proměnných. Pak existuje pouze konečně mnoho vedoucích členů symetrických polynomů o n proměnných, které jsou za členem A. Definice 11. 87. Polynomy z R[x[1] , ..., x[n]] tvaru: s[1 ](x[1], ..., x[n]) = x[1] + x[2] + ... + x[n] s[2 ](x[1], ..., x[n]) = x[1 ]x[2] + x[1] x[3] + ... + x[1] x[n ]+ x[2]^ x[3] + ... + x[n][-][1 ]x[n] s[k ](x[1], ..., x[n]) = s[n ](x[1], ..., x[n]) = x[1] . x[2] . ... . x[n] nazýváme elementární symetrické polynomy n proměnných. Poznámka 11. 88. Elementární polynom s[1 ]je tedy součtem všech proměnných x[1] ,..., x[n], polynom s[2] je součtem všech součinů jejich dvojic, polynom s[3 ]je součtem všech součinů trojic, s[4 ]čtveřic atd. Polynom s[n ]je nakonec součinem všech proměnných x[1] ,..., x[n ]. Pro případ n = 3 a zavedené označení proměnných x, y, z je tedy: s[1 ]= x + y + z s[2] = xy + xz + yz s[3] = xyz Poznámka 11. 89. Předchozí definicí 11. 88., společně s větami 11. 85 a 11. 86 jsme si „připravili půdu“ pro uvedení hlavní věty o symetrických polynomech, která řeší existenci a jednoznačnost vyjádření libovolného symetrického polynomu pomocí elementárních symetrických polynomů. Uvedením této věty končíme naše pojednání o polynomech více proměnných. Praktický převod symetrických polynomů pomocí elementárních symetrických polynomů je poměrně pracný a zdlouhavý a poznáte jej ve cvičení, včetně řady zajímavých aplikací v praxi. Věta 11. 90. Každý symetrický polynom f(x[1], ..., x[n]) Î R[s][x[1] , ..., x[n]] lze vyjádřit jako polynom n proměnných s[1 ],[ ]s[2 ], ..., [ ]s[n ]nad R , tzn. f(x[1], ..., x[n]) = j (s[1 ], ..., [ ]s[n]) přičemž toto vyjádření je jednoznačné. 12. Rozklady polynomů, algebraické rovnice a jejich řešení Definice 12. 1. Algebraickou rovnicí budeme rozumět rovnici tvaru a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0 ]= 0 , (3) kde a[i] Î R pro i = 0, 1, ..., n. Poznámka 12. 2. Řešení algebraické rovnice je, jak je vidět z jejího tvaru (3), úzce spjato s hledáním kořenů polynomů. Řešit algebraickou rovnici (3) znamená hledat kořeny její levé strany. Kořeny lze nalézt mnoha způsoby. Řadu z nich dále uvedeme. Důležité však je (a v praxi se často využívá) umět rozložit polynom na levé straně rovnice (3). Poznamenejme ještě, že rozklad levé strany (3) má značný význam také v případě, že se jedná o algebraickou nerovnici. Poslední poznámka je terminologická. Pod označením řešení rovnice se rozumí buďto početní postup vedoucí k získání kořenů nebo přímo množina kořenů rovnice (3). Řekneme-li tedy, že řešení je pracné a zdlouhavé, máme na mysli proces, kdežto výrok „Rovnice nemá řešení“ znamená, že množina kořenů je prázdná. Z kontextu bude vždy jasné, co máme na mysli. Poznámka 12. 3. Jak již bylo uvedeno v definici 12. 1., všude v této části se budeme zabývat polynomy a algebraickými rovnicemi, jejichž všechny koeficienty jsou reálná čísla; jejich kořeny však mohou být jak reálné, tak komplexní. Jedná se tedy v těchto rovnicích o polynomy nad tělesem komplexních čísel, tj. o polynomy z C[x]. Protože však s polynomy, jejichž alespoň jeden koeficient je komplexní, se v praxi běžně nesetkáte, můžeme si dovolit výše uvedené zjednodušení. Poznámka 12. 4. Z předchozí části připomínáme, že těleso komplexních čísel je algebraicky uzavřené, což má mj. tyto důsledky: 1. Ireducibilní v C[x] jsou právě všechny lineární polynomy (tzn. každý polynom stupně alespoň dvě lze v oboru C rozložit) 2. Každý polynom stupně m má v C právě m kořenů (počítáme-li každý kořen tolikrát, kolik je jeho násobnost). 3. Každý polynom f Î C[x], f = a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0 ](a[n] ¹ 0) lze vyjádřit jako součin n lineárních normovaných polynomů a nenulové konstanty ve tvaru f = a[n] . (x - c[1]) . (x - c[2]) ... (x - c[n]) , c[i] Î C, i = 1, 2, ..., n (toto vyjádření, které je jednoznačné až na pořadí, se nazývá kanonický rozklad polynomu f). Poznámka 12. 5. Nyní se vrátíme k pojmu derivace polynomu z R[x] a uvedeme, jak lze derivaci využít při hledání jeho kořenů. Věta 12. 6. Nechť fÎ R[x] a nechť c Î R je k - násobným kořenem polynomu f . a) Je-li k = 1, pak c není kořenem f´ b) Je-li k > 1, pak c je (k - 1) – násobným kořenem f´. Věta 12. 7. Nechť fÎ R[x], c Î R , nechť k > 1 je přirozené číslo. Pak platí: 1. c je k – násobný kořen f Û c je (k - 1) – násobným kořenem polynomu (f, f´) 2. c je k – násobný kořen f Û f(c) = f´(c) = ... = f ^(k^-^1)(c) = 0, f ^(k)(c) ¹ 0. Věta 12. 8. Nechť fÎ R[x], st (f) ³ 1. Nechť dále qÎ R[x] je polynom splňující f = (f, f´) . q Pak polynom q má stejné kořeny jako polynom f , ale každý pouze jednoduchý. Poznámka 12. 9. Nyní se budeme věnovat problematice kořenů a rozkladem polynomů z C[x] s reálnými koeficienty. Věta 12. 10. Nechť fÎ C[x] je polynom s reálnými koeficienty. Nechť komplexní číslo c je k – násobným kořenem polynomu f . Pak také komplexně sdružené číslo je k – násobným kořenem polynomu f . Věta 12. 11. Ireducibilními polynomy v R[x] jsou právě všechny lineární polynomy a všechny kvadratické polynomy se záporným diskriminantem. Důsledek 12. 13. Pro každý polynom f Î C[x] s reálnými koeficienty platí: 1. Polynom f má vždy sudý počet imaginárních kořenů (jsou „spárované“ po dvou komplexní sdružeností) – nemusí mít ovšem žádný imaginární kořen. 2. Je-li f lichého stupně, musí mít lichý počet reálných kořenů. 3. Každý reálný polynom f , stupně alespoň 3, je nad tělesem R reducibilní. 4. Každý reálný polynom lze vyjádřit jako součin reálného číslo a konečného počtu reálných normovaných lineárních polynomů a reálných normovaných kvadratických polynomů se zápornými diskriminanty. Je-li f nenulový polynom, pak je toto vyjádření jednoznačné až na pořadí. Poznámka 12. 14. Předchozí důsledek mj. říká, že každý polynom stupně alespoň tři lze v R rozložit, a to až na lineární a kvadratické nerozložitelné činitele. Neříká ale, jakým způsobem. Hledání rozkladů polynomů není obecně algoritmicky řešitelné. Používá se buďto hledání kořenů a postupné dělení kořenovými činiteli, dále se užívá různých vzorců, vytýkání a umělých úprav. Příklad 12. 15. Rozložte v R polynom f = x^4 + 1 . x^4 + 1 = (x^4 + 2x^2 + 1) - 2x^2 = (x^2 + 1)^2- 2x^2 = (x^2 + x + 1)( x^2 - x + 1). Z rozkladu je současně vidět, že algebraická rovnice x^4 + 1 = 0 nemá žádný reálný kořen, ale dvě dvojice komplexně sdružených kořenů (jejich výpočet není zajímavý). Další možností, jak tuto rovnici vyřešit, je řešit ji jako rovnici binomickou. O tom se ještě dále zmíníme. Poznámka 12. 16. Mezi kořeny a koeficienty polynomů v C[x] platí zajímavé tzv. Viètovy vztahy, které nyní uvedeme. Jistě si povšimnete, že pro kvadratické polynomy se tyto vztahy probírají už na střední škole. Poznamenejme, že v této větě uvažujeme všechny kořeny, tj. i komplexní (pouze v oboru C má polynom stupně n právě n kořenů). Věta 12. 17. Nechť fÎ C[x], st (f) = n ³ 1, kde f = a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0 ], a nechť c[1 ],[ ]c[2 ], ..., [ ]c[n ] jsou kořeny polynomu f. Pak platí: = c[1] + c[2] + ... + c[n] = c[1 ]c[2] + c[1] c[3] + ... + c[1] c[n ]+ c[2]^ c[3] + ... + c[n][-][1 ]c[n] = = c[1] . c[2] . ... . c[n] Poznámka 12. 18. Pravé strany ve Viètových vztazích jsou elementární symetrické polynomy vytvořené z kořenů polynomu f. Jejich užití na příkladech opět poznáte ve cvičení. Poznámka 12. 19. Nyní provedeme v rovnici (3) další omezení. Budeme předpokládat, že všechny koeficienty polynomu na levé straně rovnice (3) jsou celá čísla. Je-li alespoň jeden z nich číslo racionální (nikoliv celé), pak rovnici vynásobíme společným jmenovatelem všech takovýchto racionálních koeficientů a tím všechny koeficienty převedeme na celočíselné hodnoty. Uvedeme nyní několik užitečných tvrzení, které mohou napomoci při hledání kořenů takových rovnic s celočíselnými koeficienty. I když často k cíli vést nemusí, ve školské praxi jsou velmi užitečné. Jejich použití opět poznáte ve cvičení. Věta 12. 20. Nechť a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0] , a[i] Î Z, a[n] ¹ 0 (4) je polynom s celými koeficienty a nechť racionální číslo je kořenem f (r, s jsou nesoudělná čísla). Pak platí: r | a[0] a současně s | a[n] . Důsledek 12. 21. 1. Je-li celé číslo c kořenem polynomu s celočíselnými koeficienty, pak c | a[0. ] 2. Je-li levá strana rovnice (4) normovaný polynom (tj. a[n] = 1), pak každý racionální kořen je celé číslo. Poznámka 12. 22. Všechna tvrzení předchozí věty i jejího důsledku mají tvar implikace, přičemž žádnou z nich nelze obrátit. Tyto implikace se nejčastěji využívají v obměněném tvaru (zformulujte sami). Nelze tedy např. tvrdit, že každý celočíselný dělitel absolutního členu je řešením rovnice (4). Lze ale všechny dělitele čísla a[0] nalézt a pomocí Hornerova schématu vyzkoušet, zda mezi nimi není kořen. Pokud ani jeden z těchto dělitelů není kořenem rovnice (4), pak víme, že daná rovnice celočíselná řešení nemá. Podobně lze vypsat všechny „podezřelé zlomky“ a ověřit, zda některý není kořenem. Těchto zlomků však může být velmi mnoho a jejich zkoušení může být zdlouhavé. Proto uvedeme ještě jedno tvrzení, pomocí kterého je možné většinu „podezřelých“ zlomků ještě před zkoušením Hornerovým schématem vyřadit. Věta 12. 23. Nechť a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0] , a[i] Î Z, a[n] ¹ 0 je polynom s celými koeficienty a nechť racionální číslo je kořenem f (r, s jsou nesoudělná čísla). Pak platí: " mÎ Z: (r - ms) | f(m) . Poznámka 12. 24. Předchozí věta se užívá téměř vždy ve dvou specielních případech, a to pro hodnoty m rovny 1 a -1; platí tedy (r - s) | f(1), (r + s) | f(-1) . Poznámka 12. 25. Při hledání kořenů algebraických rovnic je užitečné i následující tvrzení, platné pro algebraické rovnice s reálnými koeficienty. (Podrobnosti viz [13]). Věta 12. 26. Nechť a[n ]x^n + a[n][-][1 ]x^n^-^1 + ... + a[2] x^2 + a[1] x + a[0 ] = 0 je algebraická rovnice. Nechť c[1], ..., c[n] jsou její kořeny (reálné i komplexní). Nechť A = max {| a[i] | ; i = 0, ..., n-1}. Pak platí: 1. Pro každý index i , i = 1, 2, ..., n platí nerovnost | c[i] | < 1 + . 2. Počet kladných reálných kořenů je roven počtu znaménkových změn v posloupnosti nenulových koeficientů a[n] , a[n][-][1] , ..., a[1] , a[0] nebo o sudé číslo menší. Důsledek 12. 27. Jsou-li všechny koeficienty polynomu kladná reálná čísla, nemůže mít tento polynom kladné kořeny. Příklad 12. 27. Je dána algebraická rovnice 4[ ]x^6 - [ ]x^3 + 4 x^2 + x - 8[ ] = 0 . A = 8, | c[i] | < 1 + = 3. Absolutní hodnota všech kořenů tedy leží v intervalu (-3, 3). Posloupnost koeficientů je 4, -1, 4, 1, -8 , obsahuje tedy 3 znaménkové změny. Proto tato rovnice má buďto 3 nebo 1 kladný kořen v intervalu (0, 3). Poznámka 12. 28. Nyní stručně popíšeme základní metody řešení některých vybraných typů algebraických rovnic (podrobnosti viz [5], s. 102 – 105). I. Lineární rovnice ax + b = 0 zřejmé II. Kvadratická rovnice ax^2 + bx + c = 0 známé ze střední školy III. Kubická rovnice a[3] x^3 + a[2] x^2 + a[1] x + a[0] = 0 (5) Nejprve vydělíme rovnici (5) číslem a[3] (předpokládáme samozřejmě a[3] ¹ 0), přeznačíme koeficienty a proměnnou označíme z: z^3 + a z^2 + b z + c = 0 Zavedeme substituci z = x - . Po dosazení a úpravě dostaneme rovnici v tzv. redukovaném tvaru x^3 + p x + q = 0 . (6) Označíme . Dále nechť K = označuje jednu (pevně zvolenou) z obou hodnot napsaného výrazu. Nechť dále u značí libovolnou (pevnou) ze tří třetích odmocnin a konečně v značí tu z třetích odmocnin , která splňuje vztah 3uv = - p. Potom kořeny rovnice (6) jsou x[1] = u + v, x[2] = e . u + e ^2. v, x[3] = e^2. u + e . v . (7) Vzorce (7) se nazývají Cardanovy vzorce. Zaveďme nyní výraz D = - 4 p^3 - 27 q^2, který budeme nazývat diskriminant. O druhu kořenů rovnice (6) lze rozhodnout podle hodnoty diskriminantu polynomu na levé straně rovnice (6). Omezíme se na kubickou rovnici (6) s reálnými nenulovými koeficienty (v případě p = 0 nebo q = 0 je řešení triviální). a) D = 0 x[1] = , x[2] = x[3 ]= . b) D > 0 jeden kořen reálný a dva imaginární komplexně sdružené kořeny, určené vztahy (7). c) D < 0 tři reálné kořeny, které však ani pomocí Cardanových vzorců (7) nelze vyřešit (tzv.“cassus irreducibilis“). Nutné je použít goniometrické řešení: Nejprve z rovnice vypočítáme hodnotu úhlu j (jednu pevně zvolenou). Kořeny rovnice (6) jsou pak určeny vztahy: , , . Poznamenejme, že Cardanovy vzorce i posledně uvedené vztahy jsou pro praktické počítání velmi pracné a zdlouhavé. Problém je rovněž v tom, že obdržené formální výsledky je nutno často pracně upravovat na použitelný tvar, zejména, užijeme-li počítače. Výjimkou jsou pouze speciálně sestavené kubické rovnice na ilustraci Cardanových vzorců. Uvedeme příklad. Příklad: Řešte rovnici x^3 - 3x + 1 = 0 . Vypočteme potřebné hodnoty. Podle zadání p = - 3, q = 1. Potom D = - 23 < 0 ; dále tedy , odtud j [1] = , j [2] = . Zvolíme j = . Potom po dosazení a úpravě obdržíme řešení , , . V tomto případě je řešené poměrně snadné (i když kořeny obdržíme pouze pomocí goniometrických funkcí). Nyní si ukážeme, jaké „problémy“ může způsobit využití některého matematického softwaru. Pomocí programu Derive obdržíme následující: , , . Je jasné, že pro jakékoliv další využití jsou takto vyjádřené kořeny zcela nevhodné. Proto musejí následovat formální úpravy. Převedeme-li komplexní číslo na goniometrický tvar , lze určit tři hodnoty výrazu : , , . Dosadíme-li první z hodnot odmocniny do výrazu pro kořen x[1], dostaneme po úpravě reálnou hodnotu . Dalším dosazením dostáváme z počítačem určených výsledků kořeny , . Snadno se přesvědčíme, že = a také = , tj. trojice řešení vypočtená přímo podle Cardanovy teorie a pomocí počítače je samozřejmě tatáž. Pro úplnost dodejme přibližné číselné hodnoty kořenů: x[1] = = 1,532088886, x[2] = = 0,3472963553, x[3 ] = = -1,879385241. Závěrem poznamenejme, že Cardanovy vzorce se v obecném případě využívají až tehdy, když není možný žádný jiný postup. V kubických rovnicích ve školské matematice se většinou podaří jeden z kořenů určit přímo, např. užitím teorie hledání kořenů polynomů s celočíselnými koeficienty (věta 12.20 až věta 12. 26). Po vydělení kořenovým činitelem pomocí Hornerova schématu již není problém vyřešit zbylé dva kořeny jako řešení kvadratické rovnice. Pokud to tvar kubické rovnice umožňuje, lze rovněž tuto rovnici řešit jako rovnici binomickou. IV. Rovnice čtvrtého stupně a[4] x^4 + a[3] x^3 + a[2] x^2 + a[1] x + a[0] = 0 (8) Stručně popíšeme metodu řešení podle R. Descarta (viz [19]). Rovnici (8) vydělíme číslem a[4] (zřejmě a[4] ¹ 0, jinak by rovnice nebyla čtvrtého stupně). Obdržíme rovnici x^4 + Bx^3 + Cx^2 + Dx + E = 0 Nyní použijeme substituci x = y - . Po dosazení a úpravě dostaneme rovnici v redukovaném tvaru y^4 + Py^2 + Qy + R = 0 (9) Polynom čtvrtého stupně na levé straně rovnice (9) se nyní budeme snažit rozložit na dva normované kvadratické trojčleny. Použijeme metodu neurčitých koeficientů. Rozklad předpokládáme ve tvaru (y^2 + Ky + L)(y^2 + My + N), musí tedy platit (y^2 + Ky + L)(y^2 + My + N) = 0. (10) Po roznásobení a porovnání koeficientů s rovnicí (9) dostaneme soustavu rovnic K + M = 0 KM + L + N = P KN + LM = Q LN = R Řešení takových soustav je obecně velmi obtížné. V tomto případě ale budeme úspěšní (musíme ale využít umělého kroku). Nejprve za M dosadíme - K a vypočteme L + N = P + K ^2 L − N = LN = R Nyní následuje avizovaný umělý obrat. Pro součet, součin a rozdíl dvou libovolných čísel u, v platí vztah: (u + v)^2 − (u − v)^2 = 4uv Tento vztah nyní uplatníme na výrazy L, N: (P + K ^2)^2 - = 4R Hodnoty P, Q, R jsou však koeficienty rovnice (9). Proto lze z poslední rovnice vypočítat hodnotu K . Po úpravě dostaneme K^6 + 2PK^4 + K^2(P^2 − 4R) − Q^2 = 0 Tato rovnice obsahuje pouze sudé mocniny neznámé K. Proto zavedeme substituci S = K^2. Tím získám kubickou rovnici o neznámé S, jejíž řešení bylo už popsáno dříve. Po vyřešení tří kořenů S po zpětném dosazení získáme hodnoty K a můžeme dopočítat hodnoty L, N. Nyní již můžeme dosadit do rozkladu (10) a po vyřešení dvou kvadratických rovnic získat řešení v proměnné y . Pak už jen stačí dosadit první substituci x = y - a konečně získáme hledané řešení rovnice čtvrtého stupně (8) proměnné x. Z uvedené metody (není samozřejmě jediná možná) plyne, že obecné řešení rovnice čtvrtého stupně je nesmírně pracné a zdlouhavé a v praxi se takřka nepoužívá. V rovnicích ve školské praxi je vždy možno využít jiný postup (nalezení kořene a dělení kořenovými činiteli, řešení jako rovnice binomická nebo reciproká), případně je v praxi nutno použít počítač. V. Rovnice vyšších stupňů Pro rovnice 5. stupně a stupňů vyšších už žádný obecný algoritmus řešení neexistuje. Podle teorie, vytvořené francouzským matematikem Galoisem, pro každé n ³ 5 existuje algebraická rovnice stupně n, která není řešitelná algebraickými metodami. Mnohé rovnice vyšších stupňů řešit můžeme, musí mít ale speciální tvar. Buďto je možné postupné „hádání“ kořenů podle 12. 20. až 12. 26. nebo je rovnice takového tvaru, který umožňuje řešit rovnici jako binomickou nebo reciprokou. Obě tyto metody znáte ze střední školy. Další metodou, jak získat kořeny algebraické rovnice, je užití numerických metod. Tyto metody se užívají velmi často v souvislosti s rozvojem výpočetní techniky. Obecný postup sestává ze tří kroků: ohraničení kořenů, jejich separace a aproximace. Mezi dnes užívané metody patří metoda půlení intervalů, metoda prosté iterace, metoda tečen (Newtonova metoda) a Halleyova metoda. Těmito problémy se nebudeme zabývat, jsou obsahem disciplíny Numerické metody. 13. Literatura [1] Beran, Ladislav. Grupy a svazy. 1. vyd. Praha : SNTL - Nakladatelství technické literatury, 1974. 358 s. [2] Drábek, Jaroslav, a kol. Základy elementární aritmetiky pro učitelství 1. stupně ZŠ. 1. vyd. Praha: Státní pedagogické nakladatelství, 1985. 223 s., 14-521-85. [3] Halaš, Radomír. Teorie čísel. 1. vyd. Olomouc: Univerzita Palackého, 1997. 140 s. ISBN 80-7067-707-4. [4] Hejný, Milan. Teória vyučovania matematiky. 2. vyd. Bratislava : Slovenské pedagogické nakladateľstvo, 1990. 554 s. ISBN 80-08-01344-3. [5] Horák, Pavel. Polynomy. 1. vyd. Brno : Rektorát UJEP, 1978. 127 s. r78U. [6] Horák, Pavel. Algebra a teoretická aritmetika. 2. vyd. Brno : Masarykova univerzita, 1993. 145 s. ISBN 80-210-0816-4. [7] Horák, Pavel. Algebra a teoretická aritmetika. II [Horák, 1988]. 1. vyd. Praha : Státní pedagogické nakladatelství, 1988. 205 s. [8] Horák, Pavel. Cvičení z algebry a teoretické aritmetiky I. 2. vyd. Brno : Masarykova univerzita, 1998. 221 s. ISBN 80-210-1853-4. [9] Katriňák, Tibor. Algebra a teoretická aritmetika 1. 1. vyd. Bratislava : Alfa, 1985. 349 s., 63-568-85. [10] Kopka, Jan. Svazy a Booleovy algebry. 1. vyd. Ústí n. Labem : Univerzita Jana Evangelisty Purkyně v Brně, 1991. 243 s. [11] KOSMÁK, LADISLAV – HORT, DANIEL. Algebra. 1. vyd. Brno: Masarykova Univerzita, 2001. 99 s. ISBN 80-210-2738-X. [12] Kučera, Radan - Skula, Ladislav. Číselné obory. Vyd. 1. Brno : Masarykova univerzita, 1998. 95 s. ISBN 80-210-1965-4. [13] MAŘÍK, ROBERT. Matematika (nejen) pro krajináře a nábytkáře. Elektronický učební text, MZLU, Brno 2011. [14] Odvárko, Oldřich - Šedivý, Jaroslav - Calda, Emil – ŽIDEK, STANISLAV. Metody řešení matematických úloh. 1. vyd. Praha : Státní pedagogické nakladatelství, 1990. 261 s. ISBN 80-04-20434-1. [15] Skula, Ladislav. Algebra a teoretická aritmetika. III, Číselné obory. 1. vyd. Praha : Státní pedagogické nakladatelství, 1984. 117 s. [16] SUŠKEVIČ, A. K. Teorie čísel. Charkov: Vydavatelství Univerzity A. M. Gorkéhov Charkově, 1954. 204 s. [17] VAŇUROVÁ, MILENA. Aritmetika 2. Elektronický učební kurz Pedagogické fakulty MU. Dostupné z elektronické adresy https://moodlinka.ped.muni.cz/login/index.php, citováno dne 14. 7. 2011. [18] Dělitelnost. In: Wikipedie – otevřená encyklopedie. Dostupné z elektronické adresy http://cs.wikipedia.org/wiki/Dělitelnost, citováno dne 12. 7. 2011. [19] Kvartická rovnice. In: Wikipedie – otevřená encyklopedie. Dostupné z elektronické adresy http://cs.wikipedia.org/wiki/Kvartická_rovnice, citováno dne 13. 8. 2011.