1

VI. POLYNOMY

1. Základní definice a vlastnosti

Obor integrity polynomů nad polem bývá v učebnicích zaváděn buď zcela ne-formálně nebo naopak formálně v řeči nekonečných posloupnosí s jednoduchýmsčítáním a podivuhodným nasobením. Přitom je tento obor velmi přirozená(a jednoduchá) algebra cest nad grafem

.....

.....

.....

......................................................................

...................................................................................................................................................................................................................................................................................................................

............................

............

•

Dříve, než toto tvrzení objasníme, popišme konstrukci oboru integrity F [x]polynomů nad tělesem T v duchu metod Sylvestera, Cayleyho a Hamiltona.

Uvažujme vektorový prostor VF všech nekonečných posloupností

f = (a0, a1, a2, . . . , at, . . . ) = (at)t≥0, kde at ∈ F,

takových, že jen konečně mnoho jejich členů je různých od 0 ∈ T . Pro každý„nenulovýÿ prvek f ∈ VF tedy existuje takové an 6= 0, že at = 0 pro všechnat > n. Číslo n nazýváme stupeň f a píšeme deg f = n.

Množina B = {en | n ≥ 0}, kde en = (at), an = 1 a at = 0 pro všechnat 6= n, je zřejmě báze vektorového prostoru VF .Nyní definujme na prostoru VF násobení, které je kompatibilní se strukturou

vektorového prostoru:arer × ases = araser+s,

a rozšiřme násobení na celý vektorový prostor VF pomocí distributivity. Toznamená následující: Jestliže

f = (ar) =∑

r≥0

arer a g = (bs) =∑

s≥0

bses,

potom

f × g = (ct) =∑

t≥0

ctet, kde ct =t∑

q=0

aqbt−q.

Nebolif × g =

∑

r≥0

∑

s≥0

arbser+s =∑

t≥0

( ∑

r+s=t

arbs

)

et.

Tímto způsobem jsme prostor VF opatřili strukturou okruhu. Nula je nulovývektor, jednotka je vektor e0, píšeme jednoduše e0 = 1. Zobrazení Φ : T → VTdefinované vztahem Φ(a) = ae0 je izomorfismus tělesa T a podokruhu všech

2

posloupností (at) takových, že at = 0 pro všechna t ≥ 1. Tento podokruhztotožníme s T . Dále vycházíme z historického značení a píšeme e1 = x. Potom

e2 = e1 × e1 = x2, e3 = e2 × e1 = x3, . . . , et = xt, . . . ,

a tedy

(⋆) (a0, a1, a2, . . . , at, . . . ) = a0+a1x+a2x2+· · ·+atxt+· · · =

∞∑

t=0

atxt = f(x).

Navíc místo VT píšeme F [x]. Zobrazení

ϕ : F → F [x] definované pomocí ϕ(a) = ae0

je izomorfismus pole F a podpole {ae0 | a ∈ F} oboru F [x].

Popišme nyní tuto konstrukci jako velmi speciální algebru cest daného ori-entovaného grafu.

Už v úvodu jsme pro daný konečný orientovaný graf Γ = (V,H), definovalivelmi přirozenou cestou pologrupu cest S(Γ). Nyní pro dané pole F sestrojímevektorový prostor FΓ, jehož bází je právě množina (pologrupa) S(Γ) všech cest.Prvky tohoto vektorového prostoru jsou tedy konečné lineární kombinace cestgrafu Γ s koeficienty z pole F . Je proto snadné, užitím distributivního zákona,rozšířit násobení z pologrupy S(Γ) na celou množinu (vektorový prostor) FΓ.

Na množině FΓ máme tedy dvě operace, (vektorové) sčítání a právě defino-vané násobení, které jsou svázány distributivním zákonem. FΓ je tedy okruhems jednotkovým prvkem e =

∑

i∈V ei, a navíc vektorovým prostorem nad po-lem F , které je kanonicky do F -algebry FΓ vnořeno izomorfismem

ϕ : F → FΓ, jenž je definován pomocí ϕ(a) = ae pro a ∈ F.

Podotkněme, že důležitým invariantem algebry FΓ je její F -dimenze.

Příklad. Pologrupa cest grafu

• ••

•

1

3

4

2.........................................................................................................

.... ............................................................................................................

.................................................................................................... ........

αβ

γ ·

byla popsána v úvodu; příslušná devítidimenzionální algebra cest je izomorfnís okruhem všech matic

a11 a12 a13 a140 a22 a23 a240 0 a33 00 0 0 a44

,

3

kde aij ∈ F .

Poznámka 1. Jednou z důležitých (a překvapivých) vlastností této (jed-noduché) konstrukce algebry cest je fakt, že „téměř každou konečně dimenzio-nální algebruÿ lze vyjádřit jako faktorovou algebru vhodné algebry cest. Např.(řečeno přesněji) pro pole F = C či F = Zp, každá konečně dimenzionální F -algebra je faktorovou algebrou algebry F (Γ) pro vhodný (konečný orientovaný)graf Γ. Důkaz tohoto tvrzení vyžaduje náročnou studii algeber a přesahuje rá-mec této publikace.

Důležitým tvrzením je nyní následující věta.

Věta 1. Algebra F [x] polynomů nad polem F je izomorfní F -algebře cestgrafu

.....

.....

.....

......................................................................

...................................................................................................................................................................................................................................................................................................................

............................

............

•

Důkaz. Izomorfismus je dán zobrazením

n∑

t=0

atxt →

n∑

t=0

atαt.

Poznámka 2. Podobným způsobem můžeme definovat polynomy nad libo-volným okruhem R a studovat příslušný okruh R[x]. Důležitý je zejména pří-pad, kdy R je oborem integrity (např. kdy R = Z); jak uvidíme níže, v tomtopřípadě je R[x] též oborem integrity. V našich formulacích je podstatný před-poklad, že F je pole.

Okruh Zm[x], kde m je složené číslo, zmíníme v několika příkladech a po-známkách, abychom zdůraznili význam tohoto předpokladu. Uvidíme, že teorietakových okruhů Zm[x] je dramaticky odlišná od teorie F [x], kde F je pole. Jižvíme, že každá rovnice tvaru ax+ b = 0, kde ax+ b ∈ Zm[x], a 6= 0 má řešenív Zm právě tehdy, když m je prvočíslo. Takové řešení je potom jednoznačné.Jednoduše lze také nahlédnout, že každá kvadratická rovnice nad Zm, kde mje prvočíslo, má nejvýše dvě řešení. Ovšem kvadratické rovnice nad Zm, kde mnení prvočíslo, mohou mít více než dvě řešení: Např. nad Z6 má kvadratickárovnice x2+3x+2 = 0 čtyři řešení 1, 2, 4 a 5. Pro polynom x2+3x+2 ∈ Z6[x]platí

x2 + 3x+ 2 = (x+ 1)(x+ 2) = (x+ 4)(x+ 5) ! ! !

Připomeňme, že v matematice obyčejně mluvíme o polynomiální funkci.Vztah mezi (formálními) polynomy, jak jsme je definovali, a polynomiálnímifunkcemi vysvětlíme podrobněji níže. Už nyní však poznamenejme, že každémupolynomu f z okruhu F [x] můžeme přiřadit „vyhodnocovací zobrazeníÿ. Každý

4

polynom f ∈ F [x] tvaru (⋆) totiž definuje zobrazení (polynomiální funkci)f : F → F přiřazující každému prvku c ∈ F prvek

f(c) =∞∑

t=0

atct.

Množina P (F ) všech polynomiálních funkcí nad polem F tvoří zřejmě vzhledemke sčítání a násobení

(f + g) (c) = f (c) + g (c) a (f . g) (c) = f (c) . g (c)

okruh, a vyhodnocovací zobrazení Φ : F [x] → P (F ) je epimorfismus. Je-li pole F konečné, pak je zřejmě počet těchto (různých) zobrazení konečný.Jestliže F má q prvků, pak je tento počet zřejmě shora ohraničen hodnotou qq.Význam těchto zobrazení uvidíme později v této části. Jednou ze základníchotázek, kterou se budeme v této souvislosti zabývat, je, do jaké míry polyno-miální funkce určují polynomy, tj. co je jádrem epimorfizmu Φ.

