Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Matematika IV - 5. přednáška Okruhy a tělesa, okruhy polynomů Michal Bulant Masarykova univerzita Fakulta informatiky 23. 3. 2011 Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Obsah přednášky Q Okruhy a tělesa • Okruhy • Polynomy Q Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů Q Polynomy více proměnných Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU • R. B. Ash, Abstract algebra, http://www.math.uiuc.edu/~r-ash/Algebra.html. • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). • Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone , Handbook of Applied Cryptography, CRC Press, 2001, 780 p., http://www.cacr.math.uwaterloo.ca/hac/ Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Plán přednášky Q Okruhy a tělesa » Okruhy a Polynomy Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných •ooooooooooo oooo ooooooooo oooo Okruhy S grupami se potkáváme nejčastěji jako s množinami transformací. Přirozenější a obvyklejší pro naše počítání pak jsou skaláry, kde máme operací více. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, reálná či komplexní čísla R, C) a množiny polynomů nad takovými skaláry R. Klasickým příkladem konečného okruhu je pak okruh zbytkových tříd Zm. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných •ooooooooooo oooo ooooooooo oooo Okruhy S grupami se potkáváme nejčastěji jako s množinami transformací. Přirozenější a obvyklejší pro naše počítání pak jsou skaláry, kde máme operací více. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, reálná či komplexní čísla R, C) a množiny polynomů nad takovými skaláry R. Klasickým příkladem konečného okruhu je pak okruh zbytkových tříd Zm. Definice (Komutativní) grupa (/?, +) s neutrálním prvkem 0 G R, spolu s operací • se nazývá (komutativní) okruh (/?,+, •), pokud splňuje • (a • b) ■ c = a ■ (b ■ c), pro všechny a, b,c e R (asociativita); • a ■ b = b ■ a, pro všechny a, b G R (komutativita); • existuje prvek 1 takový, že pro všechny a G R platí 1 • a = a (existence jedničky); Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných o«oooooooooo oooo ooooooooo oooo Definice Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků ca d nulový, pak okruh R nazýváme oborem integrity. Příklad • Okruhy (Z, +, •), (Q, +, •) jsou obory integrity. • Okruh Gaussových celých čísel Z[/] = {a + bi; a, b G Z} je oborem integrity. • Okruh (Z4,+,-) není obor integrity, na rozdíl od (Z5,+, •). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných o«oooooooooo oooo ooooooooo oooo Definice Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků ca d nulový, pak okruh R nazýváme oborem integrity. Příklad • Okruhy (Z, +, •), (Q, +, •) jsou obory integrity. • Okruh Gaussových celých čísel Z[/] = {a + bi; a, b G Z} je oborem integrity. • Okruh (Z4,+,-) není obor integrity, na rozdíl od (Z5,+, •). Pokud neplatí vlastnost komutativity operace •, hovoříme o nekomutativním okruhu (nebo pouze o okruhu). V dalším se obvykle omezíme pouze na okruhy komutativní. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných o«oooooooooo oooo ooooooooo oooo Definice Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků ca d nulový, pak okruh R nazýváme oborem integrity. Příklad • Okruhy (Z, +, •), (Q, +, •) jsou obory integrity. • Okruh Gaussových celých čísel Z[/] = {a + bi; a, b G Z} je oborem integrity. • Okruh (Z4,+,-) není obor integrity, na rozdíl od (Z5,+, •). Pokud neplatí vlastnost komutativity operace •, hovoříme o nekomutativním okruhu (nebo pouze o okruhu). V dalším se obvykle omezíme pouze na okruhy komutativní. Operaci + budeme říkat sčítání a operaci • násobení. Navíc budeme vždy předpokládat existenci jedničky 1 pro operaci násobení, neutrálnímu prvku pro sčítání říkáme nula. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oo«ooooooooo oooo ooooooooo oooo Základní vlastnosti operací v okruhu V každém komutativním okruhu R s jedničkou platí následující vztahy (které nám jistě připadají samozřejmé u skalárů) O 0 • c = c • 0 = 0 pro všechny c G R, 0 —c = (—1) ■ c = c ■ (—1) pro všechny c E R, Q —(c • d) = (—c) ■ d = c ■ (—d) pro všechny c, d G R, a ■ (b — c) = a ■ b — a ■ c, Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooo«oooooooo oooo ooooooooo oooo Dělitelnost v okruhu Obecně říkáme, že a G R dělí c G R, jestliže existuje b tak, že a ■ b = c. Skutečnost, že c e R je dělitelné a e R, zapisujeme a\c. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooo«oooooooo oooo ooooooooo oooo Dělitelnost v okruhu Obecně říkáme, že a G R dělí c G R, jestliže existuje b tak, že a ■ b = c. Skutečnost, že c e R je dělitelné a e R, zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů: Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooo«oooooooo oooo ooooooooo oooo Dělitelnost v okruhu Obecně říkáme, že a G R dělí c G R, jestliže existuje b tak, že a ■ b = c. Skutečnost, že c e R je dělitelné a e R, zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů: Věta Platí-li v oboru integrity a = bcab^0, pak c je jednoznačně dáno volbou a, b. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooo«oooooooo oooo ooooooooo oooo Dělitelnost v okruhu Obecně říkáme, že a G R dělí c G R, jestliže existuje b tak, že a ■ b = c. Skutečnost, že c e R je dělitelné a e R, zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů: Věta * Platí-li v oboru integrity a = b ■ c a dáno volbou a, b. b 7^ 0, pak c je jednoznačně Důkaz. Pro a = bc = bd totiž platí 0 = b ■ c = d. (c — c') a b 0, proto □ Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooo»ooooooo oooo ooooooooo oooo Definice (jednotky, těleso) Dělitelé jedničky, tj. invertibilní prvky v R, se nazývají jednotky Jednotky v komutativním okruhu vždy tvoří komutativní grupu (vzhledem k násobení!) (/?*,-). Netriviální komutativní okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá těleso. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooo»ooooooo oooo ooooooooo oooo Definice (jednotky, těleso) Dělitelé jedničky, tj. invertibilní prvky v R, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu (vzhledem k násobení!) (/?*,-). Netriviální komutativní okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá těleso. V české literatuře se někdy v případě komutativního tělesa můžete setkat s pojmenováním pole (z angl. field). Okruhy a tělesa Dělitelnost a neroz ložitelnost Kořeny a rozklady polynomů Polynomy ví :e protne snných ooooo«oooooo OOOO ooooooooo oooo Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooooo«oooooo oooo ooooooooo oooo Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p Základním příkladem nekomutativního okruhu s jedničkou je množina Matk(R) všech čtvercových matic nad okruhem R s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Základním příkladem nekomutativního okruhu s jedničkou je množina Matk(R) všech čtvercových matic nad okruhem R s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Jako příklad nekomutativního okruhu, kde existují inverze k nenulovým prvkům (tzv. okruh s dělením) uveďme okruh kvaternionů se sčítáním po složkách a násobením odvozeným ze základních relací H = {a + b ■ i + c • j + d ■ k; a, b, c, d e R} ■2 = k2 = -1 ij = -ji = k, jk kj = i, k i ik=j. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooo»ooooo oooo ooooooooo oooo Obor integrity vs. těleso Věta Každý konečný obor integrity je těleso. Důkaz. Dokazuje se prostřednictvím homomorfismu f : R —> R, f{x) = ax (je to injekce, proto surjekce, proto je R těleso (rozmyslete!). □ Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooo»ooooo oooo ooooooooo oooo Obor integrity vs. těleso Věta Každý konečný obor integrity je těleso. Důkaz. Dokazuje se prostřednictvím homomorfismu f : R —> R, f{x) = ax (je to injekce, proto surjekce, proto je R těleso (rozmyslete!). □ A co obráceně? Samozřejmě je každé těleso oborem integrity. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooo»ooooo oooo ooooooooo oooo Obor integrity vs. těleso Každý konečný obor integrity je těleso. Důkaz. Dokazuje se prostřednictvím homomorfismu f : R —> R, f{x) = ax (je to injekce, proto surjekce, proto je R těleso (rozmyslete!). □ A co obráceně? Samozřejmě je každé těleso oborem integrity. Příklad Zřejmě je např. Z obor integrity, který není těleso. Okruhy a tělesa Dělitelnost a nere ízložitelnost Kořeny a rozklady polynomů Polynomy ví :e protne snných ooooooo«oooo OOOO ooooooooo oooo Polynomem rozumíme jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení: Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooooooo«oooo oooo ooooooooo oooo Polynomem rozumíme jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení: Definice Nechť R je komutativní okruh skalárů. Polynomem nad R rozumíme konečný výraz k f (x) = £ a,x'' ;=o kde a,- G R, i = 0,1,..., k, jsou tzv. koeficienty polynomu, přičemž navíc předpokládáme, že a k ^ 0 (s výjimkou případu, kdy jsou všechny koeficienty nulové, pak hovoříme o nulovém polynomu). Říkáme, že f(x) má stupeň k, píšeme st f = k (nebo deg f = k). Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v R, kterým říkáme konstantní polynomy. 90.0- Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooooooo«oooo oooo ooooooooo oooo Polynomem rozumíme jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení: Definice Nechť R je komutativní okruh skalárů. Polynomem nad R rozumíme konečný výraz f (x) = £ a,x'' kde a,- G R, i = 0,1,..., k, jsou tzv. koeficienty polynomu, přičemž navíc předpokládáme, že a k ^ 0 (s výjimkou případu, kdy jsou všechny koeficienty nulové, pak hovoříme o nulovém polynomu). Říkáme, že f(x) má stupeň k, píšeme st f = k (nebo deg f = k). Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v R, kterým říkáme konstantní polynomy. Množinu všech polynomů nad okruhem R budeme značit R[x]. 10 0,0- Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOO0OOO oooo ooooooooo oooo Každý polynom zadává zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c g R za nezávislou proměnnou x, tj. f(c) = a0 + a\c H-----h akCk. Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOO0OOO oooo ooooooooo oooo Každý polynom zadává zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c g R za nezávislou proměnnou x, tj. f(c) = a0 + a\c H-----h akCk. Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Kořen polynomu f(x) je takový prvek cg/?, pro který je f(c) = 0 g R. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOO0OOO oooo ooooooooo oooo Každý polynom zadává zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c g R za nezávislou proměnnou x, tj. f(c) = a0 + a\c H-----h akCk. Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Kořen polynomu f(x) je takový prvek cg/?, pro který je f(c) = 0 g R. Obecně se může stát, že různé polynomy definují stejná zobrazení. Např. polynom x2 + x g 2^[x] zadává identicky nulové zobrazení. Obecněji, pro každý konečný okruh R = {ao, a\,..., ai<} zadává polynom f (x) = (x — 3o)(x — a\)... (x — a^) identicky nulové zobrazení. Zároveň ale platí tvrzení, které dokážeme zanedlouho: Jestliže je R nekonečný okruh, pak dva polynomy f (x) a g{x) nad R jsou stejné právě tehdy když jsou stejná příslušná zobrazení f a Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných ooooooooo«oo oooo ooooooooo oooo Dva polynomy f(x) = J2i aix' a š(x) = J2i bix' umíme přirozeně také sčítat i násobit: (f + g)(x) = (a0 + bo) + (ai + r>i)x + --- + (ak + bk)xk (f ■ g)(x) = (a0bo) + ■■■ + (aob£ + + ••• + a^x1 + ... kde uvažujeme nulové koeficienty všude, kde v původním výrazu pro polynomy nenulové koeficienty nejsou uvedeny a u sčítání nechť je k maximální ze stupňů f a g. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOO0O oooo ooooooooo oooo Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOO0O oooo ooooooooo oooo Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R. Přímo z definice vyplývá, že množina polynomů R[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v R[x] je opět jednička 1 v okruhu R vnímaná jako polynom stupně nula. Lemma Okruh polynomů nad oborem integrity je opět obor integrity Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOO0O oooo ooooooooo oooo Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R. Přímo z definice vyplývá, že množina polynomů R[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v R[x] je opět jednička 1 v okruhu R vnímaná jako polynom stupně nula. Lemma Okruh polynomů nad oborem integrity je opět obor integrity. Důkaz. Máme ukázat, že v R[x] mohou být netriviální dělitelé nuly pouze tehdy, jestliže jsou už v R. To je ale zřejmé z definice násobení polynomů. Jsou-li f(x) a g{x) polynomy stupně k a í jako výše, pak koeficient u xk+e v součinu f (x) • g{x) je součin a k ■ bga ten musí být nenulový, pokud nejsou dělitelé nuly v R. □ Okruhy a tělesa OOOOOOOOOOO* Dělitelnost a nere OOOO 'zložitelnost Kořeny a rozklady polynomů OOOOOOOOO Polynomy více proměnných OOOO Formální mocninné řady V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu: Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných 0OOOOOOOOOO« oooo ooooooooo oooo Formální mocninné řady V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu: Definice Nechť R je okruh skalárů. Formální mocninou řadou nad R rozumíme (obecně nekonečný) formální výraz f(x) = X^oa'x'> kde a,- G R, i = 0,1,..., jsou tzv. koeficienty řady. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných 0OOOOOOOOOO« oooo ooooooooo oooo Formální mocninné řady V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu: Definice Nechť R je okruh skalárů. Formální mocninou řadou nad R rozumíme (obecně nekonečný) formální výraz f(x) = X^oa'x'> kde a,- G R, i = 0,1,..., jsou tzv. koeficienty řady. Snadno se ukáže, že s dříve definovanými operacemi sčítání a násobení tvoří formální mocniné řady okruh, který značíme R[[x]] (a jehož je R[x] podokruhem). Sami si zkuste rozmyslet, že invertibilními prvky tohoto okruhu jsou právě mocninné řady, které mají invertibilní absolutní člen. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Plán přednášky Q Okruhy a tělesa • Okruhy a Polynomy Q Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů O Polynomy více proměnných Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOOOO «000 ooooooooo oooo Směřujeme nyní ke zobecnění rozkladů polynomů nad číselnými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu R samotném. Uvažujme proto nějaký pevně zvolený obor integrity R, třeba celá čísla Z nebo okruh Zp s prvočíselným p. V R definujeme dělitelnost analogicky jako to známe ze Z: b\a <š=> 3c g R : a = b ■ c . Okruhy a tělesa Dělitelnost a nere uzložitelnost Kořeny a rozklady polynomů Polynomy ví :e pro m í inných oooooooooooo •ooo ooooooooo OOOO Směřujeme nyní ke zobecnění rozkladů polynomů nad číselnými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu R samotném. Uvažujme proto nějaký pevně zvolený obor integrity R, třeba celá čísla Z nebo okruh Zp s prvočíselným p. V R definujeme dělitelnost analogicky jako to známe ze Z: b\a <š=> 3c g R : a = b ■ c . Pak platí: • je-li a\b a zároveň b\c pak také a\c; • a\b a zároveň a\c pak také a\(ab + /3c) pro všechny a,(3 g R; • a|0 pro všechny a g R (je totiž a ■ 0 = 0); • každý prvek a g R je dělitelný všemi jednotkami e g Rx a jejich násobky a • e (jak přímo plyne z existence e_1) Okruhy a tělesa Dělitelnost a neroz Jožitelnost Kořeny a rozklady polynomů Polynomy ví :e protne snných oooooooooooo o«oo ooooooooo OOOO Řekneme, že prvek a e R je ireducibilní {nerozložitelný), jestliže • je nenulový a není jednotkou (tj. a\ 1), Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo o«oo ooooooooo oooo Řekneme, že prvek a e R je ireducibilní {nerozložitelný), jestliže • je nenulový a není jednotkou (tj. a\ 1), • je dělitelný pouze jednotkami e £ Rx a čísly a • e (tzv. čísla asociovaná s a - tj. taková b ). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo o«oo ooooooooo oooo Řekneme, že prvek a e R je ireducibilní {nerozložitelný), jestliže • je nenulový a není jednotkou (tj. a\ 1), • je dělitelný pouze jednotkami e £ Rx a čísly a • e (tzv. čísla asociovaná s a - tj. taková b ). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo o«oo ooooooooo oooo Řekneme, že prvek a g R je ireducibilní {nerozložitelný), jestliže • je nenulový a není jednotkou (tj. a\ 1), • je dělitelný pouze jednotkami e g Rx a čísly a ■ e (tzv. čísla asociovaná s a - tj. taková b g R, že a\b a b\a; značíme a ~ b). Řekneme, že okruh R je obor integrity s jednoznačným rozkladem, jestliže platí: • pro každý nenulový prvek a g R, který není jednotkou, existují nerozložitelné a\,..., ar g R takové, že a = a\ ■ a-i... ar • jsou-li prvky a\,..., ar a b\,..., bs nerozložitelné, nejsou mezi nimi žádné jednotky a a\ai... ar = b\bi ■ ■ ■ bs, pak je r = s a ve vhodném přeuspořádání platí ay = ejbj pro vhodné jednotky e,-. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oo»o ooooooooo oooo Příklad O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oo»o ooooooooo oooo Příklad O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná). Q Každé těleso je obor integrity s jednoznačným rozkladem (kde každý nenulový prvek je jednotka). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oo»o ooooooooo oooo Příklad O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná). O Každé těleso je obor integrity s jednoznačným rozkladem (kde každý nenulový prvek je jednotka). O Např. v okruhu Rf-v/^Š] = {a + b\/-5; 3, b e R} existují dva různé rozklady čísla 6 na nerozložitelné prvky: 6 = 2 • 3 = (1 - V^ŠXl + V^Š).3 aTo, že uvedené prvky jsou ireducibilní a že nejsou asociované, je ale třeba trochu „odpracovat". Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo ooo« ooooooooo oooo Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo ooo« ooooooooo oooo Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Věta o dělení se zbytkem pro polynomy) Nechi R je komutativní okruh bez dělitelů nuly a f,g g R[x] polynomy g ^ 0. Pak existuje a g R, a 7^ 0, a polynomy q a r splňujícíaf = qg + r, kde r = 0 nebo str < st g. Je-li navíc R těleso nebo je aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo ooo« ooooooooo oooo Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Věta o dělení se zbytkem pro polynomy) Nechi R je komutativní okruh bez dělitelů nuly a f,g g R[x] polynomy g ^ 0. Pak existuje a g R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-li navíc R těleso nebo je aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. Poznámka Toto tvrzení je možné aplikovat i obecněji (viz Euklidovské okruhy), je ale třeba správně definovat, jak budeme porovnávat prvky. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Plán přednášky Q Okruhy a tělesa • Okruhy a Polynomy Q Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů O Polynomy více proměnných Okruhy a tělesa Dělitelnost a neroz ložitelnost Kořeny a rozklady polynomů Polynomy ví :e pro m í inných oooooooooooo OOOO •oooooooo OOOO Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOOOO OOOO »00000000 oooo Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) e R[x], st f > O, a dělme jej polynomem x - b, b e R. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOOOO OOOO »00000000 oooo Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) g R[x], st f > O, a dělme jej polynomem x - b, b g R. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q ■ (x — b) + r, kde r = O nebo st r = O, tj. r g R. Tzn., že hodnota polynomu f v b g R je rovna právě f (b) = r (toto je základ postupu známého jako Homérovo schéma). Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOOOO OOOO »00000000 oooo Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) g R[x], st f > O, a dělme jej polynomem x - b, b g R. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q ■ (x — b) + r, kde r = O nebo st r = O, tj. r g R. Tzn., že hodnota polynomu f v b g R je rovna právě f (b) = r (toto je základ postupu známého jako Homérovo schéma). Proto je prvek b g R kořen polynomu f právě, když (x — b)\f. Protože po vydělení polynomem stupně jedna vždy klesne stupeň výsledku alespoň o jedničku, dokázali jsme následující tvrzení: Důsledek Každý nenulový polynom f nad tělesem R má nejvýše st f kořenů. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo o«ooooooo oooo ' Příklad * Polynom x3 má nad Zg 4 kořeny ([0]s, [2]%, [4]8,[6]8)). Je to tím, že tento okruh není oborem inte^ rrity (a tedy ani tělesem). Důsledkem předchozího tvrzení je následující velmi důležitý fakt. Důsledek Libovolná konečná podgrupa multiplikativní grupy (Kx, •) tělesa (K, +, •) je cyklická. Speciálně existuje prvek g 1, že dokonce (x — b)k\f, kde k je největší možné, říkáme, že kořen b je násobnosti k. Dva polynomy nad nekonečným komutativním okruhem, které zadávají stejné zobrazení /?—>/?, mají rozdíl, jehož kořenem je každý prvek v R. Protože rozdíl polynomů má jen konečný stupeň, pokud není nulový, dokázali jsme tak již dříve uvedené tvrzení: Věta Jestliže je R nekonečný okruh, pak dva polynomy f (x) a g{x) nad R jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooo«ooooo oooo Polynom h je největší společný dělitel dvou polynomů a f a g g R[x] jestliže: • h\f a zároveň h\g • jestliže k\fa zároveň k\g pak také k\h. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooo«ooooo oooo Polynom h je největší společný dělitel dvou polynomů a f a g g R[x] jestliže: • h\f a zároveň h\g • jestliže k\fa zároveň k\g pak také k\h. Věta (Bezoutova rovnost) Necht R je těleso a necht f,g 1, je a kořenem f násobnosti k — 1. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných OOOOOOOOOOOO OOOO 00000000« oooo Poznámka Užitečná je často také tzv. lokalizace, tj. redukce koeficientů modulo zvolené prvočíslo p, příp. posunutí proměnné o konstantu. Např., že polynom x3 + 27x2 + 5x + 97 je ireducibilní, zjistíme díky redukci, ireducibilitu tzv. kruhového polynomu xp — 1 x — 1 díky substituci x = y + 1. Věta Je-li a kořenem polynomu f nad tělesem násobnosti k > 1, je a kořenem f násobnosti k — 1. Důsledek Násobné kořeny polynomu f jsou právě kořeny (f, f). Všechny kořeny polynomu f obdržíme jako (jednoduché) kořeny polynomu Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oooo Plán přednášky Q Okruhy a tělesa • Okruhy a Polynomy Q Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů Q Polynomy více proměnných Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo »ooo Polynomy více proměnných Okruhy polynomů v proměnných x\,... ,xr definujeme induktivně vztahem /?[xi,... ,xr] := /?[xi,... ,xr_i][xr]. Např. R[x, y] = R[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem R[x]. Snadno se ověří, že polynomy v proměnných xi,... ,xr lze chápat jako výrazy vzniklé z písmen x\,... ,xn a prvků okruhu R konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo »ooo Polynomy více proměnných Okruhy polynomů v proměnných x\,... ,xr definujeme induktivně vztahem /?[xi,... ,xr] := /?[xi,... ,xr_i][xr]. Např. R[x, y] = R[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem R[x]. Snadno se ověří, že polynomy v proměnných xi,... ,xr lze chápat jako výrazy vzniklé z písmen x\,... ,xn a prvků okruhu R konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v /?[x,y] jsou tvaru f = an(x)yn + an-^y"-1 + ■■■ + a0(x) = (amnxm + ■■■ + a0n)yn + ■■■ + (r>p0xp + • • • + ůoo) = coo + ciqx + c0iy + c2ox2 + cnxy + c02y2 + • • • Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo o«oo Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme: Důsledek O Jestliže v okruhu R nejsou dělitelé nuly, pak také v okruhu polynomů R[x\,... ,xr] nejsou dělitelé nuly. Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[x\,..., xr] je obor integrity s jednoznačným rozkladem. Příklad Z[x,y] je okruh s jednoznačným rozkladem. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oo»o Symetrické polynomy Definice Polynom f g R[x\,... , x„], který se nezmění při libovolné permutaci proměnných xi,... ,x„, se nazývá symetrický polynom. Elementárními symetrickými polynomy rozumíme polynomy Sl = xi +x2 H-----hxn, s2 = xix2 + xix3 H-----h x„_ix„, Sn — X\ ■ ■ ■ xn Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo oo»o Symetrické polynomy Definice Polynom f G R[x\,... , x„], který se nezmění při libovolné permutaci proměnných xi,... ,x„, se nazývá symetrický polynom. Elementárními symetrickými polynomy rozumíme polynomy Sl = xi +x2 H-----hx„, s2 = xix2 + xix3 H-----h x„_ix„, Sn Xi • • • x„ Věta (základní věta o symetrických polynomech) Libovolný symetrický polynom lze vyjádřit jako polynom v proměnných s\,... ,sn. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo ooo« Důsledek (Viětovy (Newtonovy) vztahy) Vztahy mezi kořeny a koeficienty polynomu f(x) =xn = an-1xn~1 + - • -+aix+a0 = (x- xi)-(x-x2) • • • (x-x„); an-i = -(xi H-----hx„) = - si) an-2 = xi*2 H-----hx„_ixn) = s2 a0 = (-1)" -xi .. .xn = (- -iy-sn Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných oooooooooooo oooo ooooooooo ooo« Důsledek (Viětovy (Newtonovy) vztahy) Vztahy mezi kořeny a koeficienty polynomu f(x) =xn = an-1xn~1 + - • -+aix+a0 = (x- xi)-(x-x2) • • • (x-x„); an-i = -(xi H-----hx„) = - si) an-2 = xi*2 H-----hx„_ixn) = s2 a0 = (-1)" -xi .. .xn = (- -iy-sn Příklad Určete polynom s kořeny O *1,*22. © x x w xi ' X2 ' jsou-li xi,X2 kořeny polynomu x2 + 13x + 7 (aniž byste je vyčíslovali). ^^^^^ ^ -O O. o-