Matematick´y ustav ´ Slezske´ univerzity v Opaveˇ Uˇcebn´ı texty k pˇrednaˇ ´ sce ALGEBRA II, letní semestr 2000/2001 Michal Marvan
15. Polynomy Polynom jedn´e neurˇcit´e x nad polem P je v´yraz tvaru am x m + am−1 x m−1 + · · · + a1 x + a0 ,
(∗)
kde m ∈ N a a0 , . . . , am jsou prvky pole P. Prvek ai ∈ P se naz´yv´a i-t´y koeficient. Koeficient a0 se naz´yv´a absolutn´ı cˇ len. Nulov´e koeficienty v z´apisu (∗) obvykle neuv´ad´ıme; neuveden´e koeficienty ai prostˇe povaˇzujeme je za nulov´e. Tak napˇr´ıklad ze z´apisu (∗) usuzujeme, zˇ e am+1 = 0, am+2 = 0, atd. Polynom, jehoˇz vˇsechny koeficienty ai jsou nulov´e, se naz´yv´a nulov´y polynom a znaˇc´ı se 0. Dva polynomy f = am x m + · · · + a1 x + a0 , g = bn x n + · · · + b1 x + b0 povaˇzujeme za sobˇe rovn´e, jestliˇze se rovnaj´ı jejich koeficienty. Tedy, f = g ⇔ a0 = b0 , a1 = b1 , . . . Stupeˇn polynomu f = am x m + · · · + a1 x + a0 je nejvˇetˇs´ı cˇ´ıslo r takov´e zˇ e ar = 0. Znaˇc´ı se deg f . Tud´ızˇ , deg f = r ⇔ ar = 0, ar +1 = 0, ar +2 = 0, . . . . Koeficient ar se pak naz´yv´a vedouc´ı koeficient. Zapisujeme ar = lc f . Podle definice nulov´y polynom nem´a ani stupeˇn ani vedouc´ı koeficient. Nulov´y polynom a polynomy stupnˇe 0 se naz´yvaj´ı konstantn´ı; konstantn´ı polynom a0 m˚uzˇ eme ztotoˇznit s odpov´ıdaj´ıc´ım prvkem a0 ∈ P. Polynomy stupnˇe 1 se naz´yvaj´ı line´arn´ı. Polynomy stupnˇe 2 se naz´yvaj´ı kvadratick´e. Polynomy stupnˇe 3 se naz´yvaj´ı kubick´e. Polynomy stupnˇe 4 se naz´yvaj´ı bikvadratick´e. Mnoˇzina vˇsech polynom˚u neurˇcit´e x nad polem P se znaˇc´ı P[x]. Algebraick´e operace s polynomy se zavedou n´asleduj´ıc´ım zp˚usobem: Definice. Bud’te f = am x m + · · · + a1 x + a0 a g = bn x n + · · · + b1 x + b0 polynomy. Souˇcet polynom˚u f a g je polynom f + g = c p x p + · · · + c1 x + c0 , kde p = max{m, n} a ck = ak + bk , k = 0, . . . , p. Polynom opaˇcn´y k polynomu f je polynom − f = −am x m − · · · − a1 x − a0 . Souˇcin polynom˚u f a g je polynom f g = c p x p + · · · + c1 x + c0 , kde p = m + n a ck = a0 bk + a1 bk−1 + · · · + ak−1 b1 + ak b0 =
ai b j ,
i+ j=k
pro k = 0, . . . , p. V sumˇe se sˇc´ıt´a pˇres vˇsechny dvojice index˚u i, j = 0, . . . , k takov´e, zˇ e i + j = k. Tvrzen´ı. Souˇcin nenulov´ych polynom˚u f, g je nenulov´y polynom a plat´ı deg( f g) = deg f + deg g, lc( f g) = lc f · lc g.
15. Polynomy
Dukaz. ˚ Necht’ lc f = am = 0, lc g = bn = 0, takˇze deg f = m, deg g = n. Pro k > m + n m´ame ck = 0 (zd˚uvodnˇete). Odtud nerovnost deg( f g) ≤ m + n. D´ale cm+n = am bn = 0, a tud´ızˇ f g = 0, lc( f g) = cm+n = lc f · lc g a deg( f g) = m + n = deg f + deg g. Nen´ı tˇezˇ k´e uhodnout, proˇc jsou algebraick´e operace s polynomy zavedeny zp˚usobem pr´avˇe uveden´ym. Jde o souvislost s dosazov´an´ım konkr´etn´ıch hodnot za neurˇcitou x. Je-li f = am x m + · · · + a1 x + a0 ∈ P[x] nˇejak´y polynom a ξ ∈ P libovoln´y prvek, poloˇz´ıme f (ξ ) = am ξ m + · · · + a1 ξ + a0 ∈ P. Tvrzen´ı. Pro libovoln´e polynomy f, g ∈ P[x] a libovoln´y prvek ξ in P plat´ı ( f + g)(ξ ) = f (ξ ) + g(ξ ),
(− f )(ξ ) = − f (ξ ),
( f g)(ξ ) = f (ξ ) g(ξ ).
Dukaz. ˚ Cviˇcen´ı. Definice. Prvek ξ ∈ P se naz´yv´a koˇren polynomu f ∈ P[x], jestliˇze f (ξ ) = 0. O koˇreny n´am p˚ujde pˇredevˇs´ım, pˇredt´ım vˇsak prozkoum´ame algebraick´e vlastnosti polynom˚u. Mnoˇzina P[x] se zaveden´ymi operacemi splˇnuje vˇsechny axiomy pole kromˇe existence inverzn´ıch prvk˚u (nemus´ı existovat prvek a −1 takov´y, zˇ e aa −1 = 1 kdykoliv a = 0). Odpov´ıdaj´ıc´ı algebraick´a struktura se naz´yv´a okruh (pln´ym jm´enem komutativn´ı asociativn´ı okruh s jedniˇckou, ale o jin´ych okruz´ıch pojedn´avat nebudeme).
Definice. Okruh je mnoˇzina, ˇreknˇeme R, spolu s a) bin´arn´ı operac´ı R × R → R, (a, b) → a + b; naz´yv´a se sˇc´ıt´an´ı; b) bin´arn´ı operac´ı R × R → R, (a, b) → a · b; naz´yv´a se n´asoben´ı; c) dvˇema vybran´ymi prvky 0 a 1 ∈ R; naz´yvaj´ı se nula a jedniˇcka; d) zobrazen´ım R → R, a → −a; prvek −a se naz´yv´a opaˇcn´y k prvku a; Pˇritom je poˇzadov´ano, aby pro libovoln´e prvky a, b, c ∈ P platilo (1) a + b = b + a,
(5) a · b = b · a,
(2) a + (b + c) = (a + b) + c,
(6) a · (b · c) = (a · b) · c,
(3) a + 0 = a,
(7) a · 1 = a,
(4) a + (−a) = 0,
(8) a · (b + c) = a · b + a · c.
Tvrzen´ı. Mnoˇzina P[x] spolu se zaveden´ymi algebraick´ymi operacemi je okruh. Dukaz. ˚ Cviˇcen´ı. Pˇr´ıklady. Okruh Z cel´ych cˇ´ısel, r˚uzn´e okruhy spojit´ych a diferencovateln´ych funkc´ı.
Prvek okruhu maj´ıc´ı inverzi se naz´yv´a invertibiln´ı. Mnoˇzina vˇsech invertibiln´ıch prvk˚u okruhu R se znaˇc´ı R ∗ . Okruh je pole pr´avˇe tehdy, kdyˇz R ∗ = R \ {0}. Okruh P[x] vˇsak nikdy nen´ı polem, protoˇze nekonstantn´ı polynomy nikdy nemaj´ı inverzi: 2
15. Polynomy
Tvrzen´ı. Invertibiln´ı prvky okruhu P[x] jsou pr´avˇe nenulov´e konstantn´ı polynomy. Dukaz. ˚ M´a-li f inverzi f −1 , pak f f −1 = 1. a proto jsou oba polynomy f, f −1 nenulov´e, naˇceˇz deg f ≤ deg f + deg f −1 = deg( f f −1 ) = deg 1 = 0. Zbytek je zˇrejm´y. Po ztotoˇznˇen´ı konstantn´ıch polynom˚u s odpov´ıdaj´ıc´ımi prvky pole P m´ame P[x]∗ = P \ {0} = P ∗ .
Aˇckoliv P[x] nen´ı pole a nem˚uzˇ eme po libosti dˇelit, lze alespoˇn kr´atit nenulov´ymi prvky. Tvrzen´ı. Necht’ f, g, h ∈ P[x]. (1) Necht’ f g = 0. Pak f = 0 nebo g = 0. (2) Necht’ f g = f h a f = 0. Pak g = h. Dukaz. ˚ (1) Je-li f = 0 nebo g = 0, nen´ı co dokazovat. Pˇripust’me opak, tj. f = 0 a z´aroveˇn g = 0. Oba polynomy f, g pak maj´ı vedouc´ı koeficienty, jejichˇz souˇcin je nenulov´y a je vedouc´ım koeficientem souˇcinu f g, naˇceˇz f g = 0. (2) M´ame f (g − h) = 0. Pˇri f = 0 pak podle (1) nutnˇe g − h = 0. Absence inverzn´ıch prvk˚u znamen´a, zˇ e m´a smysl uvaˇzovat o dˇelitelnosti polynom˚u. Teorie dˇelitelnosti polynom˚u je do znaˇcn´e m´ıry podobn´a teorii dˇelitelnosti cel´ych cˇ´ısel. ˇ ık´ame, zˇ e polynom g ∈ P[x] dˇel´ı polynom f ∈ P[x], jestliˇze existuje polynom Definice. R´ ˇ ık´ame t´ezˇ , zˇ e g je dˇelitel polynomu f . h ∈ P[x] takov´y, zˇ e f = gh. Zapisujeme g | f . R´ Pˇr´ıklad. Plat´ı x − 1 | x 2 − 1, protoˇze x 2 − 1 = (x − 1)(x + 1). Cviˇcen´ı. 1. Ukaˇzte, zˇ e x − 1 | x n − 1 pro kaˇzd´e cel´e n > 1. 2. Ukaˇzte, zˇ e relace | je reflexivn´ı a tranzitivn´ı. 3. Necht’ f = 0. Ukaˇzte, zˇ e z f g | f h plyne g | h.
Definice. Polynom f ∈ P[x] se naz´yv´a normovan´y, je-li f = 0 a lc f = 1. Je-li f = am x m + am−1 x m−1 + · · · a1 x + a0 libovoln´y nenulov´y polynom, lc f = am = 0, pak je pod´ıl f¯ = f / lc f = x m + (am−1 /am )x m−1 + · · · (a1 /am )x + a0 /am vˇzdy normovan´y polynom. Polynomy f, f¯ jsou z hlediska dˇelitelnosti rovnocenn´e (ovˇeˇrte napˇr´ıklad vztahy f | f¯ a f¯ | f ). Maj´ı tak´e tyt´ezˇ koˇreny. Lemma. Bud’te f, g ∈ P[x] normovan´e polynomy. N´asleduj´ıc´ı podm´ınky jsou ekvivalentn´ı: (1) f | g a z´aroveˇn g | f ; (2) f = g. Dukaz. ˚ Necht’ plat´ı (1), takˇze g = f p pro nˇejak´e p ∈ P[x] a souˇcasnˇe f = gq pro nˇejak´e q ∈ P[x]. Kdyˇz f = 0, pak g = 0 a (2) plat´ı. Kdyˇz f = 0, pak f = gq = f pq a po zkr´acen´ı 1 = pq, takˇze p je invertibiln´ı, a tedy vlastnˇe prvek z P ∗ . Potom 1 = lc g = lc f p = p. Tud´ızˇ , g = p f = f . Opaˇcn´a implikace je zˇrejm´a. Z lemmatu plyne, zˇ e relace dˇelitelnosti mezi normovan´ymi polynomy je nav´ıc antisymetrick´a. M´ame proto uspoˇra´ danou mnoˇzinu vˇsech normovan´ych polynom˚u. Infimum v t´eto uspoˇra´ dan´e mnoˇzinˇe se naz´yv´a nejvˇetˇs´ı spoleˇcn´y dˇelitel. 3
15. Polynomy
Nejvˇetˇs´ı spoleˇcn´y dˇelitel Definice. Bud’te f, g ∈ P[x] polynomy. Normovan´y polynom d ∈ P[x] se naz´yv´a nejvˇetˇs´ı spoleˇcn´y dˇelitel polynom˚u f, g, jestliˇze plat´ı: (a) d | f a d | g; (b) kdykoliv h ∈ P[x], h | f a h | g, pak h | d. Zapisujeme d = D( f, g). Podm´ınka (a) ˇr´ık´a, zˇ e d je spoleˇcn´y dˇelitel, podm´ınka (b) ˇr´ık´a, zˇ e kaˇzd´y jin´y spoleˇcn´y dˇelitel h dˇel´ı d. Pˇredpoklad normovanosti polynomu d zajiˇst’uje, zˇ e nejvˇetˇs´ı spoleˇcn´y dˇelitel je podm´ınkami (a), (b) urˇcen jednoznaˇcnˇe: Tvrzen´ı. Bud’te f, g ∈ P[x] dva polynomy. Pokud existuje jejich nejvˇetˇs´ı spoleˇcn´y dˇelitel, pak je jedin´y. Dukaz. ˚ Bud’ d jin´y nejvˇetˇs´ı spoleˇcn´y dˇelitel. Z definice snadno dost´av´ame, zˇ e d | d a d | d (cviˇcen´ı). Potom d = d , protoˇze jsou oba normov´any. Definice. Polynomy f, g ∈ P[x] takov´e, zˇ e D( f, g) = 1 se naz´yvaj´ı nesoudˇeln´e. Pˇr´ıklad. Plat´ı D(x, x + 1) = 1. Skuteˇcnˇe, polynom x je line´arn´ı a proto m´a jen line´arn´ı a konstantn´ı dˇelitele. Line´arn´ı dˇelitel´e jsou cx, kde c ∈ P, ale zˇ a´ dn´y z nich nedˇel´ı x + 1. Konstantn´ı dˇelitel´e jsou c ∈ P \ {0}, jejich normov´an´ım dostaneme 1.
V okruhu P[x] nejvˇetˇs´ı spoleˇcn´y dˇelitel skuteˇcnˇe existuje. D˚ukaz se vede podobnˇe jako v okruhu Z, m´ame totiˇz k dospozici ne´upln´e dˇelen´ı, zvan´e t´ezˇ dˇelen´ı se zbytkem. Viz n´asleduj´ıc´ı tvrzen´ı, kde q se naz´yv´a ne´upln´y pod´ıl a r se naz´yv´a zbytek. Tvrzen´ı. Bud’te f, g ∈ P[x] dva polynomy, necht’ g = 0. Pak existuj´ı polynomy q, r ∈ P[x] takov´e, zˇe (i) f = gq + r ; (ii) r = 0 nebo deg r < deg g. Lemma. Necht’ f, g ∈ P[x] a necht’deg f ≥ deg g. Pak existuje q ∈ P[x] takov´e, zˇe f − gq = 0 nebo deg( f − gq) < deg f. Dukaz ˚ lemmatu. Staˇc´ı poloˇzit q = (lc f /lc g) x deg f −deg g . Pak deg gq = deg f a t´ezˇ lc f = lc gq. V rozd´ılu f − gq se pak vedouc´ı cˇ leny vz´ajemnˇe zruˇs´ı. Dukaz ˚ tvrzen´ı. Poloˇzme q0 = 0 a r0 = f . Pak r := r0 , q := q0 vyhovuj´ı podm´ınce (i). Jestliˇze r0 = 0 nebo deg r0 < deg g, je vyhovˇeno i podm´ınce (ii) a d˚ukaz je hotov. V opaˇcn´em pˇr´ıpadˇe deg r0 ≥ deg g. Podle lemmatu existuje q1 ∈ P takov´e, zˇ e pro r1 = r0 − gq1 m´ame r1 = 0 nebo deg r1 < deg r0 . Pˇritom r := r1 , q := q0 + q1 vyhovuj´ı podm´ınce (i): gq + r = 0 + gq1 + r1 = r0 = f . Analogicky, pokud jsou jiˇz nalezeny nˇejak´e polynomy ri , qi splˇnuj´ıc´ı (i), pak je bud’ splnˇena i podm´ınka (ii) a d˚ukaz je hotov, anebo deg ri ≥ deg g a podle lemmatu existuje qi+1 takov´e, zˇ e pro ri+1 = ri − gqi+1 m´ame ri+1 = 0 nebo deg ri+1 < deg ri . Pˇritom opˇet r := ri+1 a q := qi + qi+1 vyhovuj´ı podm´ınce (i): gq + r = gqi + gqi+1 + ri+1 = gqi + ri = f .
4
15. Polynomy
Podm´ınka (ii) pak bude v nˇekter´em kroku jistˇe splnˇena. Pokud nenastane dˇr´ıve pˇr´ıpad ri = 0, bude to tehdy, aˇz klesaj´ıc´ı posloupnost · · · < deg r2 < deg r1 < deg r0 = deg f dos´ahne hodnoty niˇzsˇ´ı neˇz deg g.
N´asleduj´ıc´ı tvrzen´ı dokazuje existenci nejvˇetˇs´ıho spoleˇcn´eho dˇelitele v pˇr´ıpadˇe nenulov´ych polynom˚u. Tvrzen´ı. Bud’te f, g ∈ P[x] dva nenulov´e polynomy. Pak existuje jejich nejvˇetˇs´ı spoleˇcn´y dˇelitel d a polynomy u, v ∈ P[x] takov´e, zˇe d = f u + gv. Dukaz. ˚ Oznaˇcme I = { f u + gv | u, v ∈ P[x]}. V mnoˇzinˇe I jistˇe existuje nenulov´y prvek minim´aln´ıho stupnˇe. Vyberme jeden takov´y, normujme jej a oznaˇcme d. Pak jistˇe d = f u + gv pro nˇejak´a u, v ∈ P[x]. Ukaˇzme nejprve, zˇ e d | f . Dˇel´ıme-li se zbytkem, obdrˇz´ıme rovnost f = dq + r , kde r = 0 nebo deg r < deg d. V prvn´ım pˇr´ıpadˇe d | f a jsme hotovi. Druh´a moˇznost vˇsak nem˚uzˇ e nastat, protoˇze r = f − dq = f − ( f u + gv)q = f (1 − uq) − (gv)q ∈ I , takˇze r by byl nenulov´y prvek v I stupnˇe niˇzsˇ´ıho neˇz deg d. Analogicky d | g. Bud’d´ale h ∈ P[x] spoleˇcn´y dˇelitel polynom˚u f a g. Pak h zˇrejmˇe dˇel´ı i v´yraz f u + gv = d. T´ım je d˚ukaz je hotov. Aˇckoliv d˚ukaz tvrzen´ı pod´aval jist´y n´avod k nalezen´ı d, u, v, byl to n´avod prakticky nepouˇziteln´y. Prakticky pouˇziteln´ym postupem je Eukleid˚uv algoritmus. Eukleiduv ˚ algoritmus. Vstup: nenulov´e polynomy f, g ∈ P[x]. Sestavme posloupnost polynom˚u r0 , r1 , r2 , r3 , . . . kde r0 = f , r1 = g a jsou-li zn´amy cˇ leny ri , ri+1 , pak cˇ len ri+2 z´ısk´ame ne´upln´ym dˇelen´ım polynomu ri polynomem ri+1 : ri = ri+1 qi + ri+2 ,
ri+2 = 0 nebo deg ri+2 < deg ri−1 .
pro vˇsechna i = 0, . . . , N − 2. V´ystup: polynom r N −1 = 0 takov´y, zˇe r N = 0. Tvrzen´ı. Rovnosti r N = 0 je dosaˇzeno po koneˇcn´em poˇctu krok˚u a plat´ı r N −1 = D( f, g). Dukaz. ˚ Kdyby ri = 0 pro vˇsechna i ∈ N, pak bychom mˇeli nekoneˇcnou klesaj´ıc´ı posloupnost nez´aporn´ych cˇ´ısel deg g > deg r1 > deg r2 > deg r3 > . . ., coˇz nen´ı moˇzn´e. Tud´ızˇ , N vˇzdy existuje. Poloˇzme d = r¯N −1 (normovan´y zbytek) a ukaˇzme, zˇ e d | f , d | g. Zˇrejmˇe m´ame d | r N −1 , d | r N . Protoˇze ri = ri+1 qi + ri+2 , plyne odtud indukc´ı, zˇ e d | ri pro vˇsechna i = N − 2 aˇz i = 0 (cviˇcen´ı). Nakonec d | r1 = g a d | r0 = f . Bud’ d´ale h ∈ P[x] takov´e, zˇ e h | f = r0 a h | g = r1 . Protoˇze ri+2 = ri − ri+1 qi , opˇet se indukc´ı uk´azˇ e, zˇ e d | ri pro i = 0, . . . , N − 1 (cviˇcen´ı). Tud´ızˇ , d = D( f, g). 5
15. Polynomy
Poznamenejme, zˇ e existuje rozˇs´ıˇren´ı Eukleidova algoritmu, kter´ym lze z´ıskat i polynomy u, v: Rozˇs´ırˇ en´y Eukleiduv ˚ algoritmus. Vstup: nenulov´e polynomy f, g ∈ P[x]. Sestavme posloupnost polynom˚u r0 = f, r1 = g, r2 , . . . , r N −1 jako v obyˇcejn´em Eukleidovˇe algoritmu. Sestavme d´ale posloupnosti u 0 = 1, u 1 = 0, u 2 , . . . , u N −1 , v0 = 0, v1 = 1, v2 , . . . , v N −1 , kde u i = u i+1 qi + u i+2 a vi = vi+1 qi + vi+2 pro vˇsechna i = 0, . . . , N − 3. V´ystup: polynomy r N −1 , u N −1 , v N −1 . Tvrzen´ı. r N −1 = f u N −1 + gv N −1 . Dukaz. ˚ Cviˇcen´ı. Indukc´ı se dokazuj´ı rovnosti ri = f u i + gvi . Indukˇcn´ı krok pouˇz´ıv´a platnost dokazovan´eho tvrzen´ı pro i − 1 a i − 2.
Podobnˇe jako pˇrirozen´a cˇ´ısla lze jednoznaˇcnˇe rozkl´adat na souˇcin prvoˇc´ısel, lze normovan´e polynomy jednoznaˇcnˇe rozkl´adat na souˇcin normovan´ych polynom˚u d´ale nerozloˇziteln´ych. Definice. Reducibiln´ı polynom je nekonstantn´ı polynom, kter´y je souˇcinem dvou (ˇci v´ıce) nekonstantn´ıch polynom˚u. Ireducibiln´ı polynom je nekonstantn´ı polynom, kter´y nen´ı reducibiln´ı. Cviˇcen´ı. Ukaˇzte, zˇ e normovan´y reducibiln´ı polynom lze rozloˇzit tak, zˇ e oba cˇ initel´e jsou normov´ani. ¯ N´avod: je-li f = gh, pak f¯ = g¯ h.
Tvrzen´ı. Bud’ f ∈ P[x] normovan´y polynom. Pak existuj´ı normovan´e ireducibiln´ı polynomy g1 , . . . , gn takov´e, zˇe f = g1 · · · gn . Je-li f = h 1 · · · h m jin´y rozklad na normovan´e ireducibiln´ı cˇ initele, pak m = n a po vhodn´em pˇreˇc´ıslov´an´ı plat´ı h i = gi pro vˇsechna i = 1, . . . , n. (Pˇresnˇeji, existuje bijekce φ : {1, . . . , n} → {1, . . . , m} takov´a, zˇe h i = gφ(i) pro vˇsechna i.) Pˇr´ıklad. Polynom x 2 − 1 = (x − 1)(x + 1) je reducibiln´ı. Polynomy x − 1 a x + 1 jsou jiˇz ireducibiln´ı, m´ame tedy rozklad na normovan´e ireducibiln´ı polynomy.
Tvrzen´ı dok´azˇ eme, pˇritom pouˇzijeme nˇekolik pomocn´ych tvrzen´ı. Cviˇcen´ı. Necht’ jsou f, g ∈ P[x] normovan´e polynomy, necht’ je g ireducibiln´ı. Jestliˇze f | g, pak f = 1 nebo f = g. Je-li f t´ezˇ ireducibiln´ı, pak nutnˇe f = g.
Lemma. Bud’te g, h 1 , . . . , h n ireducibiln´ı normovan´e polynomy a necht’ g | h 1 · · · h n . Pak existuje index j takov´y, zˇe g = h j . Dukaz ˚ lemmatu. Poloˇzme d = D(g, h 1 ). Jelikoˇz d | g a g je ireducibiln´ı, m´ame bud’ d = g anebo d = 1 (zd˚uvodnˇete). V prvn´ım pˇr´ıpadˇe g = d | h 1 , naˇceˇz g = h 1 (cviˇcen´ı). Ve druh´em pˇr´ıpadˇe 1 = gu + h 1 v 6
15. Polynomy
pro vhodn´e polynomy u, v ∈ P[x]. N´asob´ıme-li na obou stran´ach souˇcinem h 2 · · · h m , obdrzˇ´ıme h 2 · · · h m = gh 2 · · · h m u + h 1 h 2 · · · h m v. Podle pˇredpokladu g | h 1 h 2 · · · h m , prav´a strana je tedy dˇeliteln´a g, a proto i lev´a strana je dˇeliteln´a, to jest g | h 2 · · · h m . Stejn´ym postupem pak uk´azˇ eme, zˇ e bud’ g = h 2 nebo g | h 3 · · · h m , coˇz opakujeme tak dlouho, dokud nenaraz´ıme na index j takov´y, zˇ e g = h j . Dukaz ˚ tvrzen´ı. Existence rozkladu: Je-li polynom f ireducibiln´ı, pak n = 1, g1 = f a jsme hotovi; je-li reducibiln´ı, pak se d´a rozloˇzit na souˇcin f = f 1 f 2 nekonstantn´ıch polynom˚u. Na kaˇzd´y z polynom˚u f 1 , f 2 m˚uzˇ eme uplatnit stejn´y postup – opˇet jsou bud’ ireducibiln´ı nebo se daj´ı samy rozloˇzit. Tak dojdeme k jist´emu seznamu souˇcinitel˚u, kter´y mus´ı b´yt koneˇcn´y, protoˇze poˇcet nekonstantn´ıch souˇcinitel˚u je shora omezen stupnˇem polynomu f . D˚ukaz jednoznaˇcnosti: Necht’ g1 · · · gn = h 1 · · · h m a vˇsichni souˇcinitel´e jsou ireducibiln´ı a normov´ani. Zˇrejmˇe g1 | h 1 · · · h m . Podle lemmatu existuje index φ(1) takov´y, zˇ e g1 = h φ(1) . V rovnosti g1 · · · gn = h 1 · · · h m pak m˚uzˇ eme zkr´atit g1 proti h φ(1) . Dostaneme podobnou rovnost jako na poˇca´ tku a stejn´ym zp˚usobem vyhled´ame index φ(2) takov´y, zˇ e g2 = h φ(2) , n´asledovnˇe index φ(3) takov´y, zˇ e g3 = h φ(3) , atd. aˇz gn = h φ(n) . Takto vznikne zobrazen´ı φ : {1, . . . , n} → {1, . . . , m}, podle zp˚usobu sv´e konstrukce injektivn´ı (ovˇeˇrte). Nakonec nutnˇe n ≤ m, protoˇze jinak bychom dostali gn−m | 1, coˇz nem˚uzˇ e b´yt je-li gn−m nekonstantn´ı. Opaˇcnou nerovnost m ≤ n z´ısk´ame podobn´ym postupem z rovnosti h 1 · · · h m = g1 · · · gn . Tud´ızˇ m = n a injektivn´ı zobrazen´ı φ je bijektivn´ı. Vˇsimnˇeme si, zˇ e reducibilita polynom˚u m˚uzˇ e z´aviset na volbˇe pole P. Pˇr´ıklad. Polynom x 2 + 1 je reducibiln´ı nad polem C, protoˇze x 2 + 1 = (x + i)(x − i). Tent´yzˇ polynom je ireducibiln´ı nad polem R, protoˇze jak´ykoliv jeho hypotetick´y rozklad x 2 + 1 = (x + ξ )(x + η), ξ, η ∈ R je souˇcasnˇe rozkladem nad C r˚uzn´ym od x 2 + 1 = (x + i)(x − i), ve sporu s jednoznaˇcnost´ı rozkladu.
Jako d˚usledek obdrˇz´ıme jist´e zobecnˇen´ı shora uveden´eho lemmatu. Dusledek. ˚ Bud’ f ∈ P[x], bud’te g1 , . . . , gm ∈ P[x] ireducibiln´ı, normovan´e a po dvou r˚uzn´e, tj. gi = g j pro i = j. Jestliˇze g1k1 | f , . . . , gmkm | f , pak g1k1 · · · gmkm | f . Ukaˇzme si nyn´ı souvislosti s koˇreny polynom˚u. Tvrzen´ı. Necht’ f ∈ P[x] a ξ ∈ P. N´asleduj´ıc´ı podm´ınky jsou ekvivalentn´ı: (i) ξ je koˇren polynomu f ; (ii) (x − ξ ) | f . Dukaz. ˚ Necht’plat´ı (i). Dˇelme se zbytkem: f = (x − ξ ) q + r,
r = 0 nebo deg r < deg(x − ξ ).
Je-li r = 0, pak m´ame (ii). Je-li r = 0, potom deg r < deg(x − ξ ) = 1, takˇze r je konstanta a v´ypoˇcet 0 = f (ξ ) = (ξ − ξ ) q(ξ ) + r = r ukazuje, zˇ e pˇr´ıpad r = 0 nenastane. 7
15. Polynomy
Naopak, pˇredpokl´adejme (ii). Potom f = (x − ξ ) q pro nˇejak´y polynom q, naˇceˇz f (ξ ) = (ξ − ξ ) q(ξ ) = 0. Definice. Prvek ξ ∈ P se naz´yv´a alespoˇn k-n´asobn´y koˇren polynomu f ∈ P[x], jestliˇze plat´ı (x − ξ )k | f . Prvek ξ ∈ P se naz´yv´a k-n´asobn´y koˇren polynomu f ∈ P[x], jestliˇze plat´ı (x − ξ )k | f , ale neplat´ı (x − ξ )k+1 | f . Tvrzen´ı. Bud’te ξ1 , . . . , ξn ∈ P r˚uzn´e koˇreny polynomu f ∈ P[x] s n´asobnostmi po rˇadˇe k1 , . . . , kn . Potom (1) (x − ξ1 )k1 · · · (x − ξn )kn | f ; (2) k1 + · · · + kn ≤ deg f . Dukaz. ˚ Cviˇcen´ı. Line´arn´ı polynomy x − ξ jsou zˇrejmˇe vˇzdy ireducibiln´ı. Rozloˇzen´ı polynomu f na line´arn´ı ireducibiln´ı cˇ initele je rovnocenn´e nalezen´ı vˇsech jeho koˇren˚u. Nad polem C jsou vˇsechny polynomy stupnˇe > 1 reducibiln´ı. To je d˚usledkem n´asleduj´ıc´ı vˇety: Z´akladn´ı vˇeta algebry. Kaˇzd´y nekonstantn´ı polynom f ∈ C[x] m´a alespoˇn jeden koˇren. Nen´ı zn´am zˇ a´ dn´y jednoduch´y d˚ukaz, vhodn´y pro tuto pˇredn´asˇku. Vˇeta bude dok´az´ana pozdˇeji v jin´e pˇredn´asˇce. Dusledek. ˚ Kaˇzd´y nekonstantn´ı polynom f ∈ C[x] m´a rozklad na line´arn´ı ireducibiln´ı cˇ initele. Koˇren˚u m´a se zapoˇcten´ım n´asobnosti pr´avˇe tolik, kolik cˇ in´ı jeho stupeˇn. Vid´ıme, zˇ e u´ loha nal´ezt rozklad polynomu f ∈ C[x] na ireducibiln´ı cˇ initele je rovnocenn´a u´ loze nal´ezt vˇsechny jeho koˇreny. Koˇreny polynom˚u stupnˇe dva pˇritom m˚uzˇ eme spoˇc´ıtat pomoc´ı zn´am´eho vzorce pro ˇreˇsen´ı kvadratick´e rovnice. Existuj´ı postupy pro nalezen´ı koˇren˚u ´ libovoln´eho polynomu f stupnˇe ≤ 4. Uloha se redukuje na posloupnost ˇreˇsen´ı pomocn´ych n rovnic tvaru x = c, tedy odmocˇnov´an´ı; hovoˇr´ıme o ˇreˇsen´ı v kvadratur´ach. Ukazuje se vˇsak, zˇ e pro obecn´y polynom stupnˇe ≥ 5 ˇreˇsen´ı v kvadratur´ach neexistuje (H. Abel). N´asobnost koˇrenu˚ Hled´an´ı koˇren˚u se m˚uzˇ e drasticky zjednoduˇsit, m´a-li polynom n´asobn´e koˇreny. Zaved’me zobrazen´ı C[x] −−−−→ C[x], kter´e polynomu f = am x m +am−1 x m−1 +· · ·+a1 x +a0 ∈ C[x] pˇriˇrazuje polynom f = mam x m−1 + (m − 1)am−1 x m−2 + · · · + a1 ∈ C[x]. Polynom f se naz´yv´a derivace polynomu f . Cviˇcen´ı. Ukaˇzte, zˇ e plat´ı (a) ( f + g) = f + g , (b) ( f g) = f g + f g , (c) ( f k ) = k f k−1 f .
8
15. Polynomy
Tvrzen´ı. Bud’ f ∈ C[x] polynom. Necht’ ξ ∈ C je jeho k-n´asobn´y koˇren, k ≥ 2. Potom (i) ξ je (k − 1)-n´asobn´y koˇren derivace f ; (ii) ξ je (k − 1)-n´asobn´y koˇren nejvˇetˇs´ıho spoleˇcn´eho dˇelitele D( f, f ); Dukaz. ˚ Je-li ξ koˇren polynomu f n´asobnosti k, pak f = (x − ξ )k q. (i) Derivujme:
f = k(x − ξ )k−1 q + (x − ξ )k q = (x − ξ )k−1 kq + (x − ξ )q . ı alespoˇn k − 1. Kdyby ξ byl koˇren n´asobnosti Vid´ıme, zˇ e ξ je koˇren polynomu f s n´asobnost´ k, pak bychom mˇeli (x − ξ ) kq + (x − ξ )q , naˇceˇz (x − ξ ) | kq, a tedy (x − ξ ) | q a koˇren ξ polynomu f by musel m´ıt n´asobnost k + 1. (ii) Z definice nejvˇetˇs´ıho spoleˇcn´eho dˇelitele plyne, zˇ e (x − ξ )k−1 | D( f, f ). Nejde o koˇren n´asobnosti k, protoˇze z (x − ξ )k | D( f, f ) by plynulo (x − ξ )k | f ve sporu s (i).
Cviˇcen´ı. Pˇredchoz´ı tvrzen´ı plat´ı i pro k = 1, interpretujeme-li rˇcen´ı ,,ξ je 0-n´asobn´y koˇren“ jako ,,ξ nen´ı koˇren.“
Protoˇze D( f, f ) dˇel´ı f , existuje pod´ıl f /D( f, f ) ∈ C[x]. Tvrzen´ı. Bud’ f ∈ C[x] polynom, bud’ ξ jeho koˇren. Pak ξ je 1-n´asobn´y koˇren pod´ılu f /D( f, f ). Dukaz. ˚ Je-li ξ koˇren n´asobnosti k, pak f = (x − ξ )k q a podle pˇredchoz´ıho tvrzen´ı D( f, f ) = k−1 (x − ξ ) r , kde r = kq + (x − ξ )q . Potom f q = (x − ξ ) , D( f, f ) r kde x − ξ nedˇel´ı q, a proto nedˇel´ı ani q/r . Dusledek. ˚ Bud’ f ∈ C[x] polynom. (i) Mnoˇzina vˇsech koˇren˚u polynomu f /D( f, f ) je rovna mnoˇzinˇe vˇsech koˇren˚u polynomu f ; (ii) Vˇsechny koˇreny polynomu f /D( f, f ) jsou 1-n´asobn´e. Dukaz. ˚ Cviˇcen´ı. Je-li podezˇren´ı, zˇ e polynom f m´a n´asobn´e koˇreny, pak je nejsn´aze urˇc´ıme tak, zˇ e vypoˇcteme polynom f /D( f, f ), jehoˇz stupeˇn je roven poˇctu (r˚uzn´ych) koˇren˚u polynomu f . Nelze sice oˇcek´avat, zˇ e ,,n´ahodnˇe“ zvolen´y polynom bude m´ıt n´asobn´e koˇreny, ale polynomy vyskytuj´ıc´ı se v praktick´ych u´ loh´ach cˇ asto n´asobn´e koˇreny maj´ı (v souvislosti se symetriˇcnost´ı u´ lohy). Polynomy s re´aln´ymi koeficienty Na z´avˇer se vˇenujme koˇren˚um polynom˚u s re´aln´ymi koeficienty a ukaˇzme, jak rozklad na ireducibiln´ı cˇ initele polynomu f ∈ R[x] nad polem R souvis´ı s jeho rozkladem nad polem C. 9
15. Polynomy
Zaved’me zobrazen´ı C[x] −−−−→ C[x], kter´e polynomu f ∈ C[x] pˇriˇrazuje polynom f ∗ , jehoˇz koeficienty jsou cˇ´ısla komplexnˇe sdruˇzen´a ke koeficient˚um polynomu f . To jest, je-li f = am x m + · · · + a1 x + a0 , pak f ∗ = am∗ x m + · · · + a1∗ x + a0∗ . Cviˇcen´ı. Ukaˇzte, zˇ e plat´ı (a) ( f + g)∗ = f ∗ + g ∗ , (b) ( f g)∗ = f ∗ g ∗ .
Tvrzen´ı. Bud’ f ∈ R[x] polynom s re´aln´ymi koeficienty. Necht’ ξ ∈ C je jeho koˇren. Pak komplexnˇe sdruˇzen´e cˇ´ıslo ξ ∗ je t´ezˇ koˇren, pˇriˇcemˇz stejn´e n´asobnosti. Dukaz. ˚ Jestliˇze ξ je koˇren n´asobnosti k, pak f = (x − ξ )k q. Aplikujme komplexn´ı sdruˇzen´ı na obou stran´ach. Protoˇze f m´a re´aln´e koeficienty, je f = f ∗ = (x − ξ ∗ )k q ∗ (cviˇcen´ı). Vid´ıme, zˇ e ξ ∗ je alespoˇn k-n´asobn´y koˇren polynomu f . Kdyby ξ ∗ byl vˇetˇs´ı n´asobnosti, tj. alespoˇn k + 1, pak by bylo f = (x − ξ ∗ )k+1r , naˇceˇz f = f ∗ = (x − ξ )k+1r ∗ , a ξ by t´ezˇ musel m´ıt n´asobnost k + 1. Rozklad polynomu f ∈ R[x] na ireducibiln´ı cˇ initele nad C pak obsahuje line´arn´ı ireducibiln´ı cˇ initele x − αi odpov´ıdaj´ıc´ı re´aln´ym koˇren˚um αi a dvojice line´arn´ıch ireducibiln´ıch cˇ initel˚u x − ξi , x − ξi∗ , odpov´ıdaj´ıc´ı dvojic´ım komplexnˇe sdruˇzen´ych koˇren˚u ξi , ξi∗ : f = (x − α1 )l1 · · · (x − αr )lr (x − ξ1 )k1 (x − ξ1∗ )k1 · · · (x − ξs )ks (x − ξs∗ )ks .
(∗)
Vid´ıme, zˇ e deg f = l1 + · · · + lr + 2(k1 + · · · + ks ). Cviˇcen´ı. Ukaˇzte, zˇ e kaˇzd´y polynom f ∈ R[x] lich´eho stupnˇe m´a alespoˇn jeden re´aln´y koˇren. Cviˇcen´ı. Necht’ξ ∈ C, ξ ∈ R. Ukaˇzte, zˇ e (x − ξ )(x − ξ ∗ ) = x 2 − 2 re ξ + |ξ |2 je kvadratick´y polynom s re´aln´ymi koeficienty a z´aporn´ym diskriminantem. N´avod: piˇste ξ = α + βi, kde α, β ∈ R.
Na z´akladˇe posledn´ıho cviˇcen´ı m˚uzˇ eme formuli (∗) pˇrepsat jako f = (x − α1 )l1 · · · (x − αr )lr (x 2 − 2 re ξ1 + |ξ1 |2 )k1 · · · (x 2 − 2 re ξs + |ξs |2 )ks . Tento souˇcin pˇredstavuje rozklad polynomu f na ireducibiln´ı cˇ initele nad polem R. Jak totiˇz v´ıme, kaˇzd´y kvadratick´y polynom q ∈ R[x] se z´aporn´ym diskriminantem je ireducibiln´ı. Cviˇcen´ı. Ukaˇzte, zˇ e re´aln´e polynomy ˇra´ du > 2 jsou vˇzdy reducibiln´ı nad R. Cviˇcen´ı. Rozloˇzte polynom x 4 + 1 na ireducibiln´ı cˇ initele nad polem C a nad polem R.
10