Další důležité zobrazení se vztahuje k hodnotě polynomů z F [x] v danémprvku c z F . Toto zobrazení označíme Ψc : F [x] → F . Tedy Ψc(f) = f(c).Zřejmě pro daná f, g ∈ F [x] platí Ψc(f + g) = Ψc(f) + Ψc(g) a Ψc(fg) =Ψc(f)Ψc(g), a proto Ψc je homomorfismus F [x] na F . Jádro tohoto epimorfismuje ideál {(x− c)h(x) | h(x) ∈ F [x]}. To plyne ze zřejmého faktu, že Ψc(x− c) =0. Poznamenejme, že se jedná o speciální případ kongruence v F [x], kteroubudeme uvažovat dále v této kapitole. Struktura homomorfismu Ψc je popsánarelací kongruence

f ≡ g (mod (x− c))

vyjadřující fakt, že polynom f − g je násobkem lineárního polynomu x − c.Ohodnocení daného polynomu f(x) = anxn+an−1xn−1+ · · ·+a1x+a0 v c ∈ Tmůže být výhodně vypočítáno jako

f(c) = [(((. . . {[(anc+ an−1)c+ an−2]c+ an−3} . . . )))c+ a1]c+ a0.

Poznámka 3. Homomorfizmus Ψc : F [x] → F může být jednoduše rozší-řen na homomorfismus F [x] do R, kde R je libovolný okruh obsahující pole F .Tedy můžeme např. definovat hodnotu ΨTr polynomů z F [x] pro danou lineárnítransformaci Tr vektorového prostoru nad F nebo pro matici nad F . Pozna-menejme, že Cayley-Hamiltonova věta lineární algebry říká, že charakteristickýpolynom Tr leží v jádru ΨTr.

Následující věta a její důsledek jsou zřejmé.

Věta 2. Nechť f, g ∈ F [x]. Potom deg(fg) = deg f+deg g and deg(f+g) ≤max(deg f,deg g).

Důsledek 1. F [x] nemá netriviální dělitele nuly.

5

Tedy F [x] je obor integrity, tj. komutativní okruh bez netriviálních dělitelůnuly. F [x] je (stejně jako obor integrity Z) eukleidovským oborem v tom smyslu,že platí následující (fundamentální) věta.

Věta 3 (Eukleidovské dělení). Nechť f a g 6= 0 jsou polynomy z F [x].Potom existují polynomy q, r ∈ F [x], pro něž

f(x) = q(x)g(x) + r(x), kde r = 0 nebo deg r < deg g.

Polynomy q a r jsou těmito podmínkami jednoznačně určeny.

Důkaz. Tvrzení je triviální v případě f = 0 nebo deg f < deg g. Předpoklá-dejme tedy, že

f(x) = anxn + an−1x

n−1 + · · ·+ a1x+ a0, an 6= 0

ag(x) = bmx

m + bm−1xm−1 + · · ·+ b1x+ b0, bm 6= 0,

kde n ≥ m. Budeme postupovat indukcí podle n. Označme

f♯(x) = f(x)− anb−1m xn−mg(x).

Potom deg f♯ < deg f = n, a tedy podle indukčního předpokladu f♯ = q♯g + r,kde deg r < deg g.

Proto

f(x) = anb−1m x

n−mg(x)+f♯(x) = (anb−1m x

n−m+q♯(x)) g(x)+r(x) = q(x)g(x)+r(x),

vyjádříme-li polynom f v požadovaném tvaru. K důkazu jednoznačnosti tohotovyjádření předpokládejme, že

f = q1g + r1 = q2g + r2, kde deg r1 < deg g a deg r2 < deg g.

Potom (q1 − q2)g = r2 − r1. Porovnáním stupňů polynomů zjistíme, že oběstrany mohou být pouze rovny nule. Tím je věta dokázána.

Důsledek 2. Nechť f ∈ F [x] je polynom stupně n a nechť c0, c1, . . . , cn−1 ∈F . Potom existují (jednoznačné) prvky a0, a1, a2, . . . , an ∈ F , pro něž platí(⋆⋆)f(x) = a0+a1(x−c0)+a2(x−c0)(x−c1)+· · ·+an(x−c0)(x−c1) . . . (x−cn−1).

Důkaz. Aplikujme postupně eukleidovské dělení:

f(x) = (x− c0)f1(x) + a0, kde deg f1 = n− 1

f1(x) = (x− c1)f2(x) + a1, kde deg f2 = n− 2

6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ft(x) = (x− ct)ft+1(x) + a1, kde degft+1 = n− t− 1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

fn−1(x) = (x− cn−1)fn(x) + an−1, kde degfn = 0

fn(x) = an.

Poznámka 4. Výraz (⋆⋆) pro f(x) se nazývá Newtonova interpolační for-mule: Nechť je dáno n + 1 různých prvků c0, c1, . . . , cn ∈ F a n + 1 li-bovolných prvků d0, d1, . . . , dn ∈ F . Pak můžeme rekurzivně určit prvkya0, a1, a2, . . . , an ∈ F tak, že pro f(x) =

∑nt=0 atx

t splňující f(c0) = d0,f(c1) = d1, . . . , f(cn) = dn platí a0 = d0, a1 = (d1 − d0)(c1 − c0)−1, . . .

Důsledek 3. Nechť f ∈ F [x] je polynom stupně n a nechť c ∈ F . Potomexistují (jednoznačné) prvky a0, a1, a2, . . . , an ∈ F takové, že

f(x) = a0 + a1(x− c) + a2(x− c)2 + · · ·+ an(x− c)n =n∑

t=0

at(x− c)t.

Důsledek 4. Nechť f ∈ F [x] je nenulový polynom a nechť c ∈ F . Potomf(c) = 0 právě tehdy, když

f(x) = (x− c)g(x), kde deg g = deg f − 1.

Definice 2. Řekneme, že c ∈ F je kořen polynomu f ∈ F [x] v F , jestližef(c) = 0.

Důsledek 5. Nechť F je pole takové, že každý nekonstantní polynom z F [x]má v F kořen. Nechť f ∈ F [x] je polynom stupně n. Potom existují prvkyc1, c2, . . . , cn ∈ F a a ∈ F takové, že

f(x) = a(x− c1)(x− c2) . . . (x− cn).

Poznámka 5. Pole F s vlastností, že každý nekonstantní polynom z F [x] máv F kořen, se nazývají algebraicky uzavřená. Např. pole C komplexních čísel jealgebraicky uzavřené. Na druhou stranu pole Q, R a BbbZp nejsou algebraickyuzavřená. Z posledního důsledku plyne, že polynom stupně n nad algebraickyuzavřeným polem nemůže mít více než n kořenů. Následující věta ukazuje, žetoto tvrzení platí pro každé pole F .

Věta 3. Nenulový polynom f ∈ F [x] stupně n má nejvýše n kořenů. Jestliže

f(x) = a0 + a1x+ · · ·+ anxn a g(x) = b0 + b1x+ · · ·+ bnxn

7

jsou dva polynomy takové, že f(c) = g(c) pro všechna c ∈ F a n je menší nežpočet prvků v F , potom

at = bt pro všechna 0 ≤ t ≤ n.

Důkaz. Věta plyne z Důsledku 5. Budeme postupovat indukcí: Je-li c1 kořenpolynomu f , potom f(x) = (x − c1)g(x), kde deg g = n − 1. Každý kořenc2 polynomu f , c2 6= c1, musí být kořenem polynomu g, neboť 0 = f(c2) =(c2 − c1)g(c2), a tedy g(c2) = 0. Podle indukčního předpokladu má g nejvýšen− 1 kořenů. Proto má f nejvýše n kořenů.Aplikujeme-li toto tvrzení na polynom f − g, dostaneme druhou část věty.

Poznámka 6. Všimněte si, že k důkazu této věty jsme využili důležitéhofaktu, že F nemá netriviální dělitele nuly. Jinak, jak jsme již dříve poznamenali,polynom stupně n může mít víc než n kořenů. Např. polynom x2 + 3x+ 2 máv Z6 čtyři kořeny a x2 + 28 má v Z32 osm kořenů (2, 6, 10, 14, 18, 22, 26 a30). Dodejme, že všechny prvky okruhu Z6 jsou kořeny polynomu x3 + 5x =x (x− 1) (x− 5) = (x− 1) (x− 2) (x− 3) = (x− 3) (x− 4) (x− 5).

Důsledek 6. Je-li pole F nekonečné, potom f = g právě tehdy, kdyžf(c) = g(c) pro všechna c ∈ F . Má-li pole F právě q prvků, potom pro libovolnépolynomy f, g ∈ F [x], jejichž stupeň je menší než q, platí rovnost f = g právětehdy, když f(c) = g(c) pro všechna c ∈ F , tj. když f = g.Důkaz. Stupeň polynomu f − g nemůže být menší než počet kořenů, pokud

neplatí rovnost f = g.

