Okruhy polynomů Ondřej Klíma Okruhy polynomů - p.1/31 Polynomy Př: / = 4x5 - x3 + 7x2 + 1 Co je to polynom? anx + an-\x + • • • + a\x + ao? kde n g N ("stupeň") a an, an_i,..., ai, a0 g R (koeficienty). Definice? Oblíbený způsob: formální součet. Uděláme jinak. Reprezentace? Konečná posloupnost koeficientů. Př: / = (4,0, -i, 7,0, l). Technické potíže — např. sčítání. Standardní trik: nekonečná posloupnost s konečným počtem nenulových čísel, (l, 0,7, -i, 0,4,0,0,0,...) Okruhy polynomů - p.2/31 Nechť (i?, +, ) je okruh. Polynom nad okruhem R definujeme jako nekonečnou posloupnost / = (/o, A, Í2, • • •), kde fi g R pro i e N0, takovou, že množina {i e N0 | ^ 0} je konečná. Ekvivalentní vyjádření poslední podmínky je: (3n g N)(Vi > n)(fi = 0) Prvky /o, /i,... nazýváme koeficienty polynomu /. Množinu všech polynomů nad okruhem R označujeme symbolem R[x]. Okruhy polynomů - p.3/31 Příklady 4ar x3 + 7x2 + 1 A t* 5 J- t*3 _i_ 8/^2 _ 1^ 4x4 - VŠX3 + 7tx2 + 1 2x4 - (1 + Í)X3 + 7TX2 + Z (1,0,7,-1,0,4,0,0,...) (4,0,§,1,0,4,0,0,...) (l,0,7r,-V3,4,0,0,...) (z,0,7r,-l-z,4,0,0,...) Jednoduché pozorování: R c s => R[x] c 5[x]. Co "polynomy" m x + zx + 3x + ž -» x4 + x3 + 4x3 + x2 + 5x2 - 3x2 + x + 9x + 1 Okruhy polynomů - p.4/31 polynomy nad Z7 polynomy nad maticemi 5 2\ „ ÍO ()\ (10 R triviální okruh =^ existuje jediný polynom Okruhy polynomů - p.5/31 "Divoký" příklad A = {a,6,c}. Okruh (P(A),^-,n); 0 neutrální prvek vzhledem k tj. 0; A neutrální prvek vzhledem k n. Polynom / = ({a}, 0, {c}, {a, 6, c}, 0,0,...); / =----h 0x4 + {a, 6, c}x3 + {c}x2 + 0x + {a}; / = {a, 6, c}ílx3Ť {c} ni2T {a}. Co dál s polynomy? Cíl je definovat operaci "sčítání" polynomů. Tato operace musí v naší interpretaci odpovídat "skutečnému" sčítání. Stejně tak pro násobení, tj. např. x2 = x • x. Okruhy polynomů - p.6/31 Buď / = (/o, /i, • • •) a g = (so,91, ■ - ■) polynomy nad R. Očekáváme (• • • fnXn + • • • + fIX + A) + (• * * ^ + • * • + 01* + 9o) = • • • (jn + Sn)*" + • ' • + (/l + 9l)x + (A + PO) Pro f ag polynomy nad R definujeme polynom f+ 9 vztahem (/ + g)k = fk + gk pro k e N0. Okruhy polynomů - p.7/31 Definice součinu polynomů Buď / = (/o, fu • • •) a g = (#0, gi,...) polynomy nad R. Očekáváme (• • • fnxn H-----h fix + /o) • (• • • H-----h gix + #0) = • • • (Í2#0 + figi + /O^)^2 + (/l#0 + /o£l)z + /o^O (/■#)*; = /i"^-* (*) i=0 Pro / a g polynomy nad R definujeme polynom / • g vztahem (*) pro k e N0. Okruhy polynomů - p.8/31 v^^#^.m. •^^^ | %*. 1114 -L Kj ^tAJ Věta. Buď •) okruh. Pokud na množině R[x] definujeme operace + a • vztahy i) {f + g)k = fk + 9k pro/cg N0, ii) (/ • g)k = Eto fi-9k-i Pro k g No, pak •) je okruh. Je-li (R, +, •) komutativní okruh, pak (#[#],+, •) je také komutativní okruh. (R[x\, +, ) se nazývá okruh polynomů nad okruhem Okruhy polynomů - p.9/31 Konstantní polynomy Neutrální prvek vzhledem k + je polynom (0,0,0,0,...); tzv. nulový polynom. Neutrální prvek vzhledem k • je polynom (i, 0,0,0,...). Polynomy tvaru (a, 0,0,0,...), kde a g R, se nazývají konstantní polynomy. Zobrazení k : iž —► R[x] dané vztahem k(á) = (a, 0,0,0,...), pro a g i? je prostý homomorfismus okruhů. Konstantní polynomy můžeme tedy ztotožnit s prvky okruhu R a chápat R jako podokruh okruhu R[x\. Okruhy polynomů - p.10/31 Stupeň nenulového polynomu / je největší číslo n e N0 takové, že fn ^ 0. (Označujeme st(/).) Koeficienf fn se nazývá vedoucí koeficient polynomu /. Lineární, kvadratické, kubické polynomy. Polynom x (0,1,0,0,0,...) Označme polynom (0, l, 0,0,0,...) g R[x] symbolem x. Pak 3 x1 = x • x = (0,1,0,0,...) • (0,1, 0, 0,...) = (0,0,1,0,0,...) 3 x3 = (0,0,0,1,0,0,0,...) 3 a ■ x2 = (a, 0,...) • (0,0,1,0,...) = (0, 0, a, 0,0,...) Okruhy polynomů - p.11/31 Vyjádření polynomu pomocí x Věta. Buď (R, +, •) okruh a / g R[x] polynom stupně n. Pak platí / = fn-xn + /„ ,,r"" 1 + • • • + fyx + /o, kde koeficienty /0, /i,..., /n-i, /n chápeme jako konstantní polynomy v a operace +, • jsou operacemi okruhu (Ä[x],+,-). Cíl je splněn: polynom / = (/o, /i,..., /n-i, /n, 0,0,...) můžeme zapisovat ve tvaru / = Jn^ + + • • • + /i* + /o. Okruhy polynomů - p.12/31 Polynom — nekonečná posloupnost prvků e R (skoro všechny = 0) 3 Na množině všech polynomů se definují operace + a •. 3 Ukáže se, že (#[#],+, •) je okruh. ^ Při označení a = (a, 0,0,...), x = (0, i, 0,0,...) lze pak každý polynom (/0, fu..., /„, 0,0,...) psát ve tvaru f = fn-xn + fn-i ■ xn~l + • • • + h ■ x + /0. 3 Pozn. V předchozím jsou + a • korektně definované operace na množině všech polynomů R[x\. 3 Co dál? Rozklad polynomů na "prvočinitele". Okruhy polynomů - p.13/31 Rozklad na prvočinitele v Z ra = ±1 - pí -p2Pfc, kde pi prvočísla; jednoznačnost. Důkaz — hlavní body 3 m není prvočíslo, pak m rozložíme na součin "menších" 3 proces rozkládání se zastaví jednoznačnost vi-V2.....Vk = qi • qi=Pi pro vhodné i * lemma: q \ a • 6, (g, a) = 1 =>■ q I b m Bezoutova rovnost .» Euklidův algoritmus 3 dělení se zbytkem Okruhy polynomů - p. 14/31 Postup: definice dělení (v libovolném komutativním okruhu) a | b (3c) b = c - a m "porovnávání" prvků m dělení se zbytkem Euklidův algoritmus (Bezoutova rovnost) m ireducibilní prvky (nerozložitelné) Pozn: dělitelnost v tělesech Q, R, C Prvky se navzájem dělí a, b e Q, a, b ^ 0 =^ 6 = (6a_1) - a, a = (a6_1) • 6 tzn. a | 6, 6 | a. Okruhy polynomů - p.15/31 Dělení a invertibilní prvky okruhu Nechť e je invertibilní prvek komutativního okruhu a b = e • a, pak a = e_1 • (ea) = e_1 -6, tj. a \ b, b | a. Příklad v Q [x]: f = 2x3 + x2 + x + i / = (x2 + i) • (2x + 1) = (2x2 + 1) • (x + i) f = 2-{x2 + \)-{x + \) Budeme chtít vědět jak vypadají invertibilní prvky v R[x]. Nenulový polynom se nazývá normovaný, je-li jeho vedoucí koeficient l. Okruhy polynomů - p.16/31 Jak porovnávat polynomy při rozkládání? Př: x3 + 1 = (x + 1) • {x2 - x + 1); polynomy (x + l) a (x2 - x + l) mají menší stupeň. Věta. Buď (R, +, •) okruh. Pak pro libovolné dva polynomy f,g z R[x] platí st(/ + g) < max{st(/), st(#)} a st(f-g) < st(/) + st(g). Je-li navíc (R, +, •) obor integrity, pak ve druhé nerovnosti platí vždy rovnost. Definice stupne — doplnení Okruhy polynomů - p. 17/31 Př: polynomy nad Z4: 2x ■ 2x = 0 (2x + 1) • (2x + 1) = 1 Pro nulový polynom 0 = (0,0,0,...) klademe jeho stupeň rovný -oo. Přičemž: —oo < n (—oo) + (—oo) = (—oo) + n = n + (—oo) = — oo pro všechna n g N0. St(/-0) st(p) indukcí vzhledem k st(/) Př: / = 3x4 + 2x3 - x2 + 1, 0 = 2x2 + 2x - 3 pak q = §x2 3x4 + 2x3 - x2 + 1 = (2x2 + 2x - 3) • §x2+? = 3x4 + 3x3 - §x2+? = 3x4 + 3x3 - §x2 + {-x3 + |x2 + 1) Polynom (-x3 + \ + l) má menší stupeň než /. -x3 + |x2 + 1 = (2x2 + 2x - 3) • ^x+ (|x2 - |x + 1) |x2 - \x + 1 = (2x2 + 2x - 3) • |+ (-6x + ^) Celkem / = (2x2 + 2x - 3) • (|x2 - ±x + f) + (-6x + f) Okruhy polynomů - p.21/31 Jednoznačnost při dělení m g-q + r = g-q' + r' g • {q — q') = r' — r, kde st(r' — r) < st(g) g No st(g) + st(g — ŕ/) = st(r/ — r) Odtud st(g — q') = st(r/ — r) = —oo r' — r = 0, tj. r = r' g — q' = 0, tj. g = q' Okruhy polynomů - p.22/31 UVI T ťkJl tJ J Polynom /i g R[x] se nazývá společný dělitel polynomů f, g e R[x], jestliže h \ f a také /i | g. Polynom d g R[x] se nazývá největší společný dělitel f, g e R[x], jestliže je společný dělitel f a g a všechny ostatní společní dělitelé jej dělí. Tj. d I /, d I g a (V/i g R[x])(h \ f A h \ g =^ h \ d). Polynomy nad Z4: m f = 2x = 2 • (x + 2), # = x2 + 2x = x • (x + 2). Vidíme, že x i x + 2 jsou společní dělitelé f, g. Neexistuje největší společný dělitel f a g. Existence n.s.d v R Okruhy polynomů - p.23/31 X Věta. Nechť (R, +, •) je těleso a f, g e R[x] polynomy z nichž alespoň jeden je nenulový. Pak 3 existuje největší společný dělitel f a g; m je-li d největší společný dělitel f, g, pak každý největší společný dělitel je tvaru a • d, kde a je konstantní nenulový polynom; * existuje jediný normovaný největší společný dělitel polynomů / a g. Značíme (/,#), případně nsd(/,#). Klademe (0,0) = 0 (není normovaný). Dále (/, 0) = f~l • f, pro / nenulový polynom stupně n. Okruhy polynomů - p.24/31 Existence — Euklidův algoritmus: / = #-9o + n), st(r0) < st(#), 9 = r0-qi + ri, st(ri) < st(r0), = + r2, st(r2) < st(ri), rn-2 = rn-vqn + rn, st(rn) < st(rn_i), Kde rn je n.s.d — nemusí být normovaný. Bezoutova rovnost — stejně jako v Z: rn = rn-2 + rn-i • (-qn) = rn_2 + (rn_3 - rn_2 • qn-i) • (-g™) = Okruhy polynomů - p.25/31 Poznámky k popisu všech n.s.d Pokud d, h dva největší dělitelé /, g, pak se navzájem dělí. Tj. existují a, 6 G tak, Že d = a • h, h = b • d. Celkem d = a-b- d. Odtud (po diskusi zda něco není nulový polynom) krácením (R[x] je obor integrity) dostaneme 1 = a • b. Oba dva důkazy — skripta. Tamtéž Bezoutova rovnost a její důsledek f\g-h,(f,q) = l f\h. Okruhy polynomů - p.26/31 Polynom / e R[x] je ireducibilní nad R, jestliže / je nekonstantní a nelze rozložit na součin dvou nekonstantních polynomů. 3 Každý lineární polynom (nad oborem integrity) je ireducibilní. m Polynom 2x + 2 není ireducibilní nad Z4; 2x + 2 = (2x + 2)(2x + l). 3 Polynom x3 - 2 je ireducibilní nad Q, ale není ireducibilní nad R a C; x3 - 2 = {x - ^2)(x2 + ^2x + ^4) — příště. Jednoznačný rozklad v R Okruhy polynomů - p.27/31 X Věta. Buď (i?, +, •) těleso. Pak pro každý nenulový polynom / g R[x] existují normované polynomy pi,p2, • • • ,Pk e ireducibilní nad R a konstantní polynom a e tak, že Tento rozklad polynomu / je jediný až na pořadí činitelů. Hovoříme o okruhu s jednoznačným rozkladem Okruhy polynomů - p.28/31 M. VS^Jlťl T 111 Vil T V/1% T 1^1 11uuv1 Okruh Gaussových celých čísel G je okruh s jednoznačným rozkladem. G = {a + bi | a, b G Z} Porovnávání — pomocí normy: 7V(a + bi) = (a + 6z) • (a - bi) = a2 + b2 G N0. PlatíAf(x-2/) = Af(x)-A%). Odtud plyne, že pro invertibilní prvkek x musí platit AT (x) = 1, tj. invertibilní prvky jsou 1, -1, z, -z. Lze dělit se zbytkem (není jednoznačně určen). Př: 5 + 5z = 3 • (2 + i) + (-1 + 2z) = 3 • (1 + 2z) + (2 - z), kde pro zbytky platí N(-l + 2i) = N (2 - i) = 5 < 9 = JV(3). Euklidův algoritmus, Bezout, jednoznačný rozklad. Př: 5 = (i + 2i)(l - 2i). N(x) prvočíslo =^ x invertibilní. Okruhy polynomů - p.29/31 Negativní "divoký" příklad Okruh {a + biy/Š | a,b g Z} není okruh s jednoznačným rozkladem. Norma tentokrát N (a + bi\/E) = a2 + 5b2, invertibilní prvky ±l. Př: 9 = 3 • 3 = (2 + 1 • iy/Š) • (2 - 1 • iy/E), kde 3, 2 + iy/Š i 2-zVŠ ireducibilní, neboť AT(3) = AT (2 ± zVŠ) = 9 a neexistuje prvek s normou 3. Taktéž neexistuje (9,3 • (2 + iy/5), protože mezi společné dělitele patří 3 i 2 + iy/Š. Okruhy polynomů - p.30/31 11UU Co se bude požadovat: 3 vlastnosti •), 3 rozkládání polynomů — příště, 3 hlavní věty (tučné), 3 základní pojmy — stupeň, ved. koef., ireduc. pol., ... prakticky Euklides, Bezout — nad tělesy. Co se nebude požadovat: "divoké" příklady, tj. rozklady mimo R[x]. Okruhy polynomů - p.31/31