Literatura Okruhy a tělesa Dělitelnost a ner( jzložitelnost Kořeny a rozklady polynomů oooooooooooooooo oooooo OOOOOOOOOOOOOOOO Diskrétní matematika B - 9. týden Okruhy a tělesa, okruhy polynomů Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Okruhy a tělesa Dělitelnost a ner( jzložitelnost Kořeny a rozklady polym oooooooooooooooo oooooo OOOOOOOOOOOOOOOO Okruhy a tělesa • Okruhy • Okruhy polynomů • Polynomy více proměnných Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). Předmětové záložky v IS MU Jiří Rosický, Algebra, PřF MU, 2002. Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost •ooooooooooooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo S grupami se potkáváme nejčastěji jako s množinami transformací. U skalárů i vektorů ale vystupovalo hned více obdobných struktur zároveň. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, reální či komplexní čísla M, C) a množiny polynomů nad takovými skaláry R. Klasickým příkladem konečného okruhu je pak Zm. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost o»oooooooooooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Definice Komutativní grupa (/?, +) s neutrálním prvkem 0 6 R, spolu s další operací • splňující • (a • b) ■ c = a • (b • c), pro všechny a, b,c £ R (asociativita); • a ■ b = b ■ a, pro všechny a, b 6 /? (komutativita); « existuje prvek 1 takový, že pro všechny a £ /? platí 1 • a = a (existence jedničky); » a • (fa + c) = a • fa + a • c, pro všechny a,b,c £ R (distributivita); se nazývá komutativní okruh. Takový okruh zapisujeme (/?, +, •). Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oo»ooooooooooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Definice Jestliže v komutativním okruhu R platí c ■ d = 0 právě, když je alespoň jeden z prvků c a d nulový, pak okruh R nazýváme oborem integrity3. aAngl. integrál domain 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, narozdíl od (Zs,+,-). Pokud neplatí vlastnost komutativity operace •, hovoříme o nekomutativním okruhu (nebo pouze o okruhu). 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. V každém komutativním okruhu /? s jedničkou platí následuj vztahy (které nám jistě připadají samozřejmé u skalárů) O 0 • c = c • 0 = 0 pro všechny cg/?, O — c = (—1) • c = c • (—1) pro všechny cg/?, 0 —(c • d) = (—c) • d = c • (—c/) pro všechny c, d g /?, O a ■ (b — c) = a ■ b — a ■ c, Obecně říkáme, že a £ R dělí cg/?, jestliže existuje b tak, že a ■ b = c. Skutečnost, že c g R je dělitelné a g 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- cab^Q, pak c je jednoznačně dáno volbou a, b. Důkaz. Pro a = bc = bc' totiž platí 0 = b • (c — c') a b ^ 0, proto c = c'. □ Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost ooooo»oooooooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Dělitelé jedničky, tj. invertibilní prvky v /?, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. Netriviální (komutativní) okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá (komutativní) 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). Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooo«ooooooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Typickým příkladem komutativních těles jsou číselné obory Q, M, 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 Mat/((/?) 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ů h = {a + b ■ i + c - j + d ■ k; a, b, c, d g R}, se sčítáním po složkách a násobením odvozeným ze základních relací i2 = j2 = k2 = —1, ij = —ji = k, jk = —kj = i, k\ = —/7c = j. Věta Každý konečný obor integrity je těleso. Důkaz. Dokazuje se prostřednictvím homomorfismu fa : R —» R, f(x) = a ■ x pro nenulové a (je to injekce, proto surjekce, proto existuje k a inverze, proto je R těleso). □ A co obráceně? Samozřejmě je každé těleso oborem integrity. Zřejmě je např. Z obor integrity, který není těleso. Příklad 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 jakýkoliv (dále vždy) komutativní okruh skalárů. Polynomem nad R rozumíme konečný výraz k f (x) = £ a/x'" kde a,- g R, i = 0,1,..., k, jsou tzv. koeficienty polynomu. Je-li a k ý 0' říkáme, že f[x) má stupeň k, píšeme degf = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v R, kterým říkáme konstantní polynomy. Polynomy f[x) a g(x) jsou stejné, jestliže mají stejné koeficienty. Množinu všech polynomů nad okruhem R budeme značit R[x]. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost ooooooooo»oooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Každý polynom zadává zobrazení (polynomiální funkci) f : R —> R, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj. f(c) = a0 + aic-\-----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 = {a^, a\,..., a^} zadává polynom f(x) = (x — ao)(x — a\)... (x — a^) identicky nulové zobrazení. Zároveň ale platí tvrzení, které dokážeme zanedlouho: 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. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooo»ooooo oooooo Kořeny a rozklady polynomů oooooooooooooooo Dva polynomy f(x) = J2iaix' a áí(x) = J2i ^ix' umíme přirozeně také sčítat i násobit: (f + g)(x) = (a0 + bo) + (ai + b^x + ■ ■ ■ + {ak + bk)xk (f • g)(x) = (a0b0) + ■■■ + {a0be + + ••• + aíbQ)xí + ... kde uvažujeme nulové koeficienty všude, kde v původním výrazu pro polynomy nenulové koeficienty nejsou a u sčítání nechť je k maximální ze stupňů f a g. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů ooooooooooo»oooo oooooo oooooooooooooooo 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 výrazu pro násobení polynomů. Jsou-li f(x) a g(x) polynomy stupně k a í jako výše, pak koeficient u xk+í v součinu f(x) ■ g(x) je součin a^ • b^ a ten musí být nenulový, pokud nejsou dělitelé nuly v R. □ Již dříve 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,- 6 /?,/' = 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. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost ooooooooooooo»oo oooooo Kořeny a rozklady polynomů oooooooooooooooo Často se setkáváme s objekty popsanými pomocí polynomiálních výrazů ale s více proměnnými. Např. kružnici v rovině se středem S = {xo,yo) a poloměrem r zapíšeme pomocí rovnice (x - x0)2 + (y - y0)2 - r2 = 0. Okruhy polynomů v proměnných xi,... ,xr můžeme zavést podobně jako jsme postupovali s R[x]. Místo mocnin jediné proměnné xk budeme uvažovat tzv. monomy a jejich formální lineární kombinace s koeficienty a^...^ g R. Formálně i technicky je ale jednodušší následující induktivní definice. Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů oooooooooooooo»o oooooo oooooooooooooooo Polynomy více proměnných Okruhy polynomů v proměnných xi,... ,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 xi,...,x„ 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_i(x)y"-1 + • • • + a0(x) = {amnxm + ■■■ + a0n)y" + ■■■ + (fap0xp + • • • + b00) = cqq + ci0x + c0iy + c2qx2 + cnxy + cQ2y2 + ■■■ Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost ooooooooooooooo* oooooo Kořeny a rozklady polynomů oooooooooooooooo Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme: Důsledek Jestliže v okruhu R nejsou dělitelé nuly, pak také v okruhu polynomů R[xi,... ,xr] nejsou dělitelé nuly. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost OOOOOOOOOOOOOOOO #00000 Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Naším dalším cílem bude pochopit, jak je to v obecném případě polynomů nad oborem integrity s jejich rozkladem na součin polynomů jednodušších, tj. ve speciálním případě polynomů s jedinou proměnnou budeme diskutovat kořeny polynomů. U polynomů s více proměnnými půjde o rozklad na jednodušší faktory nižších stupňů. Protože již víme, že polynomy ve více proměnných můžeme definovat induktivně, stačí nám nyní uvažovat jen polynomy v jedné proměnné, ovšem nad obecným oborem integrity, a směřujeme ke zobecnění úvah o dělitelnosti, které byly základem našeho počínání v teorii čísel. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo o»oooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Uvažujme proto nějaký pevně zvolený obor integrity /?, třeba celá čísla Z nebo okruh Zp s prvočíselným p. Pak platí: Lemma • 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 a = a ■ e ■ e^1) Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oo»ooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Definice Řekneme, že prvek a g R je ireducibilní [nerozložitelný), jestliže • je nenulový a není jednotkou (tj. afl), » 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\ • 32 ... ar • jsou-li prvky a\,..., ar a b\,..., bs ireducibilní, nejsou mezi nimi žádné jednotky a platí-li a\32 ... ar = b\b2 ... bs, pak je r = s a ve vhodném přeuspořádání platí aj = ejbj pro vhodné jednotky ej (tj. tyto dva rozklady jsou stejné až na poradia asociovanost činitelů). Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo ooo»oo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Příklad O Z, M[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 M[ degg > O a pišme f = a0 + • • • + anxn, g = b0 + • • • + bmxm. Pak na polynom bmf — anxn~m lze použít indukční předpoklad (neboje nulový). Odtud již snadno dostaneme požadované. Jednoznačnost: je-li f = qig + r\ jiné vyjádření, pak O = f — f = (q — q\)g + (r — r\), kde r = r\, nebo deg(r — ri) < degg. První případ je snadný, ve druhém případě, je-li axs člen nejvyššího stupně v q — q\, pak jeho součin se členem nejvyššího stupně v g musí být nulový, tj. a = O, a tedy i q — qi = O = r — r\ a obě vyjádření byla ve skutečnosti stejná. □ Literatura Okruhy a tělesa Dělitelnost a n rozložitelnost Kořeny a rozklady polynomů oooooooooooooooo oooooo •ooooooooooooooo Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů nad obory integrity R. Uvažme polynom f(x) g R[x], degf > 0, a dělme jej polynomem x - b, b g R. Protože je vedoucí koeficient dělitele 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 = 0 nebo degr = 0, tj. r £ 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 oborem integrity (tělesem) R má nejvýše degf kořenů. Zejména tedy zadávají polynomy nad nekonečným oborem integrity stejná zobrazení /?—>/?, právě když jde o stejné polynomy. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Příklad Polynom x3 má nad Zs čtyři kořeny ([0]s, [2]8, [4]s, [6]s,)- Je to tím, že tento okruh není oborem integrity (natož 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 £ Zx tak, že jeho mocniny generují celou grupu Zx. Důkaz. Buď H <{KX, •), \H\ = n. Pak řád každého h g H je dělitelem n. Označíme-li pro každé d | n všechny prvky H řádu d jako Hj, pak \Hd\ < Ed|JHdl = \H\ = a Proto \Hd\ = 0. □ Literatura Okruhy a tělesa Dělitelnost a ner jzložitelnost Kořeny a rozklady polynomů oooooooooooooooo oooooo oo»ooooooooooooo Násobr íé kořeny Platí-li pro k > 1, že dokonce (x — b)k\f, kde k je největší možné (tj. (x — b)k+1 )(f), říkáme, že kořen b je násobnosti k. Polynom h je největší společný dělitel dvou polynomů 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) Nechť R je těleso a nechť f,g£ R[x]- Psk existuje největší společný dělitel h polynomů f a g. Polynom h je určený jednoznačně, až na násobek nenulovým skalárem. Přitom existují polynomy A, B g R[x] takové, že h = Af + Bg. Důkaz. Euklidův algoritmus Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Důkaz následujícího tvrzení je poměrně technický a nebudeme jej prezentovat v detailech (i když jsme si vše potřebné pro něj již v podstatě připravili). Věta Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[x] je obor integrity s jednoznačným rozkladem. Příklad Z[x],Zs[x] jsou okruhy s jednoznačným rozkladem. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů oooo»ooooooooooo Důsledkem této věty je skutečnost, že každý polynom nad komutativním okruhem s jednoznačným rozkladem můžeme rozložit tak, jak to známe s polynomy s reálnými nebo komplexními koeficienty. Pokud má polynom tolik kořenů, včetně násobnosti, jako je jeho stupeň deg f = k, je odpovídající rozklad tvaru f(x) = b ■ (x - 3i) • (x - a2)... (x - ak). Zatímco reálné polynomy mohou být i úplně bez kořenů, každý komplexní polynom naopak takovýto rozklad připouští. To je obsahem tzv. základní věty algebry1: Věta (Základní věta algebry) Těleso komplexních čísel C je tzv. algebraicky uzavřené, tj. každý nekonstatnípolynom má v C kořen. 1Wikipedia: „This fact has led some to remark that the Fundamental Theorem of Algebra is neither fundamental, nor a theorem of algebra." Okruhy a tělesa Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů oooooooooooooooo oooooo ooooo»oooooooooo Hledání kořenů a ireducibilita Věta (Gaussovo lemma) Polynom f g Z [x] nazveme primitivní, jsou-li jeho koeficienty nesoudělné. O Součin primitivních polynomů je primitivní. O Je-li polynom f g Z [x] ireducibilní nad Z, pa/c _/e rovněž ireducibilní jakožto polynom nad q. Důsledek \/2 nen/ racionálni číslo. Věta Ma-// polynom f (x) = anxn + • • • + 3q g Z [x] racionální kořen r/s g q v základním tvaru, pak r\ao a s\an. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů oooooo»ooooooooo Příklad » Dokažte, že x3 -3x- 1 g q[x] je ireducibilní. • Dokažte, že x3 -3x- 1 g 2^[x] je ireducibilní. Věta (Eisensteinovo kritérium ireducibility) "* Je-li f(x) = anxn + • • • + a\x + ao g Z[x], přičemž: • p | a0,... ,pn_i,pf a„ « P2 t a0- Pak je f ireducibilní nad Z (a tedy i nad Q). Důsledek Nad okruhem Z existují ireducibilní polynomy libovolného stupně. Důkaz. Stačí uvážit fn = xn + 2, který je podle Eisensteinova kritéria (s p = 2) ireducibilní stupně n. □ Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost OOOOOOOOOOOOOOOO oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO 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 (modulo 3), 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 f/(f,n Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Příklad O Určete všechny kořeny polynomu 4x7 - 23x5 + 17x4 + 31x3 - 49x2 + 24x - 4. O Určete všechny kořeny polynomu 12x7 - 44x6 + 35x5 - 4x4 + 44x3 - 31x2 - 4x + 4. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Jako důsledek definice polynomů více proměnných 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[xi,... ,xr] nejsou dělitelé nuly. O Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[xi,...,xr] je obor integrity s jednoznačným rozkladem. Příklad Z[x,y] je okruh s jednoznačným rozkladem. olyno Definice Polynom f g R[xi,... ,xn], 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 si = xi +x2 H-----hx„, s2 = xix2 + xix3 H-----h xn_ixn, 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 si,..., s„. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Pro zjednodušení zápisu si zavedeme tzv. multiindexovou symboliku. Multiindex a délky r je r-tice nezáporných celých čísel («1,..., ar). Celé číslo \a\ = a\ + • • • + ar nazýváme velikost multiindexu a. Stručně místo x^x^2 .. .xfr píšeme xa . Důkaz. Symetrický polynom P je součtem monomů tvaru cx^x^ ■ ■ ■ x£, tyto si uspořádejme reverzně lexikograficky (tj. rozhoduje exponent u xi<, pak Xk-i, atd.) sestupně podle exponentů (multiindexu). Polynom P zapíšeme pomocí elementárních tak, že postupně redukujeme největší monomy (vzhledem k tomuto uspořádání). Nechť je cx^x^ • • • x'£ největší monom, pak \\ < i2 < • • • < ik a uvažme Q = csl s2 Sk-1 Sk ■ Snadno se vidí, že největší monom Q je též cx'^x'^ • • • x'£, a polynom P — Q je opět symetrický s největším monomem menším než P. Opakováním dostáváme potřebné. □ Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost OOOOOOOOOOOOOOOO oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Důsledek (Viětovy (Newtonovy) vztahy) Vztahy mezi kořeny a koeficienty polynomu f(x) = x" + an_ix"_1H-----haix+a0 = (x-xi)-(x-x2) • • • (x-x„); an-i = -(xi H-----hxn) = -si 3,7-2 = XlX2 H-----h Xn_iX„ = S2 a0 = (-!)"• xi... x„ = (-!)"• sn Příklad Určete polynom s kořeny O x2,x|, O w XI ' X2 ' jsou-li xi,X2 kořeny polynomu x2 + 13x + 7 (aniž byste je vyčíslovali). Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOOO Naší snahou nyní bude zobecnit způsob konstrukce racionálních čísel jakožto zlomků čísel celých. Nechť R je obor integrity. Jeho podílové těleso (Ring of Fractions) definujeme jako třídy ekvivalence dvojic (a, b) £ R x R, b ^ 0, které zapisujeme |, a ekvivalence je dána 3- = Í- & ab' = a'b. b b' Sčítání a násobení definujeme prostřednictvím reprezentantů tříd a c ad + bc ~b + ~ď~ bd a c ac ~bd~~bď Snadno se ověří korektnost této definice a všechny axiomy tělesa. Zejména je j neutrální prvek vzhledem ke sčítání, j je neutrální prvek vzhledem k násobení a pro a 7^ 0, b 7^ 0 je = j. Literatura Okruhy a tělesa Dělitelnost a nerozložitelnost oooooooooooooooo oooooo Kořeny a rozklady polynomů OOOOOOOOOOOOOOO* Touto konstrukcí „přidáme" k okruhu R minimální množství prvků tak, abychom již mohli dělit libovolnými nenulovými prvky. Příklad Podílové těleso okruhu R[xi,... ,xr] nazýváme těleso racionálních funkcí a značíme je R(xi,... ,xr). Všechny algebraické operace s polynomy v softwarových systémech jako je Maple nebo Mathematica jsou prováděny ve skutečnosti nad podílovými tělesy, tj. v tělesech racionálních funkcí, zpravidla s použitím R = Q.