Poslední důsledek říká, že pro Zp[x] existuje vzájemně jednoznačná kores-pondence mezi množinou všech polynomů stupně < p a všech zobrazení Zp doZp. Obě tyto množny mají pp prvků a dva takové různé polynomy f a g definujírůzná zobrazení f a g. Tento (důležitý) výsledek přeformulujeme a uvedemejako důsledek následující věty. Zároveň podáme jeho konstruktivní důkaz.

Věta 4 (Lagrangeova interpolace). Nechť je dáno n různých prvkůc0, c1, . . . , cn−1 a n libovolných prvků d0, d1, . . . , dn−1 z F . Potom existujeprávě jeden polynom f ∈ F [x] stupně < n takový, že f(ct) = dt pro každé0 ≤ t ≤ n− 1.

Důkaz. Sestrojme n polynomů ft ∈ F [x], 0 ≤ t ≤ n− 1 stupně n− 1 tak, že

ft(cs) = ds pro t = s a ft(cs) = 0 jinak.

Definujme ut(x) = (x− c0)(x− c1) . . . (x− ct−1)(x− ct+1) . . . (x− cn−1). Odtudut(cs) = 0 pro všechna s 6= t. Nechť ut(ct) = at. Protože at 6= 0 (ct 6=cs pro t 6= s), existuje bt ∈ T tak, že atbt = dt. Položme ft(x) = btut(x).V důsledku toho polynom f =

∑n−1t=0 ft splňuje všechny vlastnosti požado-

vané naší větou. Abychom ukázali jednoznačnost f , uvažujme další polynom g

8

s těmito vlastnostmi. Potom všech n prvků ct je kořeny polynomu f −g, a pro-tože stupeň f−g nemůže být menší než počet kořenů, nutně musí platit rovnostf − g = 0.Důsledek 7 (obecná vlastnost polynomů nad konečnými poli).

Nechť F je pole o q prvcích. Potom existuje vzájemně jednoznačná korespon-dence mezi množnou všech polynomů F [x] stupně < q a množnou všech (bo-dových) zobrazení F do sebe. Jinými slovy pro každé ϕ : F → F existujejednoznačný polynom f ∈ F [x] stupně < q tak, že f(c) = ϕ(c).

Příklad. Zkonstruujme polynom f ∈ Z5[x] stupně < 5 tak, že f(0) = 1,f(1) = 0, f(2) = 4, f(3) = 4 a f(4) = 0 [zde jednoduše píšeme 0, 1, 2, 3, 4pro prvky Z5]. Nejprve u0(x) = (x−1)(x−2)(x−3)(x−4) = x4+4; u0(0) = 4a 4× 4 = 1. Odtud f0 = 4x4+1. Všimněte si, že f1 i f4 jsou nulové polynomy.Podobně jako pro f0 zkonstruujme f2 a f3. Máme u2(x) = x4 = 2x3+4x2+3x,u2(2) = 4, odtud f2 = u2. Dále u3(x) = x4 + 3x3 + 4x2 + 2x a f3 = u3. Protof = f0 + f2 + f3, tj. f(x) = x4 + 3x2 + 1.

Příklad. Jestliže F = Zp, pak podle Malé Fermatovy věty platí cp = c prokaždé c ∈ Zp. Proto pro každé f ∈ Zp[x], deg f ≥ p existuje polynom g ∈ Zp[x],deg g < p, tak, že f(c) = g(c) pro všechna c ∈ Zp.V následující větě popíšeme polynomiální funkce nad Zp[x].

Věta 5 (Polynomiální funkce nad Zp). Označme symbolem f∗ (Ferma-tův) polynom definovaný pomocí f∗(x) = xp − x = xp + p− 1x.(a) Polynomy f ∈ Zp[x] takové, že f(c) = 0 pro všechny prvky c ∈ Zp (jinýmislovy ty polynomy f , pro něž je f nulový) tvoří ideál

I0 = {f∗h | h ∈ Zp} v oboru integrity Zp[x].

(b) Nechť g ∈ Zp[x] je daný polynom. Pak polynomy f ∈ Zp[x] takové, žef(c) = g(c) pro všechny prvky c ∈ Zp (jinými slovy ty polynomy f , které splňujíf = g), tvoří rozkladovou třídu

Ig∗ = {g∗ + f∗h | h ∈ Zp} ideálu I0 v Zp[x],

kde g∗ je (jednoznačný) polynom stupně < p takový, že g∗(c) = g(c) pro všechnac ∈ Zp.Důkaz. Z Malé Fermatovy věty plyne, že f∗(c) = 0 pro každé c ∈ Zp. Podle

předchozího výsledku existuje polynom r stupně menšího než p tak, že r(c) = 0pro všechna c ∈ Zp. Nechť tedy f(c) = 0 pro všechna c ∈ Zp. Po provedeníeukleidovského dělení dostáváme f = f∗h+ r, kde r musí být nulový polynom,neboť r(c) = 0 pro všechna c ∈ Zp. Z toho již plyne tvrzení (a).Podle jednoho z předchozích výsledků, existuje (jednoznačný) polynom g∗ ∈

Zp[x] stupně < p takový, že g∗ = g, tj. takový, že g∗(c) = g(c) pro všechnac ∈ Zp. Opět f − g∗ = f∗h, z čehož plyne (b).

9

Poznámka 7. Stejně jako dříve v případě lineárního polynomu x−c budemenyní uvažovat následující kongruenci: f a g patří do stejné rozkladové třídy Ig∗modulo I0 znamená, že f ≡ g (mod g∗), tj. f − g ∈ I0, nebo jinými slovy f − gje násobek g∗. To bude obsahem následující kapitoly.

2. Dělitelnost a kongruence v F[x]

Definice 1. Nechť f a g jsou polynomy oboru integrity F [x]. řekneme, žeg je dělitel nebo faktor polynomu f (nebo že f je násobek g) a píšeme g|f ,jestliže existuje polynom h tak, že f = gh. Platí-li g|f i f |g, pak říkáme, že fa g jsou asociované.

Věta 1. Polynom f ∈ F [x] má inverzní prvek (tj. je jednotkou v F [x]) právětehdy, když je to polynom stupně 0, tj. nenulový prvek pole F . Polynom f jeasociovaný s g právě tehdy, když f = ug, kde u je jednotka; v tomto případěf a g mají stejný stupeň. V každé třídě asociovaných polynomů (tj. jednotko-vých násobků nenulových polynomů) existuje jednoznačný monický polynom,tj. polynom s vedoucím koeficientem an = 1.

Poznámka 1. Jednotkový polynom lze charakterizovat jako polynom, kterýje dělitelem každého polynomu z F [x]. Všechny jednotky tvoří třídu navzájemasociovaných polynomů, z pohledu dělitelnosti triviální. Tvrzení o dělitelnostipolynomů se týkají polynomů až na jejich násobky nenulovými prvky z pole F(jednotkami z F [x]), tj. tříd navzájem asociovaných polynomů. Ty lze jedno-značně reprezentovat monickými polynomy.

Definice 2. Nechť f, g ∈ F [x], g 6= 0, jsou dané polynomy. Monický polynomd ∈ F [x] se nazývá jejich největší společný dělitel, je-li d dělitel f i g a navíckdykoliv d′ dělí f a g, potom d′ dělí i d.

Existence největších společných dělitelů je zaručena následující větou:

Věta 2 (Eukleidův algoritmus). Nechť f a g 6= 0 jsou dva polynomyz F [x]. Potom následující posloupnost eukleidovských dělení

f = gq0 + r0, r0 6= 0, deg r < deg g;g = r0q1 + r1, r1 6= 0, deg r1 < deg r0;r0 = r1q2 + r2, r2 6= 0, deg r2 < deg r1;. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

rt−1 = rtqt+1 + rt+1, rt+1 6= 0, deg rt+1 < deg rt;. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

je konečná: končí tehdy, když je poslední zbytek roven nule.

Monický násobek posledního nenulového zbytku je největší společný dělitel(f, g) polynomů f a g. Jestliže r0 = 0, tj. jestliže g|f , potom (f, g) je monickýnásobek g.

10

Důkaz Eukleidova algoritmu je analogický důkazu obdobné věty pro celáčísla.

Poznamenejme, že z této věty vyplývá, že největší společný dělitel f a g je(jednoznačný) monický dělitel f a g nejvyššího stupně.

Důsledek 1 (Bézoutova věta). Nechť f a g jsou dva nenulové polynomyz F [x] a d = (f, g). Potom existují polynomy u, v ∈ F [x] tak, že

fu+ gv = d.

Příklady.

