Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Matematika IV – 7. týden Okruhy polynomů a tělesa Jan Slovák Masarykova univerzita Fakulta informatiky 1. 4. – 4. 4. 2013 Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Obsah přednášky 1 Okruhy 2 Polynomy 3 Dělitelnost a nerozložitelnost 4 Polynomy více proměnných 5 Podílová tělesa Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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, komplexní čísla C) a množiny polynomů nad takovými skaláry K. Definition Komutativní grupa (M, +) s neutrálním prvkem 0 ∈ M, spolu s další operací · splňující (a · b) · c = a · (b · c), pro všechny a, b, c ∈ M; a · b = b · a, pro všechny a, b ∈ M; existuje prvek 1 takový, že pro všechny a ∈ M platí 1 · a = a; a · (b + c) = a · b + a · c, pro všechny a, b, c ∈ M; se nazývá komutativní okruh. Jestliže v okruhu K platí c · d = 0 právě, když alespoň jeden z prvků c a d je nulový, pak nazýváme okruh K oborem integrity. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Poslední vlastnosti v našem výčtu axiomů okruhu se říká distributivita. Pokud neplatí vlastnost komutativity operace ·, hovoříme o (nekomutativním okruhu). V dalším se ovšem 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 Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Obecně říkáme, že a ∈ K dělí c ∈ K, jestliže existuje b tak, že a · b = c. Skutečnost že c ∈ K je dělitelné a ∈ K 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ů: je-li b = a · c a b = 0, pak c je jednoznačně dáno volbou a, b. Pro b = ac = ac totiž platí 0 = a · (c − c ) a a = 0, proto c = c . Dělitelé jedničky, tj. invertibilní prvky v K, 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. Komutativní těleso se také nazývá pole. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Typickým příkladem komutativních okruhů, tj. polí, jsou číslené obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Dobrým příkladem nekomutativního okruhu s jedničkou je množina Matk(K) všech čtvercových matic nad okruhem K s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Jako příklad nekomutativního tělesa uveďme těleso kvaternionů H. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa V každém komutativním okruhu K s jedničkou platí následující vztahy (které nám jistě připadají samozřejmé u skalárů) 1 0 · c = c · 0 = 0 pro všechny c ∈ K, 2 −c = (−1) · c = c · (−1) pro všechny c ∈ K, 3 −(c · d) = (−c) · d = c · (−d) pro všechny c, d ∈ K, 4 a · (b − c) = a · b − a · c, 5 celý okruh K je triviální množinou {0} = {1} právě, když 0 = 1. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Polynomem rozumíme jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků K a jedné neznámé proměnné pomocí operací sčítání a násobení: Definition Nechť K je jakýkoliv komutativní okruh skalárů s jedničkou. Polynomem nad K rozumíme konečný výraz f (x) = k i=0 ai xi kde ai ∈ K, i = 0, 1, . . . , k, jsou tzv. koeficienty polynomu. Je-li ak = 0, říkáme, že f (x) má stupeň k, píšeme deg f = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v K, kterým říkáme konstantní polynomy. Polynomy f (x) a g(x) jsou stejné, jestliže mají stejné nenulové koeficienty. Množinu všech polynomů nad okruhem K budeme značit K[x]. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Každý polynom zadává zobrazení f : K → K, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj. f (c) = a0 + a1c + · · · + akck . Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Kořen polynomu f (x) je takový prvek c ∈ K, pro který je f (c) = 0 ∈ K. Obecně mohou různé polynomy definovat různá zobrazení. Např. polynom x2 + x ∈ Z2[x] zadává identicky nulové zobrazení. Obecněji, pro každý konečný okruh K = {a0, a1, . . . , ak} zadává polynom f (x) = (x − a0)(x − a1) . . . (x − ak) identicky nulové zobrazení. Zároveň ale platí tvrzení, které dokážeme zanedlouho: Theorem Jestliže je K nekonečný okruh, pak dva polynomy f (x) a g(x) nad K jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Dva polynomy f (x) = i ai xi a g(x) = i bi xi umíme přirozeně také sčítat i násobit: (f + g)(x) = (a0 + b0) + (a1 + b1)x + · · · + (ak + bk)xk (f · g)(x) = (a0b0) + · · · + (a0b + + · · · + a b0)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. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f , g : K → K, díky vlastnostem „skalárů“ v původním okruhu K. Přímo z definice vyplývá, že množina polynomů K[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v K[x] je opět jednička 1 v okruhu K 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 K[x] mohou být netriviální dělitelé nuly pouze, jetliže jsou už v K. 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 ak · b a ten musí být nenulový, pokud nejsou dělitelé nuly v K. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Směřujeme nyní ke zobecnění rozkladů polynomů nad číslenými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu K samotném. Uvažujme proto nějaký pevně zvolený obor integrity K, třeba celá čísla Z nebo okruh Zp s prvočíselným p. je-li a|b a zároveň b|c pak také a|c; a|b a zároveň a|c pak také a|(αb + βc) pro všechny α, β ∈ K; a|0 pro všechny a ∈ K (je totiž a · 0 = 0); každý prvek a ∈ K je dělitelný všemi jednotkami e ∈ K a jejich násobky a · e (jak přímo plyne z existence e−1) Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Řekneme, že prvek a ∈ K je nerozložitelný, jestliže je dělitelný pouze jednotkami e ∈ K a jejich násobky a · e. Řekneme, že okruh K je obor integrity s jednoznačným rozkladem, jestliže platí: pro každý nenulový prvek a ∈ K existují nerozložitelné a1, . . . , ar ∈ K takové, že a = a1 · a2 . . . ar jsou-li prvky a1, . . . , ar a b1, . . . , bs nerozložitelné, nejsou mezi nimi žádné jednotky a a = a1a2 . . . ar = b1b2 . . . bs, pak je r = s a ve vhodném přeuspořádání platí aj = ej bj pro vhodné jednotky ej . Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Example 1 Z je obor integrity s jednoznačným rozkladem. 2 Každé pole (komutativní těleso) je obor integrity s jednoznačným rozkladem (a každý nenulový prvek je jednotka). 3 Nechť K má prvky tvaru a0 + k i=1 ai 2ni √ xmi kde a0, . . . , ak ∈ Z, mi , n ∈ Z>0. Pak jednotky jsou pouze prvky ±1, všechny prvky s a0 = 0 jsou rozložitelné, ale např. výraz x nelze vyjádřit jako součin nerozložitelných. (Nerozložitelných je zde příliš málo.) Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Z je 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 (Algoritmus pro dělení se zbytkem) Nechť K je komutativní okruh bez dělitelů nuly a f , g ∈ K[x] polynomy, g = 0. Pak existuje a ∈ K, a = 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo deg r < deg g. Je-li navíc K pole, 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 Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f (x) ∈ K[x], deg f > 0, a dělme jej polynomem x − b, b ∈ K. 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 = 0 nebo deg r = 0, tj. r ∈ R. Tzn., že hodnota polynomu f v b ∈ K je rovna právě f (b) = r. Proto je prvek b ∈ K 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í: Corollary Každý polynom f ∈ K[x] má nejvýše deg f kořenů. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Dva polynomy nad nekonečným komutativním okruhem, které zadávají stejné zobrazení K → K, mají rozdíl, jehož kořenem je každý prvek v K. Protože rozdíl polynomů má jen konečný stupeň, pokud není nulový, dokázali jsme tak již dříve uvedené tvrzení: Theorem Jestliže je K nekonečný okruh, pak dva polynomy f (x) a g(x) nad K jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Polynom h je největší společný dělitel dvou polynomů a f a g ∈ K[x] jestliže: h|f a zároveň h|g jestliže k|f a zároveň k|g pak také k|h. Theorem (Bezoutova rovnost) Nechť K je pole a nechť f , g ∈ K[x]. Pak 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 ∈ K[x] takové, že h = Af + Bg. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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). Theorem Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x] je obor integrity s jednoznačným rozkladem. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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) = (x − a1) · (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 algebry: Theorem (Základní věta algebry) Pole C je algebraicky uzavřené, tj. každý polynom stupně alespoň 1 má kořen. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Okruhy polynomů v proměnných x1, . . . , xr definujeme induktivně vztahem K[x1, . . . , xr ] := K[x1, . . . , xr−1][xr ]. Např. K[x, y] = K[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem K[x]. Snadno se ověří, že polynomy v proměnných x1, . . . , xr lze chápat jako výrazy vzniklé z písmen x1, . . . , xn a prvků okruhu K konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v K[x, y] jsou tvaru f = an(x)yn + an−1(x)yn−1 + · · · + a0(x) = (amnxm + · · · + a0n)yn + · · · + (bp0xp + · · · + b00) = c00 + c10x + c01y + c20x2 + c11xy + c02y2 + . . . Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme: Corollary 1 Jestliže v okruhu K nejsou dělitelé nuly, pak také v okruhu polynomů K[x1, . . . , xr ] nejsou dělitelé nuly. 2 Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x1, . . . , xr ] je obor integrity s jednoznačným rozkladem. Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Nechť K je komutativní okruh (s jedničkou) bez dělitelů nuly. Jeho podílové těleso definujeme jako třídy ekvivalence dvojic (a, b) ∈ K × K, b = 0, které zapisujeme a b , a ekvivalence je dána a b = a b ⇔ ab = a b. Sčítání a násobení definujeme prostřednictvím reprezentantů tříd a b + c d = ad + bc bd a b c d = ac bd Snadno se ověří korektnost této definice a všechny axiomy komutativního tělesa. Zejména je 0 1 neutrální prvek vzhledem ke sčítání, 1 1 je neutrální prvek vzhledem k násobení a pro a = 0, b = 0 je a b b a = 1 1 . Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Podílové těleso okruhu K[x1, . . . , xr ] nazýváme těleso racionálních funkcí a značíme je K(x1, . . . , 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 raciolnálních funkcí, zpravidla s použitím K = Q.