Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných OOOO Podílová tělesa 00 Matematika IV - 5. přednáška Okruhy a tělesa, okruhy polynomů Michal Bulant Masarykova univerzita Fakulta informatiky 20. 3. 2013 Dělitelnost a neroz ložitelnost Kořeny a rozklady polynomů Polynomy vm :e proměnných Podílo\ 'á těl oooo ooooooooo OOOO 00 Ql Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů Q Polynomy více proměnných Q Podílová tělesa Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných OOOO Podílová tělesa 00 • Martin Panák, Jan Slovák, Drsná matematika, e-text. • 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/ Dělitelnost a nerozložitelnost •ooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných oooo Podílová tělesa 00 Směřujeme nyní ke zobecnění rozkladů polynomů na ireducibilní polynomy 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 -4=>- 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 • O = 0); • každý prvek a G /? 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) Dělitelnost a nerozložitelnost o»oo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných oooo Podílová tělesa 00 Ř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|/> a fa|a; značíme a ~ fa). Ř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 a\32 ... ar = b\bi... 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ů). Dělitelnost a nerozložitelnost oo»o Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných oooo Podílová tělesa 00 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[ O, 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 = O nebo str = O, 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 tělesem R má nejvýše st f kořenů. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů o»ooooooo Polynomy více proměnných OOOO Podílová tělesa 00 ' Příklad ^ Polynom x3 má nad Zs 4 kořeny ([0]s, [2]8, [4]8, [6]8,)- Je to tím, že tento okruh není oborem integrity (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 G Z£ tak, že jeho mocniny generují celou grupu Z*. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů oo»oooooo Polynomy více proměnných OOOO Podílová tělesa 00 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. Dva polynomy nad nekonečným tělesem, 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é těleso, pak dva polynomy f(x) a g(x) nad R jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooo»ooooo Polynomy více proměnných OOOO Podílová tělesa 00 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) Necht R je těleso a necht 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. □ - Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů oooo»oooo Polynomy více proměnných OOOO Podílová tělesa 00 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. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooo»ooo Polynomy více proměnných OOOO Podílová tělesa 00 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ň st 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." Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných Podílová tělesa oooo oooooo»oo oooo oo Hledání kořenů a ireducibilita Věta (Gaussovo lemma) Je-li polynom f G Z[x] ireducibilní nad Z, pak je rovněž ireducibilní jakožto polynom nad Q. Důsledek V2 není racionální číslo. Věta Má-li polynom f(x) = anxn + • • • + a$ G Z[x] racionální kořen r/s G Q v základním tvaru, pak r\a$ a s\an. Příklad • Dokažte, že x3 — 3x — 1 G Q[x] je ireducibilní. • Dokažte, že x3 — 3x — 1 G 2^[x] je ireducibilní. Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných Podílová tělesa oooo ooooooo»o oooo oo Hledání kořenů a ireducibilita, pokr. Věta (Eisensteinovo kritérium ireducibility) Je-li f(x) = anxn + • • • + a\x + 3o £ Z[x], přičemž: • p | a0,... ,pn_i,pf an « 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. □ Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů 00000000» Polynomy více proměnných OOOO Podílová tělesa 00 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 Dělitelnost a nerozložitelnost Kořeny a rozklady polynomů Polynomy více proměnných Podílová tělesa oooo ooooooooo »ooo oo 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 + ■■■ Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných 0900 Podílová tělesa 00 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[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. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných oo»o Podílová tělesa 00 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, Sn — X\ xn 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„. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných 0009 Podílová tělesa 00 Důsledek (Viětovy (Newtonovy) vztahy) Vztahy mezi kořeny a koeficienty polynomu f{x) = x" = a„-1x"-1 + - ■ -+31X+30 = (x- xi)-(x-x2) • • • (x-x„); an-i = -(xi H-----hxn) = - -si 3,7-2 = XlX2 H-----hXn_iX„ = s2 30 = (-1)" -Xi . . .X„ = (- -i)n-sn Příklad Určete polynom s kořeny O *i,x22, O w XI ' X2 ' jsou-li xi,X2 kořeny polynomu x2 + 13x + 7 (aniž byste je vyčíslovali). Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných OOOO Podílová tělesa •O 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 ^ 0, b ^ 0 je = j. Dělitelnost a nerozložitelnost oooo Kořeny a rozklady polynomů ooooooooo Polynomy více proměnných OOOO Podílová tělesa O* 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). Touto konstrukcí „přidáme" k okruhu R minimální množství prvků tak, abychom již mohli dělit libovolnými nenulovými prvky.