(a) Abychom našli největšího společného dělitele f(x) = 2x4 + 5x3 − x ag(x) = 2x3 − 3x2 + 1, použijeme Eukleidův algoritmus (polynom v každémkroku nahradíme, je-li to možné, polynomem „jednoduššímÿ, s ním asociova-ným):

2x4 + 5x3 − x = (2x3 − 3x2 + 1)(x+ 4) + (12x2 − 2x− 4);

2x3 − 3x2 + 1 = (6x2 − x− 2)( 13x− 49 ) + (29x+ 19 );

6x2 − x− 2 = (2x+ 1)(3x− 2).

Tedy d(x) = x + 12 je největší společný dělitel f a g. Budeme-li v získanýchvztazích postupovat zpět, můžeme d vyjádřit jako (lineární) kombinaci f a g:

x+1

2= (−3

4x+ 1)(2x4 + 5x3 − x) + (3

4x2 + 2x+

1

2)(2x3 − 3x2 + 1).

(b) Podobně zjistíme, že d(x) = x + 2 je největší společný dělitel f(x) =x4 + x3 + x a g(x) = 2x3 + 1 v Z3[x]: x4 + x3 + x = (x3 + 2)(x+ 1)+ (2x+ 1),x3 + 2 = (x+ 2)(x2 + x+ 1). Navíc

x+ 2 = 2(x4 + x3 + x) + (2x+ 2)(2x3 + 1).

Poznámka 2. Všimněte si, že v předchozích příkladech jsme mohli použítvýsledek (a) k získání výsledku (b). (Kanonický) homomorfismus ϕ : Z → Z3lze rozšířit na homorfismus ϕ : Z[x] → Z3[x]. [Zde Z[x] označuje podokruhQ[x] všech polynomů s celočíselnými koeficienty.] Lze jednoduše nahlédnout, žef | g pro dva polynomy s celočíselnými koeficienty v Q[x] implikuje ϕ(f) | ϕ(g).Zdůrazněme, že opačná implikace obecně neplatí! Pro f(x) = x + 1, g(x) =x2 + 2 platí ϕ(f) | ϕ(g), ale f není dělitelem g.

Definice 3. Polynom p ∈ F [x] se nazývá ireducibilní (nerozložtelný) (nadF ), jestliže je stupně ≥ 1 a dále platí, že je-li p = fg, f, g ∈ F [x], danýrozklad p, pak je deg f = 0 nebo deg g = 0 (tj. jeden z polynomů f a g je kon-stantní). Polynom, který není ireducibilní, se nazývá reducibilní (rozložtelný).Polynomy f a g se nazývají nesoudělné, je-li jejich největší společný dělitelroven 1.

11

Věta 3. Nechť jsou dány polynomy f, g, h ∈ F [x]. (Diofantovská) rovnice

fs+ gr = h

pro polynomy s a r má v F [x] řešení právě tehdy, když (f, g)|h. Je-li(s0(x), r0(x)) jedno její řešení, potom {(s0(x)+g(x)w(x), r0(x)−f(x)w(x) |w(x) ∈F [x]} je množna všech řešení.

Věta 4 (GAUSSOVA). Nechť f, g a h jsou tři nenulové polynomy. Pokudf dělí gh a f a g jsou nesoudělné polynomy, potom f dělí h.

Věta 5. Každý polynom z F [x] stupně ≥ 1 lze vyjádřit jako součinp1p2 . . . pm ireducibilních polynomů. V tomto součinu jsou polynomy p1, p2, . . . , pmjednoznačně určeny až na pořadí a nenulové konstantní faktory. Jsou-li poly-nomy pt monické, pak jsou jednoznačně určeny až na permutaci.

Obory integrity s vlastností popsanou v předchozí větě se nazývají oborys jednoznačným rozkladem. Všechny naše obory integrity polynomů F [x] jsouobory s jednoznačným rozkladem. Povaha ireducibilních polynomů v těchtooborech závisí na povaze tělesa T . Nyní uvádíme stručný přehled některýchpřípadů.

Příklady.

(a) V C[x] jsou ireducubilní pouze lineární polynomy (tj. stupně 1). Toto tvrzeníse nazývá Základní věta algebry. Důkaz této věty naleznete v Dodatku A.

(b) V R[x] jsou ireducibilní všechny lineární polynomy a kvadratické polynomyf(x) = a+ bx+ cx2 takové, že „diskriminantÿ (b2 − 4ac)/4c je záporný.(c) V Q[x] existují ireducibilní polynomy libovolně vysokých stupňů.

(d) Označme Np(d), p prvočíslo, počet ireducibilních polynomů v Zp[x]stupně d. Potom

(∗) Np(d) =1

d

∑

t|d

µ(d

t) · pt,

kde µ je Möbiova funkce µ(m) = 0, jestliže m je dělitelné druhou mocni-nou prvočísla, a µ(p1p2 . . . pk) = (−1)k, jestliže p1, p2, . . . , pk jsou různá pr-vočísla. Tedy N2(2) = 1, N2(3) = 2, N2(5) = 6, N2(7) = 18, N2(11) = 186,N2(13) = 630, N2(17) = 7710, N2(19) = 27594, . . . , N2(q) = 2q−1(2q−1 − 1)pro libovolné prvočíslo q, . . . Vzorec (∗) lze získat z výsledku C. Gausse (1777–1855) publikovaného v Disquisitiones arithmeticae, str. 610.

Cvičení 1.

(a) Vypočítejte N2(30) a N5(4).

(b) Napište všechny ireducibilní polynomy ze Z3 stupně ≤ 5.

12

(c) Najděte největšího společného dělitele polynomů 3x5 +3x3 + x2 − 6x+2 a7x4 − x3 + 15x2 − 2x+ 2 v Q[z]. [Odpověď: x2 + 2.](d) Najděte největšího společného dělitele D(x) polynomů f(x) = 3x5 +3x3 +x2 + 4x+ 2 a g(x) = 2x4 + 4x3 + 3x+ 2 ze Z5[x] a určete u, v ∈ Z5[x] tak, žeD = uf + vg. [Odpověď: x2 + 2 = 4f(x) + (4x+ 2)g(x).]

S odkazem na výše zmíněné kongruence modulo (x− c) v F [x] a modulo f∗v Zp uvádíme nyní obecnou definici:

Definice 4. Nechť q je polynom stupně deg q ≥ 2 a f, g jsou dva polynomyz F [x]. Říkáme, že f je kongruentní s b modulo q (značíme f ≡ g (mod q)),jestliže f − g je je násobkem q.

Věta 6. Dva polynomy f, g ∈ F [x] jsou kongruentní modulo q právě tehdy,když jsou zbytky v eukleidovském dělení polynomem q navzájem asociované.Relace f ≡ g (mod q) je reflexivní, symetrická a tranzitivní (je to tedy relaceekvivalence). Navíc tato relace zachovává operace sčítání a násobení: jestližef ≡ g (mod q) a f ′ ≡ g′ (mod q), potom

f + f ′ ≡ g + g′ (mod q) a ff ′ ≡ gg′ (mod q).

Ekvivalenční třídu obsahující polynom f ∈ F [x] budeme značit

f̄ = {h ∈ F [x] | h ≡ f (mod q)}.

Uvědomte si, že existuje jednoznačný reprezentant ekvivalenční třídy f̄ 6= 0̄,speciálně jednoznačný monický polynom stupně menšího než deg q v f̄ : ozna-číme jej f∗.

Nyní označmeF [x] = F [x]

/〈q〉

množinu všech kongruenčních tříd modulo q. Stejně jako v případě celých číselZ = Zn, je F [x] okruh s operacemi sčítání f̄ + ḡ = f + g a násobení f̄ · ḡ = fg.Tyto operace jsou dobře definované pomocí reprezentantů (vzhledem k tvrze-ním o vlastnostech kongruencí tato definice nezávisí na výběru reprezentantů).Analogicky jako u celých čísel Z zde existuje (kanonický) homomorfismus

ϕ : F [x]→ F [x] = F [x]/〈q〉

tak, že ϕ(f) = f̄ .

Následující dvě tvrzení ilustrují podstatný rozdíl mezi ireducibilními a redu-cibilními polynomy.

Věta 7. F [x] = F [x]/〈q〉 má netriviální dělitele nuly právě tehdy, když q je

reducibilní.

Důkaz. Je zřejmé, že rovnost q = fg v F [x] implikuje rovnost f̄ ḡ = 0̄ z F [x].Na druhou stranu je-li q ireducibilní a f̄ 6= 0̄, ḡ 6= 0̄ z F [x], pak pro největší

13

společné dělitele platí (f∗, q) = 1 a (g∗, q) = 1. Proto také (f∗g∗, q) = 1, a tedyf̄ ḡ = fg 6= 0̄ z F [x].

Věta 8. Nechť p ∈ F [x] je ireducibilní. Potom F [x] = F [x]/〈p〉 je těleso.

Důkaz. Budeme postupovat obdobně jako u oboru integrity celých čísel Zvyužtím existence polynomů u a v takových, že uf∗ + vp = 1 pro libovolnýpolynom f ∈ F [x] takový, že f̄ 6= 0̄ z F [x].

Příklad (Konstrukce pole F (x) polynomiálních zlomků nad polemF ). Užitím stejného postupu („dvojicÿ prvků) jako při konstrukci pole racionál-ních čísel Q, sestrojte pole F (x) racionálních funkcí (polynomiálních zlomků)fg, kde f, g ∈ F [x] a g 6= 0.

Věta 9. Nechť f, g1, g2 ∈ F [x] jsou takové polynomy, že g1 a g2 jsou nesou-dělné a deg f < deg g1g2. Potom existuje jednoznačný rozklad

f

g1g2=f1g1+f2g2, kde fi ∈ F [x], deg fi < deg gi, i = 1, 2.

Věta 10. Nechť f, g ∈ F [x]. Potom existuje rozklad

f

gn=

f1gn−1

+h1gn, kde f1, h1 ∈ F [x] a deg h1 < deg g.

Proto existuje jednoznačný rozklad

f

gn=h1gn+

h2gn−1

+ · · ·+ hn−1g2+hng+ hn+1,

kde hi ∈ F [x] a deg hi < deg g pro všechna 1 ≤ i ≤ n.

Ilustrace.

(a) Pro F = R a p(x) = x2 + 1, R[x]/〈x2 + 1〉 ≃ C. Označíme-li totiž x =⊂,

tj. a+ bx = a+ b ⊂, máme

(a+b ⊂)+(c+d ⊂) = (a+c)+(b+d) ⊂ a (a+b ⊂)(c+d ⊂) = (ac−bd)+(ad+bc) ⊂ .

Zcela obecně platí, že

R[x]/〈x2 + α〉 ≃ C pro libovolné reálné α > 0.

Označíme-li x̄ = I, tj. a+ bx = a+ bI, máme

(a+bI)+(c+dI) = (a+c)+(b+d)I a (a+bI)(c+dI) = (ac−bdα)+(ad+bc)I.

Tedy, definujeme-li zobrazení

ψ : R[x]/〈x2 + α〉 → C vztahem ψ(a+ bI) = a+ b

√α i,

14

lze nahlédnout, že ψ je vzájemně jednoznačná korespondence (bijekce) splňující

ψ[(a+ bI) + (c+ dI)] = ψ(a+ bI) + ψ(c+ dI)

aψ[(a+ bI)(c+ dI)] = ψ[(ac− bdα) + (ad+ bc)I)] =

= (ac−bdα)+(ad+bc)√α ⊂= (a+b

√α ⊂)(c+d

√α ⊂) = ψ(a+ bI)ψ(c+ dI),

čímž je naše tvrzení dokázáno.

(b) F = Z2; p(x) = x2 + x+ 1 : Z2[x]/〈x2 + x+ 1〉 ≃ GF22 . Zde máme „novéÿ

čtyřprvkové těleso: Galoisovo těleso GF22 se zřejmou tabulkou pro sčítání a ná-sledující tabulkou pro násobení:

· 1 x 1 + x

1 1 x 1 + x

x x x+ 1 1

1 + x 1 + x 1 x

(c) F = Z2; p(x) = x3 + x + 1 : Z2[x]/〈x3 + x+ 1〉 ≃ GF23 . Toto Galoisovo

těleso má 23 = 8 prvků. Všimněte si, že jako v příkladě (b) obsahuje (jedno-značnou) kopii (prvotělesa) GF2 = Z2. Tabulka pro sčítání je opět zřejmá (samisi ji napište!), uvádíme zde tabulku pro násobení:

· 1 x x2 x+ 1 x2 + x x2 + x+ 1 x2 + 1

1 1 x x2 x+ 1 x2 + x x2 + x+ 1 x2 + 1

x x x2 x+ 1 x2 + x x2 + x+ 1 x2 + 1 1

x2 x2 x+ 1 x2 + x x2 + x+ 1 x2 + 1 1 x

x+ 1 x+ 1 x2 + x x2 + x+ 1 x2 + 1 1 x x2

x2 + x x2 + x x2 + x+ 1 x2 + 1 1 x x2 x+ 1

x2 + x+ 1 x2 + x+ 1 x2 + 1 1 x x2 x+ 1 x2 + x

x2 + 1 x2 + 1 1 x x2 x+ 1 x2 + x x2 + x+ 1

(d) F = Z2; p(x) = x3 + x2 + 1 : Z2[x]/〈x3 + x2 + 1〉 ≃ Z2[x]

/〈x3 + x+ 1〉.

Tabulka pro násobení je uvedená níže, a tedy výše zmíněný izomorfismus lzejednoduše zavést zobrazením x na x2 (tj. x2 + x na x).

15

· 1 x x2 x2 + 1 x2 + x+ 1 x+ 1 x2 + x

1 1 x x2 x2 + 1 x2 + x+ 1 x+ 1 x2 + x

x x x2 x2 + 1 x2 + x+ 1 x+ 1 x2 + x 1

x2 x2 x2 + 1 x2 + x+ 1 x+ 1 x2 + x 1 x

x2 + 1 x2 + 1 x2 + x+ 1 x+ 1 x2 + x 1 x x2

x2 + x+ 1 x2 + x+ 1 x+ 1 x2 + x 1 x x2 x2 + 1

x+ 1 x+ 1 x2 + x 1 x x2 x2 + 1 x2 + x+ 1

x2 + x x2 + 1 1 x x2 x2 + 1 x2 + x+ 1 x+ 1

(e) F = Z3; f(x) = x2 + 2 (f je reducibilní: x2 + 2 = (x + 1)(x + 2)). ZdeZ3[x]

/〈x2 + 2〉 ≃ GF 3 × GF3. Tabulka pro násobení je následující:

· x+ 2 2x+ 1 2x+ 2 x+ 1 1 2 x 2x

x+ 2 x+ 2 2x+ 1 0 0 x+ 2 2x+ 1 2x+ 1 x+ 2

2x+ 1 2x+ 1 x+ 2 0 0 2x+ 1 x+ 2 x+ 2 2x+ 1

2x+ 2 0 0 2x+ 2 x+ 1 2x+ 2 x+ 1 2x+ 2 x+ 1

x+ 1 0 0 x+ 1 2x+ 2 x+ 1 2x+ 2 x+ 1 2x+ 2

1 x+ 2 2x+ 1 2x+ 2 x+ 1 1 2 x 2x

2 2x+ 1 x+ 2 x+ 1 2x+ 2 2 1 2x x

x 2x+ 1 x+ 2 2x+ 2 x+ 1 x 2x 1 2

2x x+ 2 2x+ 1 x+ 1 2x+ 2 2x x 2 1

Všimněte si, že prvek x+ 2 je identita první kopie tělesa GF3 a prvek 2x+ 2je identita druhé kopie tělesa GF3.

(f) F = Z2; f∗(x) = x2 − x : Z2[x]/〈x2 − x〉 ≃ GF2 × GF2. Tabulka pro

násobení je následující:

16

· x x+ 1 1

x x 0 x

x+ 1 0 x+ 1 x+ 1

1 x x+ 1 1

Zde jsou x a x+ 1 opět identity příslušných kopií GF2.

(g) T = Z3; f∗(x) = x3 − x : Z3[x]/〈x3 − x〉 ≃ GF3 ×GF3 ×GF3. Tabulka pro

násobení (tj. jeho základní část) je následující:

· 2x2 + 1 x2 + 2 2x2 + 2x x2 + x 2x2 + x x2 + 2x . . .

2x2 + 1 2x2 + 1 x2 + 2 0 0 0 0 . . .

x2 + 2 x2 + 2 2x2 + 1 0 0 0 0 . . .

2x2 + 2x 0 0 2x2 + 2x x2 + x 0 0 . . .

x2 + x 0 0 x2 + x 2x2 + x 0 0 . . .

2x2 + x 0 0 0 0 2x2 + x x2 + 2x . . .

x2 + 2x 0 0 0 0 x2 + 2x 2x2 + x . . .

. . . . . . . . . . . . . . . . . . . . . . . .

Všimněte si, že identity příslušných tří kopií GF3, tj. 2x2 + 1, x2 + 2x a2x2 + x, odpovídají polynomiálním funkcím, které zobrazují prvky {0, 1, 2} (vtomto pořadí) na {1, 0, 0}, {0, 1, 0}, resp. {0, 0, 1}.

(h) Obecně platí, že algebra A všech zobrazení φ : Zp → Zp splňujeA ≃ Zp[x]

/〈xp − x〉 ≃ GFp

︸︷︷︸×GFp × · · · × GFpp-krát.

Věta 11 (KONEČNÁ TĚLESA). Pro každé prvočíslo p a každé přirozenéčíslo n existuje, až na izomorfismus, právě jedno těleso GFpn o q = pn prvcích.Tyto prvky jsou právě kořeny polynomu f∗(x) = xq − x ∈ GFpn [x]. Všechnakonečná tělesa jsou tohoto tvaru.

Nyní podáme ilustraci této věty pro p = 3 a n = 2. V tomto případě mápolynom x9 − x následující (jednoznačný) rozklad nad GF3 ≃ Z3:

x9 − x = x(x+ 1)(x+ 2)(x2 + 1)(x2 + x+ 2)(x+ 2x+ 2).

17

Pole GF32 ≃ Z3[x]/〈x2 + 1〉(≃ Z3[x]

/〈x2 + x+ 2〉 ≃ Z3[x]

/〈x2 + 2x+ 2〉) má

následující tabulku pro násobení:

· 1 2 x 2x x+ 1 2x+ 1 x+ 2 2x+ 2

1 1 2 x 2x x+ 1 2x+ 1 x+ 2 2x+ 2

2 2 1 2x x 2x+ 2 x+ 2 2x+ 1 x+ 1

x x 2x 2 1 x+ 2 x+ 1 2x+ 2 2x+ 1

2x 2x x 1 2 2x+ 1 2x+ 2 x+ 1 x+ 2

x+ 1 x+ 1 2x+ 2 x+ 2 2x+ 1 2x 2 1 x

2x+ 1 2x+ 1 x+ 2 x+ 1 2x+ 2 2 x 2x 1

x+ 2 x+ 2 2x+ 1 2x+ 2 x+ 1 1 2x x 2

2x+ 2 2x+ 2 x+ 1 2x+ 1 x+ 2 x 1 2 2x

Zde je 0 kořenem polynomu x ∈ GF32 [x], 1 je kořenem polynomu x+2 a 2 jekořenem polynomu x+1. Navíc x a 2x jsou kořeny polynomu x2+1 = (x−x)(x−2x), x+ 1 a 2x+ 1 kořeny polynomu x2+x+2 = (x−x+ 1)(x−2x+ 1) a x+ 2a 2x+ 2 jsou kořeny polynomu x2+2x+2 = (x−x+ 2)(x−2x+ 2) ∈ GF32 [x].

Důkaz věty 11. Nechť F je konečné pole. Jak už jsme ukázali v předchozíkapitole, F obsahuje (jednoznačně určené) prvopole Zp pro jisté prvočíslo p.

Pole F je tedy konečně dimenzionálním vektorovým prostorem nad polemZp. Nechť dimFZp = n, a {b1, b2, . . . , bn} ⊆ F je báze vektorového prostoruFZp . To znamená, že každý prvek a pole F má jednoznačný tvar (lineárníkombinace)

a = a1b1 + a2b2 + · · ·+ anbn, kde a1, a2, . . . , an ∈ Zp.

Počet prvků pole F je tedy q = pn.

Množina M = F \ {0} nenulových prvků pole F tvoří multiplikatiní grupupole F , která má tedy q − 1 = pn − 1 prvků. Proto, pro každý nenulový prvekg ∈ F , musí být mezi mocninami

g0 = 1, g, g2, g3, . . . , gq−1

dva prvky stejné:gk = gl pro 1 ≤ k < l ≤ q − 1.

To znamená, že existuje s = l − k > 0 tak, že gs = 1. Nechť d je nejmenšípřirozené číslo splňující gd = 1. Je tedy C = {g, g2, . . . , gd = 1} (cyklická)

18

podgrupa grupy M , jež má d prvků, tj. je řádu d. Definujme na M relaci ∼pomocí

x ∼ y právě tehdy, když x = ygs, 1 ≤ s ≤ d.Relace ∼ je zřejmě ekvivalence na M a všechny třídy ekvivalence

xC = {xgs | 1 ≤ s ≤ d}

mají tentýž počet prvků grupy M , totiž d. Je-li tedy počet tříd ekvivalence t,q − 1 = dt, a proto pro každý prvek a ∈M platí

aq−1 = (ad)t = 1t = 1.

Jsou tedy nenulové prvky pole F kořeny polynomu xq−1 − 1 ∈ F [x], nebolivšechny prvky pole F jsou kořeny polynomu

f⋆(x) = xq − x ∈ F [x].

Proto

f⋆(x) =q

∏

r=1

(x− ar), kde ar, 1 ≤ r ≤ q

jsou právě všechny prvky pole F . Pole F je tedy (až na izomorfismus jedno-značně určené) pole o q = pn prvcích, které obdržíme rozšířením pole Zp ad-junkcí kořenů polynomu f⋆(x) = xq−x ∈ Zp[x] způsobem, který jsme naznačiliv předchozích příkladech.

Připomeňme, že v každém poli F charakteristiky p (tj. poli, jež obsahujepodpole Zp) platí

(x± y)p = xp ± yp pro všechny prvky x, y ∈ F.

To plyne ihned z binomické věty a z toho, že

(p

t

)

=p!

t! (p− t)! je dělitelné ppro všechna 0 < t < p.

Proto též(x± y)q = xq ± yq pro q = pn.

Odtud tedy plyne, že v poli F ⊇ Zp mající vlastnost, že polynom f⋆(x) =xq − x ∈ F [x] lze vyjádřit ve tvaru součinu lineárních polynomů, tj. v poli,které obdržíme např. adjunkcí kořenů polynomu xq−x ∈ Zp[x],množina všech qkořenů tvoří podpole P . Zbývá tedy pouze ukázat, že polynom f⋆ nemá více-násobné kořeny, tj. že všechny jeho kořeny jsou různé, a tím uzavřít důkaz,že P má q = pn prvků a že tedy pro každé prvočíslo p a každé přirozené číslo nexistuje (až na izomorfizmus) právě jedno pole GFpn o pn prvcích.

Podejme elementární důkaz, že kořeny polynomu f⋆ jsou jednoduché (a tímse vyhneme pojmu derivace polynomu, běžně v této souvislosti použit). Kdyby

19

měl polynom f⋆ vícenásobný kořen a, nutně by a 6= 0 a v P [x] by existovalrozklad

xq − x = (x2 − 2ax+ 1)(xq−2 + c3xq−3 + c4xq−4 + · · ·+ cq−2x2 + cq−1x+ cq).

Vynásobením a porovnáním koeficientů dostáváme cq = (q − 1)aq−2, což je vesporu s tím, že cq musí být zřejmě 0.

Poznámka 5. Využitím vlastností grupy odmocnin z jedné, lze popsatstrukturu pole GFpn ještě blíže: Multiplikativní grupa tohoto pole je vždycyklická (generovaná tak tzv. primitivním pn − 1-ím kořenem z jedné) a svazpodpolí pole GFpn je izomorfní svazu všech dělitelů přirozeného čísla n. Jinýmislovy, pro každý dělitel d čisla n existuje v poli GFpn právě jedno podpoleGFpd , a tím jsou vyčerpána všechna podpole pole GFpn .

Poznámka 6. Jestliže F1 ⊂ F2 jsou dvě pole (řekněme Q ⊂ R či R ⊂ C),potom každý polynom z F1[x] lze též považovat za polynom z F2[x]. Polynom,který je ireducibilní nad F1 nemusí být již ireducibilní nad F2. Nad C je (x− ⊂)(x+ ⊂) rozklad polynomu x2 + 1, který je ireducibilní nad R.

Příklad. Rozložte F (x) = x6 + 1 na ireducibilní faktory nad: (a) C, (b) R,(c) Q.

Rozhodnout, zda daný polynom nad polem F je reducibilní či ireducibilní, jedůležitý, ale obecně velmi obtížný, úkol. Uveďme zde jedno užitečné kritérium(včetně důležité aplikace na tak zvané cyklotomické polynomy) podávající po-stačující podmínky pro to, aby (celočíselný) polynom f ∈ Z[x] byl ireducibilnínad polem racionálních čísel Q (tedy jako f ∈ Q[x]).

Věta 12. Eisensteinovo kritérium. Ferdinand Gotthold Eisenstein(1823–1852). Nechť

f(x) = anxn + an−1x

n−1 + · · ·+ a1x+ a0 ∈ Z[x], n ≤ 1.

Pro prvočíslo p, nechť platí

p |6 an, p | at, 0 ≤ t ≤ n− 1, p2 |6 a0.

Potom je f ∈ Q[x] ireducibilní.

Důkaz. Využijme epimorfismu ϕ : Z[x] → Zp[x], který je rozšířením kano-nického epimorfismu ϕ : Z → Zp. Potom ϕ(f) = f splňuje

f(x) = anxn kde 0 6= an = ϕ(an) ∈ Zp[x]. (⋆)

Kdyby byl polynom f reducibilní, měli bychom rozklad f = gh, g ∈ Z[x],h ∈ Z[x], kde

g(x) = bkxk+bk−1x

k−1+ · · ·+b1x+b0, h(x) = clxl+cl−1xl−1+ · · ·+c1x+c0,

20

s k ≥ 1, l ≥ 1, k+ l = n a bk 6= 0, cl 6= 0. Pišme ϕ(g) = g, ϕ(h) = h, ϕ(bt) = bta ϕ(ct) = ct pro všechny indexy t. Jelikož bk cl = an 6= 0 a b0 c0 = a0 = 0,dostáváme

g(x) = bkxk + · · ·+ brxr, kde bk 6= 0, br 6= 0, r ≥ 1

ah(x) = clx

l + · · ·+ c1x+ c0, kde cl 6= 0, c0 6= 0, s ≥ 1.Zde c0 6= 0, neboť p2 |6 a0. To ovšem vede ke sporu s (⋆). Kritérium je dokázáno.

Příklad (důležitý). Polynom (jehož kořeny jsou odmocniny z jedné)

f(x) = xp−1 + xp−2 + · · ·+ x2 + x+ 1 ∈ Z[x], kde p je prvočíslo,

je ireducibilní. Eisensteinovo kriterium nemůžeme užít přímo. Avšak polynomf ∈ Z[x] je ireducibilní právě tehdy, když polynom g ∈ Z[x], kde g(x) = f(x+1)je ireducibilní. Snadno se přesvědčíme, že

g(x) = xp−1 +

(p

1

)

xp−2 +

(p

2

)

xp−3 + · · ·+(

p

p− 2

)

x+

(p

p− 1

)

.

Nyní, jak už víme z dřívějška, všechny koeficienty (kromě při nejvyšší mocniněxp−1) jsou dělitelny prvočíslem p a navíc poslední koeficient p není dělitelnýčtvercem p. Proto můžeme aplikovar Eisensteinovo kritérium, a vše plyne.

Zakončeme tento odstavec několika poněkud náročnějšími úlohami.

Úlohy

1. Nechť f je libovolný polynom nad polem racionálních čísel Q : f(x) ∈ Q[x].Dokažte, že existuje jednoznačně polynom g(x) ∈ Q[x] takový, že

1

2

[g(x+ 1) + g(x− 1)

]= f(x).

[Nápověda. Pro každé n ≥ 0, zvolme specielně fn(x) = xn a definujme poly-nomy gn(x) ∈ Q[x] pomocí

1

2

[gn(x+ 1) + gn(x− 1)

]= xn.

Potomg0(x) = 1 a derivace g

′n(x) = ngn−1(x) pro n ≥ 1.

Odtud

gn(x) = n!

∫ x

an

(· · · (∫ x2

a2

(

∫ x1

a1

dx) dx1) . . . )dxn−1,

kde at = 1 pro sudé t a at = 0 pro liché t.

21

Poznamenejme, že absolutními členy polynomů gn(x) jsou Eulerova čísla Endefinovaná pomocí této Taylorovy řady:

2

ex + e−x=

∞∑

n=0

Enn !xn.

Zde jsou uvedeny polynomy gn(x) pro n = 0, 1, 2, 3, 4, 5, 6, 7 a 8:

g0(x) = 1,

g1(x) = x,

g2(x) = x2 − 1,

g3(x) = x3 − 3x,

g4(x) = x4 − 6x2 + 5,

g5(x) = x5 − 10x3 + 25x,

g6(x) = x6 − 15x4 + 75x2 − 61,

g7(x) = x7 − 21x5 + 175x3 − 475x,

g8(x) = x8 − 28x6 + 350x4 − 1708x2 + 1385.

2. Nechť f je libovolný polynom nad polem racionálních čísel Q : f(x) ∈ Q[x].Dokažte, že existuje jednoznačně polynom g(x) ∈ Q[x] takový, že

g(0) = 0 a g(x)− g(x− 1) = f(x).

[Nápověda. Stejně jako v předchozí úloze, je-li f(x) =∑n

t=0 atxt, potom

koeficienty polynomu g(x) =∑n+1

t=1 btxt jsou jednoznačným řešením soustavy

n+1 lineárních rovnic Ax = a, kde a = (a0, a1, . . . , an)T a determinant maticeA je roven (n+ 1)!.

Zřejmě, g(1) = f(1) a g(−1) = −f(0). Obecně,

g(n) =n∑

t=1

f(t) a g(−n) = −n−1∑

t=0

f(−t).

Specielně, pro f(x) = xk označme příslušný polynom g(x) = Sk(x); tedy

Sk(n) =n∑

t=1

tk.]

3. Definujme, pro každé reálné čislo x,(x0

)= 1 a pro k ≥ 1,

(x

k

)

=1

k!x(x− 1) . . . (x− k + 1).

22

Dokažte tato překvapující tvrzení:

(a) Nechť f(x) ∈ Z[x] je (celočíselný) polynom n-tého stupně, jehož hodnotav každém celočíselném bodě z je násobkem faktoriálu n!. Potom

f(x) =n∑

k=0

n!an−k+1

(x

k

)

, (⋆)

kde an−k+1 jsou celá čísla.

(b) Polynom (⋆), kde an−k+1 jsou libovolná celá čísla, má v každém celočísel-ném bodě z hodnotu, která je je násobkem faktoriálu n!.

K dokonalému porozumění výše uvedených tvrzení nám napomůže následu-jící obecnější formulace.

(c) Nechť f(x) ∈ Z[x] je (celočíselný) polynom n-tého stupně, jehož hodnotyf(z) jsou dělitelné faktoriálem n! pro z = 0, 1, . . . , n − 1. Potom jsou hodnotyf(z) dělitelné faktoriálem n! pro všechna celá čísla z ∈ Z a f má tvar (⋆), kdean−k+1 jsou celá čísla.

(d) Dedukujte, že hodnoty az4+(6a−4b)z3+(11a−12b+12c)z2+(6a−8b+12c)zjsou pro všechna celá čísla z násobkem čísla 24.

4. Interpolace funkcí pomocí polynomů. Pro posloupnost a = (a1, a2, . . . , an, . . . )reálných čísel definujme diferenční posloupnost D(a) posloupnosti a pomocí

D(a) = (a2 − a1, a3 − a2, . . . , an+1 − an, . . . ).

Rekurrentně definujme D1(a) = D(a) a Dk+1(a) = D(Dk(a)) pro k ≥ 1.Pišme a = D0(a). První člen posloupnosti Dn(a) označme bn+1; tedy b1 = a1,b2 = a2 − a1, . . . Dále pišme b = ∆(a) = (b1, b2, . . . , bn, . . . ).Reálný semipolynom fk(x) definujme rekurentně takto: f1(x) = 0 pro x ≤ 0

a P1(x) = 1 pro x > 0; pro k > 1,

fk+1(x) = 0 pro x ≤ k a Pk+1(x) =x− kk

Pk(x) pro x > k.

(a) Dokažte: Nechť f je reálná funkce definovaná pro x ≥ 0. Uvažujme posloup-nost

af = (a1 = f(1), a2 = f(2), . . . , an = f(n), . . . ).

Potom interpolační funkce If funkce f , definovaná pomocí

If (x) =∞∑

k=1

bk Dk(x),

kde bf = ∆(a) = (b1, b2, . . . , bn, . . . )s, splňuje rovnosti

If (n) = f(n) pro všechna přirozená čísla n.

23

(b) Ověřte: Jestliže f(x) = 2x−1, potom

a = (1, 2, 4, 8, . . . , 2n−1, . . . ),b = ∆(a) = (1, 1, 1, 1, . . . , 1, . . . ),

a tedy

If (n) =∞∑

k=1

Pk(n) = 2n−1.

Jestliže f(x) = sin πx2 , potom

a = (1, 0,−1, 0, 1, 0,−1, 0, . . . ), b = (1,−1, 0, 2,−22, 23,−24, 25, . . . ),

a tedy

If (n) = 2− n−∞∑

k=1

(−2)kPk+3(n) = sinnπ

2.

3. Polynomy více neurčitých, symetrické funkce

Obraťme nyní pozornost na jednu velmi důležitou třídu polynomů nad (libo-volným) polem F , totiž řídu symetrických polynomů (symetrických funkcí). Uždříve jsme upozornili, že je důležité definovat polynomy nad libovolným obo-rem integrity. A této konstrukce využijeme při definici polynomů n neurčitýchnad daným polem F :

F [x] = F [x1, x2, . . . , xn] = (...((F [x1])[x2])[x2] . . . )[xn].

Je-li σ permutace přirozených čísel (1, 2, . . . , n) a f ∈ F [x], označme fσ ∈ F [x]polynom definovaný pomocí fσ(x1, x2, . . . , xn) = f(xσ(1), xσ(2), . . . , xσ(n)). Po-všimněme si, že pro dvě permutace σ1, σ2, (P σ1)σ2 = P σ1σ2 , tj. že symetrickágrupa Σn všech permutací n prvků operuje na oboru integrity F [x].

Definice 1. Polynom f = f(x1, x2, . . . , xn) ∈ F [x] se nazývá symetrickýpolynom, jestliže f = fσ pro každou permutaci σ ∈ Σn.

Poznámka 1. Evidentně, f je symetrický polynom právě tehdy, jestliže sef = f(x1, x2, . . . , xn) nezmění žádnou transpozicí dvou neurčitých.

Věta 1. Množina všech symetrických polynomů je podokruhem (podoboremintegrity) okruhu (oboru integrity) F [x] ( který obsahuje F ).

Definice 2. Polynom f ∈ F [x] je jednoduchý symetrický polynom, jestližese nedá vyjádřit jako součet dvou nenulových symetrických polynomů.

Následující tvrzení je triviální.

24

Věta 2. Každý symetrický polynom je (konečným) součtem jednoduchýchpolynomů.

Jednoduché polynomy jsou charakterizovány velice snadno: Každý je souč-tem členů, které obdržíme všemi permutacemi neurčitých jednoho z nich. Jed-noduchý symetrický polynom f je tedy určen vedoucím členem (členem nejvyš-šího stupně) axk11 x

k22 . . . x

knn splňujícím nerovnosti k1 ≥ k2 ≥ · · · ≥ kn a budeme

jej označovat symbolem P = Σaxk11 xk22 . . . x

knn (a jeho stupeň symbolem st(f)).

Nyní je snadné popsat (lineární) uspořádání všech jednoduchých symetrickýchpolynomů pomocí lexikografického uspořádání jejich vedoucích (definujících)členů:

Σaxk11 xk22 . . . x

knn ≺ Σbxl11 xl22 . . . xlnn ,

jestliže k1 = l1, k2 = l2, . . . , ks = ls, ks+1 < ls+1 pro nějaké s ≤ n.Definujme následující dva typy jednoduchých symetrických polynomů:

St(x1, x2, . . . , xn) = Σxt1 = x

t1 + x

t2 + · · ·+ xtn pro všechna 1 ≤ t

a elementární symetrické polynomy

Et(x1, x2, . . . , xn) = Σx1x2 . . . xt pro všechna 1 ≤ t ≤ n.

Připomeňme, že hodnoty elementárních symetrických polynomů v kořenechα1, α2, . . . , αn algebraické rovnice

xn + a1xn−1 + a2x

n−2 + · · ·+ an−2x2 + an−1x+ an = 0

splňují Viètovy formule at = (−1)tEt(α1, α2, . . . , αn), 1 ≤ t ≤ n.V následující větě uvidíme další důležitou vlastnost n elementárních symet-

rických polynomů: Generují (a to jednoznačně) všechny symetrické polynomy!Nejprve však formulujme dvě pomocná tvrzení, která nám usnadní důkaz tétověty.

Pomocná věta 1. Nechť f ∈ F [x] je jednoduchý symetrický polynom. Po-tom existuje symetrický polynom g ∈ F [x] takový, že polynom f1 ∈ F [x] defi-novaný vztahem

f1(x1, x2, . . . , xn) = f(x1, x2, . . . , xn)−

g(E1(x1, x2, . . . , xn), E2(x1, x2, . . . , xn), . . . , En(x1, x2, . . . , xn)

)

je součtem jednoduchých symetrických polynomů, z nichž každý má stupeňmenší než polynom f .

Důkaz. Je-li f = Σaxk11 xk22 . . . x

knn , kde kr 6= 0, kr+1 = 0, položme

g(E1, E2, . . . , En) = Ekrr E

kr−1−krr−1 . . . E

k1−k21 ,

25

tj.g(x1, x2, . . . , xn) = (Σx1x2 . . . xr)

kr (Σx1x2 . . . xr−1)kr−1−kr ·

(Σx1x2 . . . xr−2)kr−2−kr−1 . . . . . . (Σx1)

k1−k2 .

Po odečtení od polynomu f členy nejvyššího stupně zmizí a vše je jasné.

Pomocná věta 2. Elementární symetrické polynomy jsou nad F algebraickynezávislé, tj. je-li pro h ∈ F [x],

h(E1(x1, x2, . . . , xn), E2(x1, x2, . . . , xn), . . . , En(x1, x2, . . . , xn)

)= 0, (∗∗)

potom h je nulový polynom.

Důkaz. Není-li tomu tak, nechť h 6= 0 je polynom nejnižšího stupně, kterýsplňuje podmínku (**). Zapišme h ve tvaru polynomu v xn s koeficienty ht ∈K[x1, x2, . . . , xn−1]:

h(x1, x2, . . . , xn) = h0(x1, x2, . . . , xn−1) + h1(x1, x2, . . . , xn−1)xn + · · ·+

+hs(x1, x2, . . . , xn−1)xsn.

Zde je h0 6= 0. Jinak by totiž h(x1, x2, . . . , xn) = xnh̃(x1, x2, . . . , xn), a tedyEnh̃(E1, E2, . . . , En) = 0. Potom však nutně h̃(E1, E2, . . . , En) = 0, přičemžst(h̃) < st(h); to je ve sporu s výběrem polynomu h.

Dosaďme do předchozí rovnosti za xt elementární polynomy Et:

0 = h0(E1, . . . , En−1) + h1(E1, . . . , En−1)En + · · ·+ hs(E1, . . . , En−1)Esn.

Jestliže v této rovnosti pro x1, x2, . . . , xn dosadíme xn = 0, dostáváme

h0(Ẽ1, Ẽ2, . . . , Ẽn−1) = 0,

kdeẼt(x1, x2, . . . , xn−1) = Et(x1, x2, . . . , xn−1, 0)

jsou právě elementární symetrické polynomy v n−1 neurčitých x1, x2, . . . , xn−1.K dokončení důkazu stačí užít matematické indukce.

Nyní už formulujme slíbenou hlavní větu o symetrických polynomech.

Věta 3. Pro každý symetrický polynom f ∈ F [x] existuje jednoznačně poly-nom g ∈ F [E1, E2, . . . , En] takový, že

f(x1, . . . , xn) = g(E1(x1, . . . , xn), E2(x1, . . . , xn), . . . , En(x1, . . . , xn)

).

Důkaz. Existence polynomu g plyne (užitím matematické indukce) z prvnípomocné věty. Jednoznačnost plyne z druhé pomocné věty.

26

Důsledek 1. (Přeformulování hlavní věty). Podobor integrity všech symet-rických polynomů v F [x] je izomorfní s oborem integrity F [E1, E2, . . . , En].

Připojme ještě několik poznámek o jednoduchých symetrických polyno-mech St. Stejně jako pro elementární symetrické polynomy, i zde platí ná-sledující věta.

Věta 4. Pro každý symetrický polynom f ∈ F [x] existuje jednoznačně poly-nom h ∈ F [S1, S2, . . . , Sn] takový, že

f(x1, . . . , xn) = h(S1(x1, . . . , xn), S2(x1, . . . , xn), . . . , Sn(x1, . . . , xn)

).

Poznamenejme, že mezi polynomy St a Et v n neurčitých (tj. z F [x]) existujevelmi blízký vztah, vyjádřený pro každé d, Newtonovým vzorcem

Sd = E1Sd−1 − E2Sd−2 + · · ·+ (−1)k+1EkSd−k + · · ·

+(−1)dEd−1S1 + (−1)d+1S0Ed,

kde S0 = d a Et = 0 pro t > n.

Odtud jde, rekurzivně, snadno vyjádřit každý polynom Sd jako polynomv Et, a naopak každý elementární symetrický polynom Ed jako polynom v St.

Zde doplníme několik ilustraci a úloh.