ALGEBRA II PRO INFORMATIKY

6. Ideály a kongruence na okruzích

Poznámka 6.1. Bud’ C uzávěrový systém obsažený v systému všech ekvivalencí na množině A. Necht’ pro N ⊆ P(A) a e ∈ A platí:

(a) [e]_{ρ} ∈ N pro každé ρ ∈ C,

(b) pro každé N ∈ N existuje takové ρ ∈ C, že N = [e]_{ρ},

(c) pro každé ρ, η ∈ C platí, že [e]_{ρ} ⊆ [e]_{η} ⇒ ρ ⊆ η. Pak N je uzávěrový systém na A (a tedy svaz) a zobrazení φ : C → N dané předpisem φ(ρ) = [e]_{ρ} je izomorfismus svazů.

Důkaz. Nejprve ukážeme, že je N uzávěrový systém. Protože A × A ∈ C, máme A = [e]_{A×A} ∈ N díky (a). Vezmeme-li N_{i} ∈ N, i ∈ I, pak podle (b) existuje pro každé i ∈ I taková ekvivalence ρ_{i} ∈ C, že N_{i} = [e]_{ρ_{i}}. Protože je C uzávěrový systém, tedy ⋂_{i∈I} ρ_{i} ∈ C, dostáváme ⋂_{i∈I} N_{i} = ⋂_{i∈I}[e]_{ρ_{i}} = [e]_{⋂_{i∈I} ρ_{i}} ∈ N opět díky (a).

Nyní stačí podle 4.9 ověřit, že je φ dobře definovaná bijekce a že φ i φ^{−1} jsou monotónní vzhledem k inkluzi. Korektnost definice přitom zaručuje podmínka (a), podmínka (b) říká, že je φ na N, a z podmínky (c) plyne, že jde o prosté zobrazení. Konečně, je-li ρ ⊆ η, pak [e]_{ρ} ⊆ [e]_{η} pro každou dvojici ekvivalencí ρ a η, což zaručuje monotónii φ, a monotónie φ^{−1} je přímo obsahem podmínky (c). □

Věta 6.2. (1) Všechny normální podgrupy libovolné grupy G(·) tvoří spolu s inkluzí svaz a zobrazení ρ → [1]_{ρ} je izomorfismus svazu všech kongruencí na grupě G(·) a svazu všech normálních podgrup.

(2) Všechny kongruence a všechny ideály okruhu R(+, ·, −, 0, 1) tvoří spolu s inkluzí svazy a zobrazení ρ → [0]_{ρ} je izomorfismus svazu všech kongruencí a svazu všech ideálů okruhu R.

Důkaz. (1) Označme symbolem C množinu všech kongruencí na G(·), tj. ekvivalencí slučitelných s operací · (viz 3.3(3)), symbolem N množinu všech normálních podgrup G(·) a symbolem e neutrální prvek G(·). Z 4.5 plyne, že je C uzávěrový systém a 1.16 zaručuje, že jsou splněny předpoklady (a), (b), (c) Poznámky 6.1, odkud plyne závěr.

(2) Nejprve dokážeme, že ekvivalence ρ je kongruence na R(+, ·, −, 0, 1), právě když [0]_{ρ} je ideál a (a, b) ∈ ρ ⇔ a − b ∈ [0]_{ρ}.. Je-li ρ je kongruence na okruhu R, pak jde také o kongruenci grupy R(+), proto je [0]_{ρ} podle 1.16 podgrupou R(+) a (a, b) ∈ ρ ⇔ a − b ∈ [0]_{ρ}. Zbývá ověřit, že jde o ideál. Zvolme i ∈ [0]_{ρ} a r ∈ R, tedy (i, 0) ∈ ρ a (r, r) ∈ ρ, proto (ir, 0) = (ir, 0r) ∈ ρ a (ri, 0) = (ri, r0) ∈ ρ, tedy ir, ri ∈ I.

Předpokládejme, že je I je ideál a definujme (a, b) ∈ ρ ⇔ a − b ∈ I. Potom I = [0]_{ρ} a podle 1.16 je ρ slučitelné s +. Zvolme (a, b), (c, d) ∈ ρ. Pak a − b, c − d, (a − b)c, b(c − d) ∈ [0]_{ρ}, a tudíž −a + b ∈ [0]_{ρ} a ac − bd = (a − b)c + b(c − d) ∈ [0]_{ρ}, proto (−a, −b), (a·c, b·d) ∈ ρ, čímž jsme ověřili, že je ρ kongruence na R(+, ·, −, 0, 1).

Date: 26.9.2013.

Nyní stejným způsobem jako v důkazu (1) nahlédneme že jsou pro e = 0, C množinu všech kongruencí a N množinu všech ideálů okruhu R(+, ·, −, 0, 1) splněny předpoklady 6.1, odkud dostáváme závěr. □

Obdobně jako v případu faktorizace grup podle normálních podgrup budeme faktor okruhu R podle kongruence jednoznačně odpovídající ideálu I značit R/I. Poznamenejme, že faktorová algebra R/I je opět okruh.

Definice. Okruh R(+, ·, −, 0, 1) se nazývá komutativní, je-li operace · komutativní. Komutativní okruh nazveme oborem integrity, platí-li pro každé a, b ∈ R, že a·b = 0 implikuje a = 0 nebo b = 0.

Podokruhem okruhu R(+, ·, −, 0, 1) budeme rozumět každou podalgebru algebry R(+, ·, −, 0, 1).

Příklad 6.3. (1) Okruhu celých čísel Z(+, ·, −, 0, 1) je oborem integrity. (2) Každé komutativní těleso i každý jeho podokruh jsou obory integrity.

(3) Okruh reálných polynomů R[x](+, ·, −, 0, 1) je obor integrity.

Následující tvrzení zobecňuje dobře známou konstrukci zlomků pro všechny obory integrity. Ukážeme, že každý obor integrity lze chápat jako podokruh nějakého tělesa, tedy bod (2) předchozího příkladu je jediným možným typem příkladu oboru integrity.

Uvažujme obor integrity R(+, ·, −, 0, 1), a definujme algebru F (+, ·, −, 0, 1), kde F = R × (R \ {0}) s operacemi: (a, b) · (c, d) = (a · c, b · d), (a, b) + (c, d) = (a · d + b · c, b·d), −(a, b) = (−a, b), 0 = (0, 1) a 1 = (1, 1). Na algebře F (+, ·, −, 0, 1) konečně definujme relaci ∼ předpisem (a, b) ∼ (c, d) ⇔ a · d = b · c.

Věta 6.4. Pro algebru F (+, ·, −, 0, 1) platí:

(1) F (+) a F (·) jsou komutativní monoidy,

(2) ∼ je kongruence na F (+, ·, −, 0, 1) a (0, a) ∼ 0 a (a, a) ∼ 1 pro každé a ∈ R \ {0},

(3) F/ ∼ je komutativní těleso,

(4) zobrazení σ : R → F/ ∼ dané předpisem σ(r) = [(r, 1)]_{∼} je prostý okruhový homomorfismus.

Důkaz. Vezměme (a, b), (c, d), (e, f) ∈ F.

(1) Postupujeme zcela přímočaře podle definice.

(a, b) + ((c, d) + (e, f)) = (a, b) + ((cf + de, df)) = ((adf + b(cf + de), bdf)) =

= ((adf + bcf + bde, bdf)) = (((ad + bc)f + bde, bdf)) = ((a, b) + (c, d)) + (e, f),

(a, b) + (c, d) = (ad + bc, bd) = (cb + ad, bd) = (c, d) + (a, b).

Ověřili jsme, že je operace + asociativní a komutativní. Uvážíme-li, že (a, b) + (0, 1) = (a, b), máme dokázáno, že F (+) je komutativní monoid. Totéž provedeme pro násobení:

(a, b) · ((c, d) · (e, f)) = (a, b) · ((ce, df)) = (ace, bdf)) = ((a, b) · (c, d)) · (e, f),

dále (a, b) · (c, d) = (c, d) · (a, b) a (a, b) · (1, 1) = (a, b), proto i F (·) je komutativní monoid.

(2) Předně uvažme, že je relace ∼ zřejmě reflexivní a symetrická a předpokládejme, že (a, b) ∼ (c, d) a (c, d) ∼ (e, f), tedy ad = bc a cf = de. Potom adf = bcf = bde, a proto (af−be)d = 0. Jelikož d ≠ 0, dostáváme z definice oboru integrity, že af−be = 0, a tudíž (a, b) ∼ (e, f). Díky pozorování Příkladu 3.3 z minulého semestru zbývá ověřit slučitelnost ∼ s operacemi +, · a −. Předpokládejme, že (a_{i}, b_{i}) ∼ (c_{i}, d_{i}) tedy a_{i}d_{i} = c_{i}b_{i} pro i = 1, 2. Proto (a_{1}b_{2} + b_{1}a_{2})d_{1}d_{2} = a_{1}d_{1} · b_{2}d_{2} + a_{2}d_{2} · b_{1}d_{1} = c_{1}b_{1}·b_{2}d_{2}+c_{2}b_{2}·b_{1}d_{1} = (c_{1}d_{2}+d_{1}c_{2})b_{1}b_{2}, tedy (a_{1}, b_{1})+(a_{2}, b_{2}) ∼ (c_{1}, d_{1})+(c_{2}, d_{2}). Dále a_{1}a_{2}d_{1}d_{2} = c_{1}c_{2}b_{1}b_{2}, tudíž (a_{1}, b_{1}) · (a_{2}, b_{2}) ∼ (c_{1}, d_{1}) · (c_{2}, d_{2}) a konečně (−a_{1}, b_{1}) ∼ (−c_{1}, d_{1}) podle 5.2(2). Vztahy (0, a) ∼ 0 a (a, a) ∼ 1 plynou okamžitě z definice ∼.

(3) Díky (1), (2) a 3.10 už víme, že F/ ∼ (+) a F/ ∼ (·) jsou komutativní monoidy. Zbývá tedy dokázat existenci opačných prvků monoidu F/ ∼ (+) a distributivitu. Označme \frac{a}{b} rozkladové třídy [(a, b)]_{∼}. Všimněme si, že \frac{ad}{bd} = \frac{ac}{bc} pro každé nenulové b, d ∈ R, protože (ad, bd) ∼ (ac, bc). Nyní snadno spočítáme, že

\frac{a}{b} + \frac{−a}{b} = \frac{a + (−a)}{bb} = \frac{0}{bb} = 0,

\frac{a}{b} · \frac{c}{d} + \frac{a}{b} · \frac{e}{f} = \frac{acbf + bdae}{bdbf} = \frac{acf + ade}{bdf} = \frac{a}{b} · \frac{cf + de}{df} = \frac{a}{b} · (\frac{c}{d} + \frac{e}{f}).

Konečně, zvolíme-li \frac{a}{b} ≠ 0, pak (a, b) ≁ (0, 1), tedy a ≠ 0, a proto \frac{b}{a} ∈ F a \frac{a}{b} · \frac{b}{a} = 1. Tím jsme dokázali, že každý nenulový prvek F ¨ je invertibilní, a proto je F/ ∼ komutativní těleso.

(4) Okamžitě vidíme, že je \frac{a}{1} · \frac{b}{1} = \frac{a·b}{1}, \frac{a}{1} + \frac{b}{1} = \frac{a+b}{1} a σ(1) = 1, proto je σ homomorfismus. Konečně, je-li σ(a) = σ(b), pak a = b, tedy jde o prostý homomorfismus. □

Definice. Komutativní těleso F/ ∼ budeme nazývat podílovým tělesem okruhu R a jeho prvky budeme značit \frac{a}{b} = [(a, b)]_{∼}.

Příklad 6.5. (1) Těleso racionálních čísel Q(+, ·, −, 0, 1) je podílovým tělesem okruhu celých čísel Z(+, ·, −, 0, 1).

(2) Těleso racionálních lomených funkcí je podílovým tělesem okruhu reálných polynomů R[x](+, ·, −, 0, 1).

Definice. O okruhu R(+, ·, −, 0, 1) řekneme, že je Booleův, je-li to komutativní okruh a pro každé r ∈ R platí, že r · r = r a r + r = 0.

Příklad 6.6. Algebra P(X)(÷, ∩, Id_{P(X)}, ∅, X), kde ÷ značí symetrickou diferenci, je pro každou neprázdnou množinu X Booleův okruh. Je-li Y ⊆ X, potom je zjevně P(Y) ideálem okruhu P(X)(÷, ∩, Id_{P(X)}, ∅, X). Je-li naopak I ideál, všimněme si, že je uzavřen na konečná sjednocení svých prvků. Díky indukčnímu argumentu nám stačí ověřit, že A∪B ∈ I pro každé A, B ∈ I. Ovšem A∪B = (A÷B)÷(A∩B) ∈ I, protože A ÷ B, A ∩ B ∈ I.

Uvažujme X konečnou množinu a bud’ I ideál. Pak je I konečný, a proto Y = ⋃ I ∈ I. Tudíž I = P(Y) = Y ∩ P(X) a v okruhu P(X)(÷, ∩, Id_{P(X)}, ∅, X) jsou všechny ideály hlavní.

Věta 6.7. (1) Necht’ S_{A} = S(∨, ∧, 0, 1, ′) je Booleova algebra. Definujeme-li na S binární operaci + předpisem a + b = (a ∧ b′) ∨ (a′ ∧ b), pak S_{0} = S(+, ∧, Id_{S}, 0, 1) je Booleův okruh. Navíc P je podalgebra resp. ρ kongruence S_{A}, právě když je P podalgebra resp. ρ kongruence S_{O}.

(2) Necht’ S_{0} = S(+, ·, −, 0, 1) je Booleův okruh. Definujeme-li na S binární operaci ∨ předpisem a∨b = a+b+a·b a unární operaci ′ předpisem a′ = 1+a, pak S_{A} = S(∨, ·, 0, 1, ′) je Booleova algebra. Navíc P je podokruh resp. ρ kongruence S_{O}, právě když je P podalgebra resp. ρ kongruence S_{A}.

Důkaz. Nejprve si všimněme, že jakmile oběma směry složíme konstrukci operací Booleova okruhu a Booleovy algebry, dostaneme se k původní struktuře. Označímeli ˜∨ spojení na Booleově algebře definovaný pomocí operací Booleova okruhu a operace na Booleově okruhu jsou naopak definovány pomocí struktury původní Booleovy algebry spočítáme

a˜∨b = a + b + a · b = (a ∧ b′) ∨ (a′ ∧ b) + a ∧ b =
= ([(a ∧ b′) ∨ (a′ ∧ b)] ∧ [a′ ∨ b′]) ∨ ([(a′ ∨ b) ∧ (a ∨ b′)] ∧ [a ∧ b]) =
= (a′ ∧ b) ∨ (a ∧ b′) ∨ (a ∧ b) ∨ (a ∧ b) = a ∨ b.

Výpočet pro komplement je snadný a podobně jako v předchozí úvaze, označíme-li ˜+ sčítání na Booleově okruhu definované pomocí operací Booleovy algebry, dostaneme:

a˜+b = (a ∧ b′) ∨ (a′ ∧ b) = a · (1 + b) + (1 + a) · b + a · (1 + b) · (1 + a) · b

= a + a · b + b + a · b + a · b + a · a · b + a · b · b + a · b · a · b = a + b.

Proto stačí, abychom u obou ekvivalence ztotožňující podalgebry a kongruence dokázali jen přímou implikaci.

(1) Přímo z definice vidíme, že jsou operace + resp. ∧ komutativní s neutrálními prvky 0 resp. 1. Dále ∧ je asociativní,a∧a = a a a+a = (a∧a′)∨(a′∧a) = 0∨0 = 0, tedy každý prvek a ∈ S je sám k sobě opačný. Zbývá ověřit asociativitu operace + a distributivitu ∨ vzhledem k +. Vezměme libovolné a, b, c ∈ S. Potom díky distributivitě Booleovy algebry a 4.17

(a + b) + c = ([(a ∧ b′) ∨ (a′ ∧ b)] ∧ c′) ∨ ((a′ ∨ b) ∧ (a ∨ b′) ∧ c) =

= (a ∧ b′ ∧ c′) ∨ (a′ ∧ b ∧ c′) ∨ (a′ ∧ a ∧ c) ∨ (a′ ∧ b′ ∧ c) ∨ (b ∧ a ∧ c) ∨ (b ∧ b′ ∧ c) =

= (a ∧ b′ ∧ c′) ∨ (a′ ∧ b ∧ c′) ∨ (a′ ∧ b′ ∧ c) ∨ (b ∧ a ∧ c).

Protože a + (b + c) = (c + b) + a, dostáváme z předchozího výpočtu

(b + c) + a = (c ∧ b′ ∧ a′) ∨ (c′ ∧ b ∧ a′) ∨ (c′ ∧ b′ ∧ s) ∨ (b ∧ c ∧ a) = (a + b) + c.

Konečně

a ∧ c + b ∧ c = (a ∧ c ∧ (b′ ∨ c′)) ∨ ((a′ ∨ c′) ∧ b ∧ c) =
= (a ∧ c ∧ b′) ∨ (a′ ∧ b ∧ c) = [(a ∧ b′) ∨ (a′ ∧ b)] ∧ c = (a + b) ∧ c.

Vezměme nyní podalgebru P a kongruenci ρ Booleovy algebry S(∨, ∧, 0, 1, ′). Potom pro každé a, b ∈ P a (c_{i}, d_{i}) ∈ ρ, i = 1, 2 máme a′, b′, a+b = (a∧b′)∨(a′∧b) ∈ P a podobně (c′_{i}, d′_{i}), (c_{1}∧c′_{2}, d_{1}∧d′_{2}), (c′_{1}∧c_{2}, d′_{1}∧d_{2}), (c_{1}+c_{2}, d_{1}+d_{2}) ∈ ρ. Uzavřenost a slučitelnost s dalšími operacemi je zřejmá.

(2) Dokážeme, že je S(·, ∨) distributivní svaz. Zvolme libovolně a, b, c ∈ S. Komutativita · je zaručena předpoklady a komutativita ∨ plyne okamžitě z definice. Dále a · a = a podle předpkladu a a ∨ a = a + a + a · a = 0 + a = a. Asociativita operace · opět plyne z předpokladu, že S(+, ·, −, 0, 1) je (Booleův) okruh a a∨(b∨c) = a+(b+c+b·c)+a·(b+c+b·c) = a+b+c+a·b+a·c+b·c+a·b·c = (a∨b)∨c. Dále ověříme axiom (S4):

a ∨ (b · a) = a + b · a + a · b · a = a + a · b + a · b = a,
a · (b ∨ a) = a · (b + a + b · a) = a · b + a · a + a · b · a = a.

Zbývá ověřit jednu distributivitu:

a · (b ∨ c) = a · (b + c + b · c) = a · b + a · c + a · b · c = (a · b) ∨ (a · c).

Konečně a ∨ 0 = a · 1 = a, a ∨ a′ = a + (1 + a) + a · (1 + a) = 1 + a + a · a = 1 a a · a′ = a · (1 + a) = a + a = 0, tedy S(∨, ·, 0, 1, ′) je Booleova algebra.

Vezmeme-li nyní podalgebru a kongruenci Booleova okruhu S(+, ·, −, 0, 1), potom díky tomu, že jsou nové operace definováni výlučně pomocí operací původních, stejně přímočarou argumentací jako v (1) dokazuje, že se jedná o podalgebru a kongruenci přslušné Booleovy algebry S(∨, ·, 0, 1, ′). □

Důsledek 6.8. Svaz všech kongruencí konečné Booleovy algebry S(∨, ∧, 0, 1, ′) je izomorfní svazu všech podmnožin P(A)(∩, ∪), kde A je množina všech atomů S.

Důkaz. Podle Věty 4.13 je Booleova algebra S(∨, ∧, 0, 1, ′) izomorfní Booleově algebře P(A)(∪, ∩, ∅, A,′) a díky Větám 6.2(2) a 6.7 stačí popsat svaz ideálů příslušného Booleova okruhu P(A)(÷, ∩, Id_{P(A)}, ∅, A). V příkladu 6.6 jsme zjistili, že ideály jsou právě tvaru P(Y) pro Y ∈ P(A). Konečně snadno nahlédneme, že P(Y) ∨ P(Y) = P(Y ∪ Z) a P(Y) ∧ P(Y) = P(Y ∩ Z), tedy svaz ideálů (a tedy i svaz kongruencí původní Booleovy algebry) je izomorfní svazu P(A)(∩, ∪). □

Příklad 6.9. (1) Bud’ S(∨, ∧, 0, 1, ′) konečná Booleova algebra. Víme, že je S izomorfní potenční Boolově algebře nad množinou všech atomů A. To mimo jiné znamená, že |S| = |P(A)| = 2^{|A|}. Podle 6.8 existuje na S(∨, ∧, 0, 1, ′) právě 2^{|A|} = |S| kongruencí.

(2) Bud’ X konečná množina a P(X)(∪, ∩, ∅, X,′) Booleova algebra všech podmnožin množiny X a uvažujme na ní nějakou kongruenci ρ. Tato kongruence je podle 6.7 kongruencí na okruhu P(X)(÷, ∩, Id_{P(X)}, ∅, X). 0značme Y = ⋃[∅]_{ρ}. Využijeme-li popis kongruencí na okruzích pomocí ideálů a připomeneme, že podle 6.6 je ideál [∅]_{ρ} = P(Y), vidíme, že (A, B) ∈ ρ, právě když A ÷ B ⊆ Y.

Cvičení:

(1) Dokažte, že je každý konečný obor nutně tělesem.

(2) Popište všechny podalgebry konečné Booleovy algebry.

(3) Je faktor Boleova okruhu (Booleovy algebry) opět Boleův okruh (Booleova algebra)?

(4) Najděte nekonečnou Booleovu algebru, která nemá žádné atomy.

7. Dělitelnost

Definice. Řekneme, že S(·) je komutativní monoid s krácením, je-li S(·) monoid s komutativní operací · splňující pro každé a, b, c ∈ S podmínku a·c = b·c ⇒ a = b.

Příklad 7.1. (1) N(·) a Z \ {0}(·) jsou zřejmě komutativní monoidy s krácením.

(2) Je-li R(+, ·, −, 0, 1) obor integrity, pak je R \ {0}(·) komutativní monoid s krácením. Vezmeme-li totiž prvky a, b, c ∈ R \ {0}, pro něž a · c = b · c, potom díky distributivitě dostáváme 0 = a · c − b · c = (a − b) · c, a proto a − b = 0.

Poznamenejme, že komutativní monoid s krácením R \ {0}(·) oboru integrity R(+, ·, −, 0, 1) bude v následujícím nejvýznamnějším příkladem tohoto pojmu.

Definice. Bud’ S(·) komutativní monoid s krácením (nebo S(+, ·, −, 0, 1) obor integrity) a necht’ a, b ∈ S. Řekneme, že a dělí b (píšeme a/b), pokud existuje takové c ∈ S, že b = a · c. Řekneme že a je asociován s b (píšeme a∥b), pokud a/b a zároveň b/a.

Všimněme si, že prvek komutativního monoidu s krácením je asociován s 1, právě když je invertibilní.

Poznámka 7.2. Bud’ R(+, ·, −, 0, 1) oboru integrity Pak a/b právě když bR ⊆ aR a a∥b právě když bR = aR.

Důkaz. Jestliže b = a · r pro r ∈ R, pak b ∈ aR a proto bs ∈ aR pro každé s ∈ R. Platí-li bR ⊆ aR, pak i b = b1 ∈ aR, proto a/b. Druhou ekvivalenci dostaneme dvojím použitím první ekvivalence právě dokázaného

kritéria. □

Poznámka 7.3. Necht’ S(·) je komutativní monoid s krácením.

(1) Pro každé a, b ∈ S existuje nejvýše jeden takový prvek c ∈ S, že a = b · c.

(2) Necht’ a, b ∈ S. Pak a∥b právě tehdy, když existuje invertibilní prvek u ∈ S tak, že a = b · u.

(3) ∥ je kongruence na S(·).

(4) S/∥(·) je komutativní monoid s krácením a relace ”dělí”na něm tvoří uspořádání.

Důkaz. (1) Jestliže (a =)b · c_{0} = b · c_{1}, pak stačí vykrátit hodnotou b, abychom dostali c_{0} = c_{1}.

(2) Pro dvojici asociovaných prvků a∥b existuje dvojice prvků u, v ∈ S, pro něž a = b · u a b = a · v. Dosadíme-li do prvního vzahu za b, máme a = a · v · u, a vykrátíme-li prvkem a dostáváme, že 1 = v · u, tj. u a v jsou vzájemně inverzní.

Naopak je-li a = b · u pro invertibilní u ∈ S, je b = a · u^{−1}, tedy a/b i b/a.

(3) Zřejmě je ∥ reflexivní a symetrická relace. Jestliže a/b a b/c, existují x a y, pro něž b = a · x a c = b · y, proto c = a · (x · y), tedy a/c a dtud vidíme, že relace / i ∥ jsou ekvivalence. Mějme a_{0}∥b_{0} a a_{1}∥b_{1}. Pak podle (2) existují invertibilní prvky u_{0}, u_{1} pro které a_{i} = b_{i} · u_{i}, kde i = 1, 2. Nyní a_{0} · a_{1} = (b_{0} · b_{1}) · (u_{0} · u_{1}), kde u_{0} · u_{1} je opět invertibilní prvek. Tedy (a_{0} · a_{1})∥(b_{0} · b_{1}) podle (2).

(4) Je zjevné, že S/∥(·) je komutativní monoid. Mějme [a]_{∥} · [b]_{∥} = [a]_{∥} · [c]_{∥}, potom [a · b]_{∥} = [a · c]_{∥}, tedy podle (2) existuje invertibilní prvek u ∈ S, pro který a · b = a · c · u. Nyní můžeme vykrátit, tudíž b = c · u a opětovným použitím (2) máme [b]_{∥} = [c]_{∥}.

Uvážíme-li, že reflexivita relace ”dělí”na faktorovém monoidu plyne okamžitě z definice faktorové operace, zbývá ověřit tranzitivitu a slabou antisymetrii. Necht’ [a]_{∥} · [x]_{∥} = [b]_{∥} a [b]_{∥} · [y]_{∥} = [c]_{∥}. Potom existují takové invertibilní prvky u a u, pro něž a · x · u = b a b · y · v = c, a proto (a · x · y) · (u · v) = a · x · u · y · v = c. Protože u · v je invertibilní prvek dokázali jsme, že [a]_{∥} · [x · y]_{∥} = [c]_{∥}. Konečně jestliže [a]_{∥} · [x]_{∥} = [b]_{∥} a [b]_{∥} · [y]_{∥} = [a]_{∥}, pak máme invertibilní w, pro které a · x · y · w = a, tedy x · y · w = 1 a x (stejně jako y) je invertibilní prvek. Tím jsme ověřili, že [a]_{∥} = [b]_{∥}.

□

Příklad 7.4. Komutativní monoidy N(·) a Z \ {0}/∥(·) jsou izomorfní.

Definice. Bud’ S(·) komutativní monoid s krácením (nebo S(+, ·, −, 0, 1) obor integrity) a necht’ a, b, c, a_{1}, …, a_{n} ∈ S. Prvek c nazveme největší společný dělitel prvků a_{1}, …, a_{n} (píšeme NSD(a_{1}, …, a_{n})), jestliže c/a_{i} pro všechna i, a každý prvek d ∈ S, který dělí všechna a_{i}, dělí i prvek c. Prvek c nazveme ireducibilním prvkem, jestliže c není invertibilní (ani nulový v oboru integrity) a c = a · b ⇒ c∥a nebo c∥b. Prvek c nazveme prvočinitelem, jestliže c není invertibilní (ani nulový) a c/a · b ⇒ c/a nebo c/b.

Poznamenejme, že každé prvočíslo je určitě ireducibilní prvek v oboru celých čísel.

Poznámka 7.5. Necht’ S(·) je komutativní monoid s krácením a a, b, c, d, e ∈ S. (1) Necht’ d je NSD(a, b) a e je NSD(a · c, b · c). Potom (d · c)∥e

(2) Necht’ 1 je NSD(a, b) a a/b · c. Existuje-li NSD(a · c, b · c), pak a/c.

Důkaz. (1) Protože dc/ac, dc/bc a e je NSD(a · c, b · c), dc/e, tj. existuje u, pro něž e = dcu. To znamená, že dcu/ac a dcu/bc a vykrátíme-li du/a a du/b, a proto du/d, tudíž u∥1 a (d · c)∥e podle 7.3.

(2) Necht’ e je NSD(a·c, b·c), pak je (1·c)∥e podle (1), tedy c je NSD(a·c, b·c). Protože je a společný dělitel b · c, a · c, dostáváme, že a/c. □

Věta 7.6. Mějme S(·) komutativní monoid s krácením. Potom je každý prvočinitel ireducibilní. Pokud navíc pro každé a, b ∈ S existuje NSD(a, b) pak je každý ireducibilní prvek prvočinitelem.

Důkaz. Je-li p prvočinitel a p = a · b, pak p/a · b, a/p, b/p a platí, že p/a (tedy p∥a) nebo p/b (tedy p∥b).

Předpokládejme, že je p ireducibilní, p dělí součin a · b a nedělí prvek a. Protože existuje NSD(p, a), který není asociován s p, plyne z ireducibility p, že 1 je NSD(p, a). Navíc p/a · b a existuje NSD(p · b, a · b), proto podle 7.5(2) p/b. □

Příklad 7.7. Uvažujme podokruh Z[\sqrt{5}] = \{a + \sqrt{5}b| a, b ∈ Z\} okruhu reálných čísel. Zřejmě se jedná o obor integrity, tedy Z[\sqrt{5}]\\{0\}(·) je komutativního monoidu s krácením. Lze ukázat, že prvky 2, \sqrt{5} + 1 a \sqrt{5} − 1 jsou ireducibilní, ale nejde o prvočinitele, protože 2/4 = (\sqrt{5} + 1) · (\sqrt{5} − 1), ale 2 nedělí \sqrt{5} + 1, ani \sqrt{5} − 1 (podobně pro \sqrt{5} + 1 a \sqrt{5} − 1).

Věta 7.8. Necht’ je každý ireducibilní prvek komutativního monoidu s krácením S(·) prvočinitelem a necht’ p_{1}, …, p_{r}, q_{1}, …, q_{s} ∈ S jsou ireducibilní prvky takové, že p_{1} · p_{2} · · · · · p_{r}∥q_{1} · q_{2} · · · · · q_{s}. Potom r = s a existuje taková bijekce σ, že p_{i}∥q_{σ(i)} pro všechna i = 1, …, r.

Důkaz. Tvrzení dokážeme indukcí podle r. Jesliže r = 1 máme p_{1} = u·q_{1} ·q_{2} ·· · ··q_{s} pro nějaký invertibilní prvek u podle 7.3(2) a protože je p_{1} ireducibilní máme podle stejného tvrzení s = 1 (ostatní q_{i} by musely být invertibilní, což je v rozporu s definicí ireducibilního prvku).

Necht’ tvrzení platí pro r − 1. Protože p_{r}/q_{1} · q_{2} · · · · · q_{s}, najdeme indukčním rozšířením definice prvočinitele takové i ≤ s, pro které p_{r}/q_{i}, bez újmy na obecnosti můžeme předpokládat, že i = s. Z ireducibility prvků p_{r} i q_{s} plyne, že jsou nutně asociovány, proto můžeme vykrátit a dostaneme p_{1} · p_{2} · · · · · p_{r−1}∥q_{1} · q_{2} · · · · · q_{s−1}. Nyní podle indukčního předpokladu r − 1 = s − 1 a dostáváme hledanou permutaci σ na množině {1, …, r − 1}, kterou dodefinujeme σ(r) = r. □

Definice. Řekneme, že je R obor integrity hlavních ideálů, jestliže je každý jeho ideál hlavní.

Řekneme, že obor R je UFD (nebo Gaussův), splňuje-li dvě podmínky:

(1) pro každý nenulový neinvertibilní prvek a ∈ R existují ireducibilní prvky p_{1}, …, p_{n} ∈ R \ {0}, pro něž a = p_{1} · · · · · p_{n}

(2) je-li navíc a = q_{1} · · · · · q_{k} pro ireducibilní prvky q_{1}, …, q_{k}, pak n = k a existuje bijekce σ tak, že p_{i}∥q_{σ(i)} pro všechna i = 1, …, n.

Poznámka 7.9. Bud’ R(+, ·, −, 0, 1) obor integrity hlavních ideálů a a_{1}, …, a_{n} ∈ R. Pak existují prvky u_{1}, …, u_{n} tak, že ∑_{i=1}^{n} a_{i} · u_{i} je NSD(a_{1}, …, a_{n}).

Důkaz. Snadno nahlédneme, že množina I = {∑_{i=1}^{n} a_{i}u_{i}| u_{i} ∈ R} je ideál oboru integrity hlavních ideálů R, tedy existuje prvek c ∈ I, pro nějž cR = I. Protože a_{i}R ⊆ cR, je c společný dělitel a_{1}, …, a_{n} a zvolíme-li jiného společného dělitele d těchto prvků, dostáváme, že cR = I ⊆ dR, tedy d/c. □

Věta 7.10. Bud’ R(+, ·, −, 0, 1) obor integrity hlavních ideálů. Pak platí:

(1) Každý ireducibilní prvek R(+, ·, −, 0, 1) je prvočinitelem.

(2) R(+, ·, −, 0, 1) je UFD.

Důkaz. (1) Podle 7.9 jsou splněny předpoklady 7.6, které implikují závěr.

(2) Díky (1) a 7.8 platí jednoznačnost, zbývá tedy dokázat existenci ireducibilního rozkladu.

Předpokládejme ke sporu, že nějaký neinvertibilní prvek a ∈ R nemá ireducibilní rozklad (tj. neexistje posloupnost ireducibilních prvků c_{1}, …, c_{k}, pro které a = c_{1} · · · · · c_{k}), a budeme induktivně vytvářet takovou posloupnost prvků a_{i} a b_{i}, že a_{i} nemá ireducibilní rozklad b_{i} není invertibilní a a_{i} = a_{i+1}b_{i+1}. Nejprve položíme a_{0} = a.

Jestliže a_{i} nemá ireducibilní rozklad a není invertibilní, musí existovat dva neinvertibilní prvky x a y, z nichž aspoň jeden, například x, nemá ireducibilní rozklad a a_{i} = x · y (kdyby ho měly oba, tvořil by jejich součin ireducibilní rozklad a_{i}). Stačí tedy položit a_{i+1} = x a b_{i+1} = y.

Nyní z 7.2 a 7.3 plyne, že a_{i}R ⊂ a_{i+1}R a a_{i}R ≠ a_{i+1}R. Snadno nahlédneme, že je I = ⋃_{i} a_{i}R ideál, který je podle předpokladu hlavní, tj. existuje takové c ∈ I, že cR = I. Protože c ∈ a_{i}R pro dostatečně velké i, dostáváme, že cR ⊆ a_{i}R ⊂ a_{i+1}R ⊆ cR, tedy cR ≠ cR, což je spor. □

Důsledek 7.11 (Základní věta aritmetiky). Protože je okruh Z(+, ·, −, 0, 1) obor integrity hlavních ideálů, existují v monoidech N\{0}(·) a Z\{0}(·) největší společní dělitelé a zřejmě existují rozklady na ireducibilní prvky, tedy jsou v N ireducibilní rozklady určeny až na pořadí jednoznačně, v Z jsou jednoznačné až na pořadí a znaménko.

Cvičení:

(1) Dokažte, že jsou dva největší společní dělitelé týchž prvků asociovány.

(2) Popište prvočinitele okruhu reálných polynomů a okruhu komplexních polynomů.

(3) Dokažte, že v UFD existují největší společní dělitelé každé dvojice prvků.

8. Eukleidovské obory integrity

Definice. Bud’ R(+, ·, −, 0, 1) obor integrity. Řekneme, že R je eukleidovský obor integrity, existuje-li zobrazení ν : R → N_{0}∪{−1} (tzv. eukleidovská funkce) splňující pro každé a, b ∈ R, b ≠ 0 podmínky:

(1) jestliže a/b, pak ν(a) ≤ ν(b),
(2) existuje q, r ∈ R takové, že a = b · q + r a ν(r) < ν(b).

Příklad 8.1. (1) Okruh celých čísel je eukleidovským oborem integrity s eukleidovskou funkcí absolutní hodnotou | − |. První podmínka definice platí zřejmě, druhá plyne z toho, že i v celých čísel umíme dělit se zbytkem.

(2) Snadno si rozmyslíme, že funkce, která každému polynomu s reálnými koeficienty přiřadí jeho stupeň splňuje podmínky eukleidovské funkce, proto je obor reálných polynomů eukleidovským oborem integrity.

(3) Podokruh Z[i] = {a + bi| a, b ∈ Z} (tzv. Gaussova celá čísla) okruhu komplexních čísel je eukleidovským oborem integrity s eukleidovskou funkcí ν(a + bi) = a^{2} + b^{2}. Připomeňme, že |c_{1} · c_{2}| = |c_{1}| · |c_{2}| pro každou dvojici komplexních čísel c_{1} a c_{2}, proto ν(α · β) = |α · β|^{2} = |α|^{2} · |β|^{2} = ν(α) · ν(β) pro všechna α, β ∈ Z[i]. Jetliže α/β a β ≠ 0, existuje γ ∈ Z[i], pro které α · γ = β, proto ν(β) = ν(α · γ) = ν(α) · ν(γ) ≥ ν(α), nebot’ ν(γ) ≥ 0.

Chceme-li vydělit se zbytkem Gaussovo celé číslo α nenulovým číslem β, najdeme nejprve komplexní x + iy = \frac{α}{β} a poté vezmeme taková x_{0}, y_{0} ∈ Z, pro která |x − x_{0}| ≤ \frac{1}{2} a |y − y_{0}| ≤ \frac{1}{2}. Položíme-li γ = x_{0} + iy_{0} a δ = α − β · γ, pak vidíme, že \frac{δ}{β} = \frac{α}{β} − γ = x − x_{0} + i(y − y_{0}), tudíž \frac{|δ|^{2}}{|β|^{2}} = (x − x_{0})^{2} + (y − y_{0})^{2} ≤ \frac{1}{4} + \frac{1}{4} = \frac{1}{2},

proto ν(δ) ≤ \frac{ν(β)}{2} < ν(β).

(4) Podokruh Z[\sqrt{2}] = \{a+\sqrt{2}b| a, b ∈ Z\} okruhu reálných čísel je eukleidovským oborem integrity s eukleidovskou funkcí ν(a + b\sqrt{2}) = |a^{2} − 2b^{2}|. Důkaz toho, že je ν eukleidovská norma plyne podobně jako v (2) z faktu, že ν(α · β) = ν(α) · ν(β).

Následující důkaz je analogický důkazu, že každá podgrupa cyklické grupy je cyklická.

Věta 8.2. Každý eukleidovský obor integrity je oborem integrity hlavních ideálů.

Důkaz. Mějme R(+, ·, −, 0, 1) eukleidovský obor integrity s eukleidovskou funkcí ν : R → N_{0} ∪ {−1} a vezměme libovolný nenulový ideál I. V ideálu I zvolíme nenulový prvek a s minimální hodnotou ν(a). Zřejmě aR ⊆ I. Necht’ i ∈ I. Pak podle definice existuje q, r ∈ R takové, že i = a · q + r a ν(r) < ν(a). Protože r = i − a · q ∈ I a ν(a) bylo minimální, je nutně r = 0 a aR = I. Protože nulový ideál {0} = 0R je vždy hlavním ideálem, ukázali jsme, že všechny ideály eukleidovského oboru integrity jsou hlavní. □

Příklad 8.3. (1) Okruh Z[x] polynomů s celočíselnými koeficienty není oborem integrity hlavních ideálů, protože ideál xZ[x]+2Z[x] = {∑_{i} p_{i}x^{i}| 2/p_{0}} není hlavní. Podle 8.2 tedy nejde o eukleidovský okruh.

(2) Protože v Z[\sqrt{5}] = \{a+\sqrt{5}b| a, b ∈ Z\} nesplývají podle 7.7 ireducibilní prvky prvočinitelé, nejde podle 7.10 obor integrity hlavních ideálů, tedy ani o eukleidovský okruh.

Poznamenejme, že je možné dokázat (i elementárními prostředky), že je okruh Z[\frac{1+\sqrt{19}i}{2}] = \{a + \frac{1+\sqrt{19}i}{2}b| a, b ∈ Z\} obor integrity hlavních ideálů, který není eukleidovský.

Věta 8.4 (Eukleidův algoritmus). Bud’ R(+, ·, −, 0, 1) eukleidovským obor integrity s eukleidovskou funkcí ν a necht’ a_{0}, a_{1} ∈ R \ {0}. Sestrojme pro i ≥ 1 posloupnosti prvků a_{i} a q_{i} následujícím postupem:

(1) jestliže a_{i} nedělí a_{i−1}, vezměme taková a_{i+1}, q_{i} ∈ R, že a_{i−1} = a_{i} · q_{i} + a_{i+1} a ν(a_{i+1}) < ν(a_{i}),

(2) jestliže a_{i} dělí a_{i−1}, položme n = i a konstrukce končí. Posloupnost a_{i} je konečná a a_{n} je NSD(a_{0}, a_{1}). Definujme dále posloupnosti x_{i} a y_{i} tak, že x_{0} = y_{1} = 1, x_{1} = y_{0} = 0, a pro i ≥ 1 položme x_{i+1} = x_{i−1} − x_{i} · q_{i} a y_{i+1} = y_{i−1} − y_{i} · q_{i}. Potom a_{i} = x_{i} · a_{0} + y_{i} · a_{1}, speciálně x_{n} · a_{0} + y_{n} · a_{1} je NSD(a_{0}, a_{1}).

Důkaz. Tvrzení 8.2 a 7.9 říkají, že největší společní dělitelé všech dvoji prvků eukleidovského oboru integrity existují. Protože a_{n} je NSD(a_{n−1}, a_{n}), stačí dokázat, že prvky c a d jsou asociované pro každé 0 < i < n, kde c je NSD(a_{i−1}, a_{i}) a d je NSD(a_{i}, a_{i+1}). Protože c/a_{i} a c/a_{i+1} = a_{i−1} − a_{i} · q_{i} dostáváme z defince NSD, že c/d. Podobně d/a_{i} a d/a_{i−1} = a_{i} · q_{i} + a_{i+1}, tedy d/c.

Platnost formule a_{i} = x_{i} · a_{0} + y_{i} · a_{1} dokážeme indukcí podle i. Triviálně tvrzení platí pro i = 0, 1. Nyní stačí dosadit do výrazu a_{i+1} = a_{i} · q_{i} − a_{i−1} hodnoty a_{i} = x_{i} · a_{0} + y_{i} · a_{1} a a_{i−1} = x_{i−1} · a_{0} + y_{i−1} · a_{1}, abychom dostali

a_{i+1} = (x_{i} · a_{0} + y_{i} · a_{1}) · q_{i} − x_{i−1} · a_{0} + y_{i−1} · a_{1} =
= (x_{i−1} − x_{i} · q_{i}) · a_{0} + (y_{i−1} − y_{i} · q_{i}) · a_{1} = x_{i+1} · a_{0} + y_{i+1} · a_{1}.
□

Příklad 8.5. Najdeme v Z[i](+, ·, −, 0, 1) Eukleidovým algoritmem největší společný dělitel prvků a_{0} = 6 − 7i a a_{1} = 7 + i.

Nejprve spočítáme \frac{6−7i}{7+i} = \frac{(6−7i)(7−i)}{(7+i)(7−i)} = \frac{35}{50} − \frac{55}{50}i, tedy q_{1} = 1 − i a a_{2} = a_{0} − q_{1} ·

a_{1} = 6−7i−(1−i)(7+i) = −2−i. V dalším kroku počítáme \frac{7+i}{−2−i} = \frac{(7+i)(−2+i)}{(−2−i)(−2+i)} = −\frac{15}{5} + \frac{5}{5}i = −3 + i, tedy vidíme, že q_{2} = −3 + i a že a_{2}/a_{1}. Zjistili jsme, že −2 − i je největší společný dělitel prvků 6 − 7i a 7 + i a −2 − i = (6 − 7i) + (−1 + i)(7 + i).

Příklad 8.6 (Polynomy jako formální sumy). Uvědomme si na příkladu polynomů s celočíselnými koeficienty, jakým způsobem zobecnit jejich chápání jako okruhu. Uvažujme polynomy p, q ∈ Z[x], kde polynomem rozumíme sumu p = ∑_{i∈N_{0}} p_{i}x^{i}, resp q = ∑_{i∈N_{0}} q_{i}x^{i}, jejichž skoro všechny (tj. až na konečně mnoho ,,výjimek”) nulové. Takové polynomy umíme sčítat, odčítat a násobit: p+q = ∑_{i∈N_{0}}(p_{i}+q_{i})·x^{i}, −p = ∑_{i∈N_{0}}(−p_{i}) · x^{i} a p · q = ∑_{n∈N_{0}}(∑_{i+j=n} p_{i} · q_{j}) · x^{n}. Všimněme si, že kromě okruhu Z(+, ·, −, 0, 1) v zavedení klasického pojmu polynomu využíváme ještě vlastnosti monoidu nezáporných celých čísel N_{0}(+) (nebo, ekvivalentně řečeno, monoidu {x^{n}| n ∈ N_{0}}(·), který je s N_{0}(+) izomorfní).

Pozorování Příkladu 8.6 tedy chápe polynomy jako posloupnosti koeficientů, jejíž členy jsou označeny pomocí symbolu x^{n}. Tento přístup vvyužijeme v následující obecné konstrukci.

Necht’ R(+, ·, −, 0, 1) je okruh a M(·, e) je monoid. Položme R[M] = {p : M → R| {m|p(m) ≠ 0} je konečné}. Prvek p ∈ R[M] budeme zapisovat také ve tvaru ∑_{m∈M} p(m) · m. Na R[M] definujme binární operace + a ·, unární operaci − a nulární operace 0 a 1:

p + q = ∑_{m∈M}(p(m) + q(m)) · m, p · q = ∑_{m∈M}( ∑_{r·s=m} p(r) · q(s)) · m,

−p = ∑_{m∈M}(−p(m)) · m, 0 = ∑_{m∈M} 0 · m, 1 = 1 · e + ∑_{m∈M\{e}} 0 · m.

Na tomto místě si uvědomme, že pro nás není vhodné chápání polynomů na okruhu s nosnou množinou R jako (vybrané) funkce R → R. Například pro těleso Z_{2} existují pouze 4 funkce Z_{2} → Z_{2}, zatímco polynomů nad Z_{2} je nekonečně mnoho.

Poznámka 8.7. Necht’ R(+, ·, −, 0, 1) je okruh a M(·) je monoid s neutrálním prvkem e.

(1) R[M](+, ·, −, 0, 1) je okruh,

(2) zobrazení i : R → R[M] dané předpisem i(r) = r · e (tj. [i(r)](m) = 0 pro všechna m ≠ e a [i(r)](e) = r) je prostý okruhový homomorfismus.

(3) zobrazení ν : M → R[M] dané předpisem ν(m) = 1 · m je prostý homomorfismus monoidu M(·) do monoidu R[M](·).

Důkaz. (1) Vezměme p, q, r ∈ R, kde p = ∑_{m∈M} p(m)·m, q = ∑_{m∈M} q(m)·m, r = ∑_{m∈M} r(m) · m. Nejprve si uvědomíme, že jsou binární operace dobře definované (pro nulární a unární je korektnost definice zřejmá). K tomu stačí uvážit, že

{m| (p + q)(m) ≠ 0} ⊆ {m| p(m) ≠ 0} ∪ {m| q(m) ≠ 0}

a že

{m| (p · q)(m) ≠ 0} ⊆ {a · b| p(a) ≠ 0, q(b) ≠ 0}.

Dále platí, že

p + q = ∑_{m∈M}(p(m) + q(m)) · m = ∑_{m∈M}(q(m) + p(m)) · m = q + p,

(p+q)+r = ∑_{m∈M}[(p(m)+q(m))+r(m)]·m = ∑_{m∈M}(p(m)+q(m)+r(m))·m = p+(q+r).

Proto 0 je zjevně neutrální prvek operace + a platí, že p+(−p) = 0, je R(+, −, 0) komutativní grupa.

Podobně

(p + q) · r = ∑_{m∈M} ∑_{a·b=m}[p(a) + q(a)) · r(b)] · m =

= ∑_{m∈M} ∑_{a·b=m}(p(a) · r(b) + q(a) · r(b)) · m = p · r + q · r,

důkaz druhé distributivity je symetrický. Konečně zbývá ověřit, že je R(·, 1) monoid:

(p·q)·r = ( ∑_{m∈M} ∑_{a·b=m}(p(a)·q(b))·m)·r = ∑_{m∈M} ∑_{a·b·c=m}(p(a)·q(b)·r(c))·m = p·(q·r).

a

p · 1 = ∑_{m∈M} ∑_{a·b=m}(p(a) · 1(b)) · m = ∑_{m∈M}(p(m) · 1(e)) · m = p = 1 · p.

(2) a (3) dostáváme okamžitě z konstrukce okruhu R[M]. □

Definice. Bud’ R(+, ·, −, 0, 1) okruh a bud’ N_{0}(+, 0) monoid nezáporných celých čísel se sčítáním. Potom okruh R[N_{0}](+, ·, −, 0, 1) nazveme okruhem polynomů jedné neurčité a jeho prvkům budeme říkat polynomy. Místo R[N_{0}] budeme psát R[x] a polynomy budeme místo p = ∑_{n∈N_{0}} p(n).n ∈ R[x] zapisovat ve tvaru p = ∑_{n∈N_{0}} p(n) · x^{n} nebo p = ∑_{n∈N_{0}} p_{n} · x^{n}.

Příklad 8.8. Polynomy více neurčitých můžeme zavést dvěma ekvivalentními způsoby: jednak indukcí R[x_{1}, …, x_{n}] = (R[x_{1}, …, x_{n−1}])[x_{n}] nebo jako monoidový okruh R[N_{0}^{n}] = (R[x_{1}, …, x_{n−1}])[x_{n}] se součinovým monoidem N_{0}^{n}(+, (0, …, 0)).

Definice. Bud’ R(+, ·, −, 0, 1) je okruh a p = ∑_{n∈N_{0}} a_{n} · x^{n} ∈ R[x]. Je-li p ≠ 0, budeme největší takové n ∈ N_{0}, že a_{n} ≠ 0, nazývat stupněm polynomu p. Stupeň polynomu 0 položíme roven −1. Stupeň polynomu p budeme označovat deg p.

Poznámka 8.9. Necht’ R(+, ·, −, 0, 1) je okruh a p, q ∈ R[x]. Pak platí:

(1) deg −p = deg p,

(2) deg p + q ≤ max(deg p, deg q),

(3) je-li p ≠ 0 ≠ q, pak deg p · q ≤ deg p + deg q, je-li navíc R oborem integrity, potom deg p · q = deg p + deg q,

(4) R[x] je obor integrity právě tehdy, když je R obor integrity,

(5) je-li R obor integrity, polynom p je invertibilní prvek okruhu R[x], právě když deg p = 0 a p(0) je invertibilní prvek okruhu R.

Důkaz. Mějme p = ∑_{n} p_{n} · x^{n} a q = ∑_{n} q_{n} · x^{n}, všimněme si, že p_{0} = p(0) = j_{0}(p). (1) Plyne okamžitě z pozorování {n| p_{n} ≠ 0} = {n| − p_{n} ≠ 0}.

(2) Plyne z inkluze {n| p_{n} + q_{n} ≠ 0} ⊆ {n| p_{n} ≠ 0} ∪ {n| q_{n} ≠ 0}.

(3) Označme ν = deg p a μ = deg q q uvědomme si pro každé n > ν + μ, že koeficient u x^{n} v polynomu deg p · q je ∑_{k=0}^{n}(p_{k} · q_{n−k}) = ∑_{k=0}^{n−μ}(p_{k} · 0) + ∑_{k=n−μ+1}^{n}(0 · q_{n−k}) = 0, proto deg p · q ≤ ν + μ.

Je-li R obor integrity, máme koeficient polynomu p · q u x^{ν+μ}:

∑_{k=0}^{ν+μ}(p_{k} · q_{n−k}) = ∑_{k=0}^{n−μ−1}(p_{k} · 0) + p_{ν} · q_{μ} + ∑_{k=n−μ+1}^{n}(0 · q_{n−k}) = p_{ν} · q_{μ} ≠ 0.

(4) Je-li R[x] obor integrity, je každý jeho podokruh oborem integrity, tedy i i(R[x]). Navíc i(R) ≅ R podle 8.7(2) a 1. věty o izomorfismu, proto je R obor integrity.

Je-li R obor integrity a p ≠ 0 ≠ q, máme podle (3) deg p · q = deg p + deg q ≥ 0, proto p · q ≠ 0.

(5) Jestliže p · q = 1, pak podle (3) je 0 = deg 1 = deg p + deg q, proto deg p = deg q = 0, p = p_{0}x^{0} a p_{0}q_{0} = 1, tedy p_{0} je invertibilní.

Naopak, jestliže deg p = 0 a p_{0} je invertibilní, pak p · p_{0}^{−1}x^{0} = 1x^{0}. □

Věta 8.10 (Dělení se zbytkem). Necht’ R(+, ·, −, 0, 1) je obor integrity, a, b ∈ R[x], a b = ∑ b_{n}x^{n}. Předpokládejme, že m = deg b ≥ 0 a b_{m} je invertibilní v R. Potom existují jednoznačně určené polynomy q, r ∈ R[x] tak, že a = b·q+r a deg r < deg b.

Důkaz. Dokážeme nejprve existenční část tvrzení a to indukcí podle n = deg a − deg b. Jestliže deg a < deg b, a tedy n < 0, stačí položit q = 0 a r = a. Platí-li existenční tvrzení pro všechna i < n, dokážeme ho pro n. Bud’ a = ∑ a_{n}x^{n} a položme u = a_{n+m}b_{m}^{−1}x^{n} a t = a − u · b. Podle 8.9(2) a (3) je deg t ≤ max(deg a, deg u + deg b) = n+m a koeficient polynomu t u mocniny x^{n+m} je a_{n+m} −a_{n+m}b_{m}^{−1}b_{m} = 0, tedy deg t−deg b < n. Proto pro polynom t můžeme užít indukční předpoklad, podle nějž existují takové polynomy v a r, že t = b · v + r a deg r < deg b. Položíme-li nyní q = u + v, dostáváme

b · q + r = b · u + b · v + r = b · u + t = a.

Konečně předpokládejme, že a = b·q′+r′ a deg r′ < deg b. Potom b·(q−q′) = r′−r a podle 8.9(3) a protože deg(r′−r) < deg b, dostáváme r′−r = 0, a proto q−q′ = 0 □ Důsledek 8.11. Je-li T (+, ·, −, 0, 1) komutativní těleso, pak je T [x] díky 8.9 a 8.10 eukleidovský obor integrity s eukleidovskou funkcí danou stupněm polynomů, tedy jde podle 8.2 o obor integrity hlavních ideálů.

Poznámka 8.12. Je-li S(+, ·, −, 0, 1) komutativni okruh, R jeho podokruh a α ∈ S, pak zobrazení j_{α} : R[x] → S dané předpisem j_{α}(∑_{n∈N_{0}} a_{n}x^{n}) = ∑_{n∈N_{0}} a_{n} · α^{n} je okruhový homomorfismus.

Důkaz. Nejprve snadno spočítáme, že j_{α}(0) = 0x^{0}, j_{α}(1x^{0}) = 1 a pro klibovolné a, b ∈ R[x], kde a = ∑_{n} a_{n} · x^{n} a b = ∑_{n} b_{n} · x^{n}

j_{α}(a + b) = j_{α}(∑_{n}(a_{n} + b_{n}) · x^{n}) = ∑_{n}(a_{n} + b_{n}) · α^{n} = j_{α}(a) + j_{α}(b),

proto je j_{α} homomorfismus grup R(+, −, 0) a S(+, −, 0). Zbývá nahlédnout, že

j_{α}(a · b) = j_{α}(∑_{n} ∑_{k=0}^{n}(a_{k} · b_{n−k}) · x^{n}) = ∑_{n} ∑_{k=0}^{n}(a_{k} · b_{n−k}) · α^{n} = j_{α}(a) · j_{α}(b).

□

Definice. Necht’ S(+, ·, −, 0, 1) je komutativni okruh, R jeho podokruh, α ∈ S a p ∈ R[x]. Homomorfismu j_{α} z 8.12 říkáme dosazovací homomorfismus, α nazveme kořenem polynomu p, jestliže j_{α}(p) = 0, a α je vícenásobný kořen polynomu p, pokud (x−α)^{2}/p. Kořenovým činitelem (kořenu α) rozumíme polynom tvaru x−α. Řekneme, že se polynom p rozkládá na kořenové činitele v S[x], existují-li takové prvky a ∈ R a α_{1}, …, α_{n} ∈ S, že p = a · (x − α_{1}) · · · · · (x − α_{n}).

V následujícím budeme často používat pro dosazení obvyklý zápis p(α) místo právě zavedeného zápisu j_{α}(p).

Poznámka 8.13. Necht’ je R(+, ·, −, 0, 1) obor integrity, α ∈ R a p ∈ R[x] \ {0}. (1) α je kořenem p právě tehdy, když (x − α)/p v R[x],

(2) x − α je prvočinitel oboru R[x],

(3) je-li p ≠ 0, pak p má nejvýše deg p kořenů.

Důkaz. (1) Předpokládejme, že je α kořenem p. Protože je 1 invertibilní prvek oboru R můžeme podle 8.10 vydělit polynom p polynomem x − α se zbytkem, tedy existují q, r ∈ R[x], pro něž p = (x − α)q + r a deg r < deg(x − α) = 1. Dosadíme-li nyní α do polynomu r = p − (x − α)q a využijeme-li 8.12, dostaneme r(α) = j_{α}(r) = j_{α}(p)−j_{α}((x−α))j_{α}(q) = 0−0q(α) = 0. Protože deg r < 1, vidíme, že r = 0, a proto (x − α)/p.

Jestliže (x − α)/p, máme p = (x − α)q pro vhodné q ∈ R[x] a tedy p(α) = (α − α)q(α) = 0 díky 8.12.

(2) Jestliže (x − α)/a · b pro a, b ∈ R[x], plyne z (1), že je α kořenem a · b. Nyní a(α) · b(α) = 0 podle 8.12, proto a(α) = 0 nebo b(α) = 0, nebot’ je R obor integrity. Tedy x − α/a nebo x − α/b podle (1).

(3) Necht’ α_{1}, …, α_{k} ∈ R jsou různé kořeny p. Indukcí podle počtu r různých kořenů nahlédneme, že p = (x−α_{1})·· · ··(x−α_{k})·q pro vhodný nenulový polynom q. Krok r = 1 nám dává (1). Jestliže p = (x−α_{1})·· · ··(x−α_{r})·q a (x−α_{r+1})/p podle (1), pak x−α_{r+1} je prvočinitel podle (2) nedělí žádný z polynomů x−α_{i}, kde i ≤ r, proto (x−α_{r+1})/q. Konečně z 8.9(3) plyne, že deg p = deg((x−α_{1})·· · ··(x−α_{k})·q) = k + deg q ≥ k. □

Všimněme si, že 8.13(1) říká, že vícenásobný kořen je kořenem, a 8.13(2) nám poskytne příklady prvočinitelů (a tedy ireducibilních prvků) v okruhu polynomů nad obecným oborem integrity.

Definice. Bud’ R(+, ·, −, 0, 1) komutativní okruh a p = ∑_{i≥0} a_{i}x^{i} ∈ R[x]. Derivací polynomu p budeme rozumět polynom (∑_{i≥0} a_{i}x^{i})′ = ∑_{i≥0}(i + 1)a_{i+1}x^{i}.

Poznámka 8.14. Necht’ R(+, ·, −, 0, 1) je komutativní okruh, α ∈ R, p, q ∈ R[x] a n ∈ N. Pak platí:

(1) (p + q)′ = p′ + q′,

(2) (αx^{0} · p)′ = αx^{0} · p′,
(3) (p · q)′ = p′ · q + p · q′.
(4) (p^{n})′ = np^{n−1} · p′, kde n = 1 + ⋯ + 1 ∈ R.

Důkaz. (1)–(3) Vlastnosti dostáváme přimočarým použitím definice.

(4) Dokážeme indukcí indukcí podle n. Pro n = 1 je (p^{1})′ = p′ = 1p^{0} · p′. Platí-li tvrzení pro n − 1 a použijeme-li (3) dostáváme

(p^{n})′ = (p·p^{n−1})′ = p′ ·p^{n−1} +p·(p^{n−1})′ = p′ ·p^{n−1} +p·(n−1)p^{n−2} ·p′ = np^{n−1} ·p′.

□

Poznámka 8.15. Necht’ S(+, ·, −, 0, 1) je obor integrity, R jeho podokruh, α ∈ S a p ∈ R[x].

(1) α je vícenásobný kořen p, právě když je α kořenem p i p′,

(2) jestliže deg p ≥ 1 a 1 je NSD(p, p′), pak p nemá žádný vícenásobný kořen,

(3) nedělí-li charakteristika R přirozené číslo n, pak x^{n} −1 ani x^{n+1} −x nemají v S žádný vícenásobný kořen.

Důkaz. Poznamenejme, že polynom s koeficienty v R můžeme přirozeným způsobem chápat jako polynom okruhu S[x].

(1) Předpokládáme, že α je kořen p, tedy p = (x − α) · q pro vhodný polynom q ∈ S[x] podle 8.13(1). Pomocí 8.14(3) spočítáme p′ = q + (x − α) · q′. Díky 8.12 vidíme, že je α kořenem p′ právě tehdy, když je kořenem q a to je podle 8.13(1) ekvivalentní tomu, že (x − α)/q tj. (x − α)^{2}/p.

(2) Tvrzení dokážeme nepřímo. Je-li α vícenásobný kořen p, potom podle (1) a 8.13(1) (x − α)/p′. Protože (x − α)/p, polynomy p a p′ nemohou být nesoudělné.

(3) Označme n ∈ R je součet n kopií 1 tělesa, a poznamenejme, že podle předpokladu n ≠ 0. Protože polynom (x^{n}−1)′ = n·x^{n−1} je nenulový, j_{α}(n·x^{n−1}) = (n × 1) · α^{n−1} ≠ 0 pro všechna α ≠ 0, a naopak 0 není kořenem polynomu x^{n} − 1, x^{n} − 1 nemá žádný vícenásobný kořen díky (1).

Předpokládejme, že (x−α)^{2}/x^{n+1} −x, tedy existuje p ∈ S[x], pro který (x−α)^{2} · p = x^{n+1} − x = x · (x^{n} − 1). Jestliže α = 0, pak výraz vykrátíme na x · p = x^{n} − 1, což není možné, protože x^{n} − 1 nemá kořen 0. Kdyby α ≠ 0, pak (−α)^{2} · p(0) = 0, a proto p(0) = 0. Tedy podle 8.13(1) existuje takové q ∈ S[x], že p = x·q. Dosadíme-li za p do původní rovnosti a opět vykrátíme x, dostáváme, že (x − α)^{2} · q = x^{n} − 1, což jsme vyloučili v první části důkazu (3). □

Příklad 8.16. V tělese charakteristiky 3 (např Z_{3}) platí, že (x − 1)^{3} = x^{3} − 3x^{2} + 3x − 1 = x^{3} − 1, tedy polynom x^{3} − 1 má nad takovým tělesem vícenásobný kořen 1. Vidíme, že předpoklad o charakteristice z 8.15(3) nemůžeme odstranit. Navíc si všimněme derivace (x^{3} − 1)′ = 0.

Nyní už jsme s to dokázat nedokázané tvrzení 2.14 z 2. kapitoly:

Věta 8.17. Necht’ T (+, ·, −, 0, 1) je komutativní těleso a necht’ G je konečná podgrupa multiplikativní grupy T \ {0}(·). Potom je G cyklická grupa.

Důkaz. Uvažujme nejprve libovolnou konečnou grupu G(·) a položme n = |G|. Poznamenejme, že řádem prvku grupy budeme rozumět řád cyklické podgrupy tímto prvkem generované. Podle Lagrangeovy věty dělí řád každého prvku konečné grupy její řád. Označíme-li t_{k} počet všech prvků G, které jsou právě řádu k, vidíme, že |G| = ∑_{k/|G|} t_{k}. Připomeňme, že v cyklické grupě řádu n máme pro každé k/n právě jednu (cyklickou) podgrupu řádu k (viz 2.7) a počet generátorů této podgrupy, tedy právě všechny prvky řádu k, udává hodnota Eulerovy funkce φ(k) (viz 2.9), dává nám předchozí rovnost vztah n = ∑_{k/n} φ(k).

Nyní předpokládejme, že G je (konečná) podgrupa multiplikativní grupy T \ {0}(·), která není cyklická, tedy t_{n} = 0 (< φ(n)). Z úvodních úvah víme, že n = |G| = ∑_{k/n} t_{k} = ∑_{k/n} φ(k), proto musí existovat k/n, pro nějž t_{k} > φ(k), zvolme nějaké takové k a vezměme u ∈ G řádu k. Potom pro všechny prvky a cyklické grupy ⟨u⟩ platí a^{k} = 1, tedy a je kořenem polynomu x^{k} − 1. Ovšem ⟨u⟩ obshuje právě φ(k) generátorů, tj. prvků řádu k, tedy musí existovat nějaký další prvek v ∈ G \ ⟨u⟩ řádu k. I on je kořenem polynomu x^{k} − 1, tedy jsme našli k + 1 kořenů polynomu stupně k, což je ve sporu s 8.13(3). □

Příklad 8.18. Z_{53} \ {0}(·) je podle 8.17 cyklická grupa řádu 52. To znamená, že obsahuje φ(52) = 3 · 12 = 36 generátorů.

Cvičení:

(1) Dokažte, že okruh Z[\sqrt{3}] = \{a + \sqrt{3}b| a, b ∈ Z\} je eukleiovským oborem integrity.

(2) Popište prvočinitele oboru Gaussových celých čísel.

9. Kořenová a rozkladová nadtělesa

Nejprve si uvědomíme, že homomorfismus okruhů lze přirozeným způsobem rozšířit na homomorfismus příslušných polynomiálních okruhů.

Definice. Jsou-li R(+, ·, −, 0, 1) a S(+, ·, −, 0, 1) okruhy a f : R → S jejich homomorfismus, pak definujme zobrazení f_{x} : R[x] → S[x] předpisem f_{x}(∑_{i≥0} a_{i}x^{i}) = ∑_{i≥0} f(a_{i})x^{i}.

Poznámka 9.1. Bud’ R(+, ·, −, 0, 1), S(+, ·, −, 0, 1) a T (+, ·, −, 0, 1) komutativní okruhy a f : R → S a g : S → T homomorfismy. Potom platí:

(1) f_{x} je okruhový homomorfismus,

(2) (gf)_{x} = g_{x}f_{x},

(3) f_{x} je izomorfismus, právě když f je izomorfismus,

(4) fj_{α} = j_{f(α)}f_{x} pro každé α ∈ R.

Důkaz. (1) Zřejmě f_{x}(1x^{0}) = 1x^{0}, proto stačí dokázat slučitelnost f_{x} s operacemi + a ·. Bud’ a, b ∈ R[x], a = ∑_{n} a_{n}x^{n}, b = ∑_{n} b_{n}x^{n}:

f_{x}(a + b) = f_{x}(∑_{n}(a_{n} + b_{n})x^{n}) = ∑_{n} f(a_{n} + b_{n})x^{n} = ∑_{n}(f(a_{n}) + f(b_{n}))x^{n} =

= ∑_{n} f(a_{n})x^{n} + ∑_{n} f(b_{n})x^{n} = f_{x}(a) + f_{x}(b),

f_{x}(a · b) = f_{x}(∑_{n} ∑_{k=0}^{n}(a_{k} · b_{n−k})x^{n}) = ∑_{n} f(∑_{k=0}^{n}(a_{k} · b_{n−k}))x^{n} =

= ∑_{n}(∑_{k=0}^{n} f(a_{k}) · f(b_{n−k}))x^{n} = ∑_{n} f(a_{n})x^{n} · ∑_{n} f(b_{n})x^{n} = f_{x}(a) · f_{x}(b).

(2) g_{x}f_{x}(∑_{n} a_{n}x^{n}) = ∑_{n} gf(a_{n})x^{n} = (gf)_{x}(∑_{n} a_{n}x^{n}).

(3) Necht’ je f_{x} izomorfismus. Jestliže f(u) = f(v), pak f_{x}(ux^{0}) = f_{x}(vx^{0}), a proto u = v, pro každé u, v ∈ R. Tedy f je prostý. Vezmeme-li b ∈ S pak existuje ax^{0}, pro který f_{x}(ax^{0}) = bx^{0}, tedy f(a) = b a f je na celé S.

Je-li f izomorfismus, pak f_{x}(f^{−1})_{x} = Id_{S[x]} a (f^{−1})_{x}f_{x} = Id_{R[x]} podle (2), tedy (f_{x})^{−1} = (f^{−1})_{x} a f_{x} je izomorfismus.

(4) fj_{α}(∑ a_{n}x^{n}) = ∑ f(a_{n})f(α)^{n} = j_{f(α)}f_{x}(∑ a_{n}x^{n}). □

Poznámka 9.2. Necht’ R(+, ·, −, 0, 1) je komutativní okruh a I jeho ideál. Potom faktorový okruh R/I je těleso právě tehdy, když I je maximální ideál.

Důkaz. Připomeňme, že je svaz ideálů izomorfní svazu kongruencí okruhu, označme ρ_{I} kongruenci, která v tomto izomorfismu odpovídá ideálu I. Dále si uvědomme, že díky tomuto izomorfismu je I maximální ideál, právě když je ρ_{I} koatom svazu kongruencí a to je podle Poznámky 3.11 ekvivalentní tomu, že faktorokruh R/ρ_{I} = R/I obsahuje pouze triviální kongruence. Tato podmínka ovšem díky Větě 6.2 tentokrát na okruh R/I nastává právě tehdy, když je R/I těleso. □

Věta 9.3. Necht’ T (+, ·, −, 0, 1) je komutativní těleso a u = ∑_{i≥0} a_{i}x^{i} ∈ T [x].

(1) Faktorový okruh T [x]/uT [x] je komutativní těleso, právě když je u ireducibilní.

(2) Jestliže u není invertibilní, zobrazení μ(t) = tx^{0} + uT [x] je prostý homomorfismus tělesa T do okruhu T [x]/uT [x], .

(3) Je-li u ireducibilní, pak polynom μ_{y}(∑_{i≥0} a_{i}y^{i}) má kořen v tělese T [x]/uT [x].

Důkaz. (1) Podle Poznámky 9.2 stačí ověřit, že u je ireducibilní, právě když je uT [x] maximální ideál. Necht’ je u je ireducibilní a J ideál obsahující uT [x]. Podle 8.11 existuje j ∈ T [x] J = jT [x], tedy díky 7.2 j/u. Protože je u ireducibilní, máme bud’ j∥u a tudíž uT [x] = J nebo 1∥j a tudíž jT [x] = T [x]. Je-li uT [x] maximální ideál, dostáváme závěr přímým použitím 7.2 a definice ireducibility.

(2) Uvědomme si, že zobrazení μ dostaneme jako složení homomorfismus i z 8.7(2) a přirozené projekce π : T [x] → T [x]/uT [x], proto μ = πi je opět homomorfismus. Jestliže konečně μ(a) = μ(b), pak u/ax^{0} −bx^{0}, tedy podle 8.9(3) je ax^{0} −bx^{0} musí být nulový polynom (v opačném případě by deg u ≤ deg(ax^{0} − bx^{0})), a tedy μ je prosté.

(3) Stačí ověřit, že je X = x+uT [x] kořenem ∑_{i≥0} a_{i}y^{i} nad okruhem T [x]/uT [x]. Dosadíme-li, dostáváme j_{X}(∑_{i≥0} a_{i}y^{i}) = ∑_{i≥0}(a_{i}x^{i} + uT [x]) = (∑_{i≥0} a_{i}x^{i}) + uT [x] = u + uT [x] = 0 + uT [x]. □

Pro každý ireducibilní polynom u označme symbolem (T [x])_{u} těleso T [x]/uT [x]. Podle předchozí poznámky a 1. věty o izomorfismu můžeme ztotožnit těleso T a jeho homomorfní obraz μ(T), tedy těleso T budeme chápat jako podokruh tělesa (T [x])_{u}.

Definice. Necht’ U(+, ·, −, 0, 1) je komutativní těleso a T ⊆ U. Řekneme, že T je podtěleso U (resp. U je nadtěleso T), je-li T podokruh okruhu U(+, ·, −, 0, 1) a T je těleso (tj. navíc T \ {0} je podgrupou multiplikativní grupy U \ {0}(·) tělesa U).

Všimněmem si, že množina všech podtěles komutativního tělesa tvoří uzávěrový systém, tj. průnik libovolného systému podtěles nějakého tělese je opět podtěleso. To nám umožňuje zavést pro libovolné komutativní těleso U, jeho podtěleso T a prvek α ∈ U a podmnožinu S ⊆ U následující značení:

• T [S] je nejmenší podokruh U obsahující množinu T ∪ S a T [α] = T [{α}]

• T (S) je nejmenší podtěleso U obsahující množinu T ∪ S a T (α) = T ({α}). V následujícím budeme uvažovat vždy komutativní těleso U a jeho podtěleso T.

Poznámka 9.4. Jsou-li T ⊆ U komutativní tělesa, α ∈ U a S ⊂ U, pak T [α] = {∑_{i=0}^{n} a_{i} · α^{i}| a_{i} ∈ T } = j_{α}(T [x]), T [α] ⊆ T (α) a T [S] ⊆ T (S).

Důkaz. Zřejmě {p(α)| p ∈ T [x]} ⊆ T [α], nebot’ α ∈ T [α] a T ⊆ T [α]. Naopak {p(α)| p ∈ T [x]} = j_{α}(T [x]) je podokruh U obsahující α = j_{α}(x) a t = j_{α}(tx^{0}) pro všechna t ∈ T, proto T [α] ⊆ {p(α)| p ∈ T [x]}. Zbytek plyne okamžitě z definice. □

Definice. Necht’ T ⊆ U jsou komutativní tělesa a p ∈ T [x]. Řekneme, že U je kořenové nadtěleso polynomu p, jestliže U = T (α) pro nějaký kořen α ∈ U polynomu p a U nazveme rozkladovým nadtělesem polynomu p, je-li p = a(x−α_{1}) … (x− α_{n}) pro a ∈ T a α_{1}, …, α_{n} ∈ U a U = T ({α_{1}, …, α_{n}}).

Věta 9.5. Necht’ T (+, ·, −, 0, 1) je komutativní těleso a p ∈ T [x], deg p ≥ 1. (1) existuje kořenové nadtěleso polynomu p,

(2) existuje rozkladové nadtěleso polynomu p.

Důkaz. (1) Podle 7.10 a 8.11 existuje (jednoznačný) ireducibilní rozklad polynomu p, zvolíme-li nějaký ireducibilní polynom p_{1}, který dělí p, dostaneme podle 9.3 nadtěleso U = (T [x])_{p_{1}}, v němž má polynom p kořen α. Hledaným kořenovým nadtělesem je potom těleso T (α).

(2) Indukcí podle n = deg p dokážeme, že existuje komutativní nadtěleso V tělesa T, nad nímž se p rozkládá na kořenové činitele. Podle (1) existuje nadtěleso U, v němž má p kořen α ∈ U. Označíme-li μ inkluzi T do U, pak p = μ_{x}(p) ∈ U[x] je polynom stupně n a podle 8.13(1) existuje polynom v ∈ U[x] stupně n − 1, pro který u = (x − α) · v. Podle indukčního předpokladu existuje nadtěleso V tělesa U, nad nímž se v a tedy i p rozkládá na kořenové činitele.

Dokázali jsme, že existují prvky a ∈ U a α_{1}, …, α_{n} ∈ V, pro něž p = a(x − α_{1}) … (x − α_{n}). Protože je p ∈ T [x], máme a ∈ T, tedy rozkladovým nadtělesem polynomu p je právě těleso T ({α_{1}, …, α_{n}}). □

Definice. Necht’ T ⊆ U jsou komutativní tělesa a α ∈ U. Řekneme, že α je algebraický prvek nad T, existuje-li nenulový polynom p ∈ T [x], jehož je α kořenem, tj. j_{α}(p) = 0. V opačném případě mluvíme o transcendentním prvku. Těleso U nazveme algebraickým rozšířením tělesa T, jsou-li všechny prvky α ∈ U algebraické nad T. Polynom p = ∑ a_{i}x^{i} je monický, je-li a_{deg p} = 1.

Věta 9.6. Bud’ T ⊆ U komutativní tělesa a α ∈ U je algebraický prvek nad T. Pak existuje právě jeden takový monický polynom m ∈ T [x] \ {0}, že pro každé p ∈ T [x]\{0} platí, že j_{α}(p) = 0, právě když m/p. Navíc m je ireducibilní, (T [x])_{m} ≅ T (α) a T [α] = T (α).

Důkaz. Vezměme množinu I = {p ∈ T [x]| j_{α}(p) = 0} = j_{α}^{−1}(0) všech polynomů, které mají kořen α. Protože je j_{α} homomorfimus podle 8.12, vidíme, že je I jako úplný vzor nulové podgrupy podgrupou grupy T [x](+, −, 0). Jestliže p ∈ I a q ∈ T [x], máme j_{α}(pq) = 0 · j_{α}(q) = 0, tedy p · q ∈ I. Nahlédli jsme, že je I ideál, tedy podle 8.11 existuje jeho generátor a = ∑ a_{n}x^{n} ∈ I. Protože je prvek α algebraický nad T, obsahuje I = aT [x] nenulový polynom a proto je nenulový i polynom a ∈ I. Je-li n = deg a, položme m = a_{n}^{−1}a. Nyní je m monický, platí I = mT [x], tedy p(α) = 0 ⇔ p ∈ I ⇔ m/p, a zřejmě je takový monický polynom určen jednoznačně.

Nyní předpokládejme, že m = a · b, kde a, b ∈ T [x]. Potom podle 8.12 a(α) = 0 a pak m∥a nebo b(α) = 0 a pak m∥b, tedy m je ireducibilní. Konečně si všimněme, že díky 1. větě o izomorfismu a 9.4(1) je

(T [x])_{m} = T [x]/mT [x] = T [x]/ker j_{α} ≅ j_{α}(T [x]) = T [α].

Protože je T [x]/mT [x] podle 9.3 těleso, je i T [α] těleso, proto T [α] = T (α). □

Definice. Bud’ T ⊆ U komutativní tělesa. Polynom z předchozí věty nazveme minimálním polynomem algebraického prvku α ∈ U, budeme ho značit m_{α}. Stupeň rozšíření U nad T definujeme jako [U : T] = dim_{T} U, kde U chápeme jako vektorový prostor nad tělesem T.

Příklad 9.7. Těleso komplexních čísel je kořenovým i rozkladovým nadtělesem polynomu x^{2} + 1 nad R, [C : R] = 2.

Věta 9.8. Necht’ T ⊆ U jsou komutativní tělesa a α, α_{1}, …, α_{n} ∈ U.

(1) Je-li α algebraický, pak [T (α) : T] = deg m_{α},

(2) je-li [T (α) : T] konečné, pak je α algebraický,

(3) je-li [U : T] konečné, pak je U algebraické rozšíření tělesa T,

(4) T (α_{1}, …, α_{n}) = T [α_{1}, …, α_{n}] je rozšířením konečného stupně tedy algebraickým rozšířením tělesa T, jsou-li α_{1}, …, α_{n} algebraické nad T.

Důkaz. (1) Položme n = deg m_{α} a připomeňme, že T [α] = T (α) podle 9.6. Dokážeme, že množina {α^{i}| i = 0, 1, …, n − 1} je bází T [α] nad tělesem T. Vezměme prvek t ∈ T [α], o němž z 9.4 víme, že je tvaru t = p(α) pro vhodný polynom p ∈ T [x]. Vydělíme-li nyní se zbytkem polynom p poynomem m_{α}, dostaneme (8.10) p = qm_{α} + r pro q, r ∈ T [x] a deg r < n. Nyní vidíme, že t = p(α) = q(α)m_{α}(α) + r(α) = r(α), protože je α kořenem m_{α}, tedy t = r(α) = ∑_{i<n} r_{i}α^{i} je T -lineární kombinací prvků {α^{i}| i = 0, 1, …, n − 1}. Je-li nyní ∑_{i<n} c_{i}α^{i} = 0, kde c_{i} ∈ T, je α kořenem polynomu c = ∑_{i<n} c_{i}x^{i} = 0 stupně menšího než n. Protože podle 9.6 m_{α}/c, dostáváme, že c = 0, tudíž {α^{i}| i = 0, 1, …, n − 1} je lineárně nezávislá množina.

(2) Je-li [T (α) : T] konečné, je množina {α^{i}| i ≥ 0} lineárně závislá, tudíž existuje netriviální lineární kombinace ∑_{i≤n} d_{i}α^{i} = 0, tedy α kořenem nenulového polynomu ∑_{i≤n} d_{i}x^{i}.

(3) Vezměme libovolné α ∈ U. Potom je T (α) podprostor konečně generovaného vektorového prostoru U nad tělesem T, tedy [T (α) : T] je konečné a proto je α algebraický prvek podle (2).

(4) Nejprve ukážeme, že [V : T] = [V : U][U : T] pro T ⊆ U ⊆ V jsou do sebe zařazená komutativní tělesa. Je-li (u_{i}) báze prostoru U nad tělesem T a (v_{j}) báze prostoru V nad tělesem U, ukážeme, že (u_{i}v_{j}) je báze prostoru V nad tělesem T. Vezmeme-li libovolné a ∈ V, pak existuje lineární kombinace a = ∑_{j} d_{j}v_{j}, kde d_{j} ∈ U. Proto pro každé j existují lineární kombinace d_{j} = ∑_{i} c_{ij}u_{i}, kde c_{ij} ∈ T. Vidíme, že a = ∑_{i,j} c_{ij}u_{i}v_{j}, tedy (u_{i}v_{j}) generuje V nad T. Podobně jestliže 0 = ∑_{i,j} c_{ij}u_{i}v_{j} = ∑_{j}(∑_{i} c_{ij}u_{i})v_{j} pro nějaká c_{ij} ∈ T, dostáváme z lineární nezávislosti (v_{j}) nad U, že ∑_{i} c_{ij}u_{i} = 0 a z lineární nezávislosti (u_{i}) nad T plyne, že jsou všechna c_{ij} nulová. Tím jsme ověřili, že (u_{i}v_{j}) je lineárně nezávislá generující množina, tedy báze. Proto [V : T] = |(u_{i}v_{j})| = |(u_{i})||(v_{j})| = [V : U][U : T].

Nyní dokážeme indukcí podle n, přičemž jsme tvrzení pro n = 1 dokázali v 9.6, navíc [T (α) : T] je konečné podle (1). Předpokládejme, že tvrzení platí pro n − 1. Nyní T [α_{1}, …, α_{n}] = T [α_{1}, …, α_{n−1}][α_{n}] = T (α_{1}, …, α_{n−1})[α_{n}] a T (α_{1}, …, α_{n−1}) je konečného stupně nad T podle indukčního předpokladu. Protože je prvek α_{n} algebraický nad tělesem T (α_{1}, …, α_{n−1}), vidíme díky 9.6, že T (α_{1}, …, α_{n−1})[α_{n}] = T (α_{1}, …, α_{n−1})(α_{n}) = T (α_{1}, …, α_{n}). Konečně díky (1), indukčnímu předpokladu a dokázanému pozorování o stupni rozšíření dostáváme

[T (α_{1}, …, α_{n−1})(α_{n}) : T] =
= [T (α_{1}, …, α_{n−1})(α_{n}) : T (α_{1}, …, α_{n−1})][T (α_{1}, …, α_{n−1}) : T].

Protože jsou oba součinitele vpravo konečné, je i [T (α_{1}, …, α_{n−1}, α_{n}) : T] konečný. □

Důsledek 9.9. Necht’ T je komutativní těleso, p ∈ T [x] a necht’ je U rozkladové nadtěleso polynomu p. Jsou-li α_{1}, …, α_{n} ∈ U všechny kořeny polynomu p v tělese U, pak U = T [α_{1}, …, α_{n}].

Příklad 9.10. (1) Q(\sqrt[3]{2}) = Q[\sqrt[3]{2}] = \{x + y\sqrt[3]{2} + z\sqrt[3]{4}| x, y, z ∈ Q\} je kořenové nadtěleso polynomu x^{3}−2 nad Q a [Q(\sqrt[3]{2}) : Q] = 3, tedy x^{3}−2 je monický polynom stupně 3, a proto jde podle 9.8(1) a 9.6 právě o minimální polynom algebraického prvku \sqrt[3]{2} nad Q. Všimněme si, že zatímco nad Q je polynom x^{3} − 2 ireducibilní, nad R máme ireducibilní rozklad x^{3} − 2 = (x − \sqrt[3]{2})(x^{2} + \sqrt[3]{2}x + \sqrt[3]{4}) a nad C se polynom rozkládá na kořenové činitele.

(2) Necht’ k ∈ Z a \sqrt{k} ∈ C \ Q. Pak Q(\sqrt{k}) ≠ Q a \sqrt{k} je kořenem polynomu x^{2} − k, proto je m\sqrt{k} = x^{2} − k díky 9.4 nutně minimální polynom a [Q(\sqrt{k}) : Q] = deg m\sqrt{k} = 2 podle 9.8(1). Q(\sqrt{k}) je tzv. kvadratické rozšíření tělesa Q.

(3) R není algebraickým rozšířením tělesa Q, protože polynomů Q[x] je pouze spočetně mnoho a každý má pouze konečně mnoho kořenů, tedy všech reálných kořenů Q[x] je opět pouze spočetně. Ovšem množina R spočetná není.

(4) Prvek \sqrt[5]{3} je kořenem polynomu x^{5} − 3 ∈ Q[x] a prvek \sqrt[7]{11} kořenem polynomu x^{7} − 11 ∈ Q[x], tedy oba jsou algebraické nad Q. Podle Poznámky 9.8(4) je Q(\sqrt[5]{3}, \sqrt[7]{11}) = Q[\sqrt[5]{3}, \sqrt[7]{11}] algebraické rozšíření. Z toho plyne, že například pro prvek α = 5\sqrt[5]{3} + 2\sqrt[7]{11} − \sqrt[5]{27}\sqrt[7]{11} − 3 existuje polynom p ∈ Q[x], jehož je α kořenem.

Poznámka 9.11. Bud’ T_{1} ⊆ U_{1} a T_{2} ⊆ U_{2} komutativní tělesa, bud’ f : T_{1} → T_{2} izomorfismus a necht’ α ∈ U_{1} je algebraický prvek nad T_{1} a β ∈ U_{2} je algebraický prvek nad T_{2}. Pak existuje takový izomorfismus g : T_{1}(α) → T_{2}(β), že g(α) = β a g(t) = f(t) pro všechna t ∈ T_{1}, právě když f_{x}(m_{α}) = m_{β}.

Důkaz. (⇒) Poznamenejme, že f_{x} je podle Poznámky 9.1(3) izomorfismus okruhů T_{1}[x] a T_{2}[x], proto je f_{x}(m_{α}) ireducibilní. Dále j_{g(α)}f_{x}(m_{α}) = j_{g(α)}g_{x}(m_{α}) = g(j_{α}(m_{α})) = g(0) = 0 podle Poznámky 9.1(4), tedy β = g(α) je kořenem polynomu f_{x}(m_{α}) ∈ T_{2}[x] ⊂ U_{2}[x]. Podle Věty 9.6 m_{β}/f_{x}(m_{α}). Protože je f_{x}(m_{α}) ireducibilní a monický, dostáváme nutně m_{β} = f_{x}(m_{α}).

(⇐) Stačí si uvědomit, že Věta 9.6 zaručuje existenci izomorfismů

i_{α} : T_{1}[x]/(m_{α}T_{1}[x]) → T_{1}(α), i_{β} : T_{2}[x]/(m_{β}T_{2}[x]) → T_{2}(β)

a že izomorfismus f_{x} indukuje podle předpokladu izomorfismus faktorových okruhů \overline{f_{x}} : T_{1}[x]/(m_{α}T_{1}[x]) → T_{2}[x]/(m_{β}T_{2}[x]), kde \overline{f_{x}}(p + m_{α}T_{1}[x]) = f_{x}(p) + m_{β}T_{2}[x]. Složíme-li izomorfismy dostáváme

T_{1}(α) ≅ (T_{1}[x])_{m_{α}} ≅ (T_{2}[x])_{m_{β}} ≅ T_{2}(β),

tedy máme izomorfismus g = i_{β}\overline{f_{x}}i_{α}^{−1}. Nyní zbývá spočítat

g(t) = i_{β}\overline{f_{x}}i_{α}^{−1}(t) = i_{β}\overline{f_{x}}(tx^{0} + m_{α}T_{1}[x]) = i_{β}(f(t)x^{0} + m_{β}T_{2}[x]) = f(t)

pro každé t ∈ T_{1} a podobně

g(α) = i_{β}\overline{f_{x}}i_{α}^{−1}(α) = i_{β}\overline{f_{x}}(x^{1} + m_{α}T_{1}[x]) = i_{β}(x^{1} + m_{β}T_{2}[x]) = β.
□

Věta 9.12. Necht’ T_{1} a T_{2} jsou komutativní tělesa, f : T_{1} → T_{2} je izomorfismus a necht’ U_{1} je rozkladové nadtěleso polynomu p ∈ T_{1}[x] a U_{2} je rozkladové nadtěleso polynomu f_{x}(p) ∈ T_{2}[x]. Označme α_{1}, …, α_{n} všechny kořeny polynomu p v U_{1} a β_{1}, …, β_{m} všechny kořeny polynomu f_{x}(p) v U_{2}. Potom n = m a existuje permutace σ a izomorfismus g : U_{1} → U_{2} tak, že g(α_{i}) = β_{σ(i)} pro i = 1, …, n a g(t) = f(t) pro všechna t ∈ T_{1}.

Důkaz. Znovu si všimněme, že f_{x} je izomorfismus okruhů T_{1}[x] a T_{2}[x]. Tvrzení dokážeme indukcí podle stupně k = deg p = deg f_{x}(p). Protože je rozkladové nadtěleso polynomu stupně 1 nad tělesem T_{1} (T_{2}) rovno T_{1} (T_{2}) stačí pro k = 1 položit g = f.

Předpokládejme, že tvrzení platí pro každou dovojici těles T_{1} a T_{2} a každý polynom stupně k − 1 nad tělesem T_{1} a mějme polynom p ∈ T_{1}[x] ⊆ U_{1}[x] stupně k. Protože α_{n} ∈ U_{1} je kořenem p, minimální polynom m_{α_{n}} dělí p podle 9.6, a proto f_{x}(m_{α_{n}}) dělí f_{x}(p). Poznamenejme, že deg m_{α_{n}} = deg f_{x}(m_{α_{n}}) > 0 a že rozklad na ireducibilní prvky je podle 8.11 a 7.10 v okruhu U_{2}[x] jednoznačný až na asociovanost, proto existuje (ireducibilní polynom) x − β_{i}, který dělí f_{x}(m_{α_{n}}), bez újmy na obecnosti můžeme předpokládat, že i = m. Použijeme-li opět Větu 9.6, vidíme, že je polynom f_{x}(m_{α_{n}}) ireducibilní (nad T_{2}) a monický, β_{m} je jeho kořen (nad U_{2}), a proto f_{x}(m_{α_{n}}) = m_{β_{m}}. Nyní podle 9.11 existuje izomorfismus těles h : T_{1}(α_{n}) → T_{2}(β_{m}), pro nějž platí, že h(α_{n}) = β_{m} a h(t) = f(t) pro všechna t ∈ T_{1}. Zároveň můžeme v okruhu T_{1}(α_{n})[x] vydělit polynom p polynomem x − α_{n}, tedy najdeme polynom q ∈ T_{1}(α_{n})[x] stupně k − 1, pro který p = (x − α_{n})q, a tudíž f_{x}(p) = f_{x}(x−α_{n})f_{x}(q) = (x−β_{m})f_{x}(q). Využijeme-li nyní indukčního předpokladu pro tělesa T_{1}(α_{n}) a T_{2}(β_{m}), jejich izomorfismus h a polynom q, dostáváme, že n − 1 = m − 1, existuje permutace σ′ na S_{n−1} a takový izomorfismus g : U_{1} → U_{2}, že g(α_{i}) = β_{σ(i)} pro i = 1, …, n − 1 a g(s) = h(s) pro všechna s ∈ T_{1}(α_{n}). Zřejmě tedy n = m, g(t) = h(t) = f(t) pro všechna s ∈ T_{1} a g(α_{n}) = β_{m}. □

Použijeme-li 9.12 pro f = Id dostáváme

Důsledek 9.13. Necht’ T je komutativní těleso, p ∈ T [x]. Pak existuje až na izomorfismus právě jedno rozkladové nadtěleso polynomu p.

10. Konečná tělesa

Poznámka 10.1. Bud’ T komutativní těleso (prvočíselné) kladné charakteristiky p, bud’ n přirozené číslo a necht’ q = p^{n}. Pak množina Q = {t ∈ T | t^{q} = t} tvoří podtěleso T.

Důkaz. Nejprve uvážíme, že f_{p} : T → T, f_{p}(a) = a^{p} je okruhový homomorfismus. Okamžitě vidíme, že 0^{p} = 0, 1^{p} = 1, (a·b)^{p} = a^{p} ·b^{p}. Dále (a+b)^{p} = ∑_{i=0}^{p} \binom{p}{i}×(a^{i} · b^{p−i}) = a^{p}+b^{p}, protože p/\binom{p}{i} pro každé i = 1, …, p−1, tedy ∑_{i=1}^{p−1} \binom{p}{i}×(a^{i}·b^{p−i}) = 0. Indukčním argumentem zjistíme, že f_{p^{i}} = f_{p^{i−1}}f_{p} je homomorfismus okruhů pro každé kladné i. Proto (a+b)^{p^{n}} = f_{p^{n}}(a+b) = f_{p^{n}}(a)+f_{p^{n}}(b) = a^{p^{n}} +b^{p^{n}} a podobně (−a)^{p^{n}} = −a^{p^{n}}, (a·b)^{p^{n}} = a^{p^{n}} ·b^{p^{n}}. Konečně například přímým výpočtem zjistíme, že (a^{−1})^{p^{n}} = (a^{p^{n}})^{−1} pro každé nenulové a. Mějme nyní a, b ∈ Q, tj (a^{p^{n}} = a, b^{p^{n}} = b). Pak (a + b)^{p^{n}} = a^{p^{n}} + b^{p^{n}} = a + b a podobně (a · b)^{p^{n}} = a^{p^{n}} · b^{p^{n}} = a · b, (−a)^{p^{n}} = −a^{p^{n}}. Je-li navíc a ≠ 0, potom (a^{−1})^{p^{n}} = (a^{p^{n}})^{−1} = a^{−1}. čímž jsme ověřili, že a+b, a·b, −a, a^{−1} ∈ Q. Protože 0, 1 ∈ Q zřejmě, vidíme, že Q je podtěleso T □

Poznámka 10.2. Necht’ T je konečné komutativní těleso, pak P = {k × 1| k ∈ N} ≅ Z_{p}, kde p je prvočíslo, je podtěleso T a existuje n tak, že |T | = |P |^{n} = p^{n}.

Důkaz. Snadno nahlédneme, že P ≅ Z/pZ ≅ Z_{p}, proto je P těleso a T má strukturu konečného vektorového prostoru nad P. Je-li n = dim_{P} (T), dostáváme, že |T | = |P |^{n} = p^{n}. □

Věta 10.3. Necht’ q ∈ N. Pak existuje komutativní těleso o q prvcích, právě když q = p^{n} pro nějaké prvočíslo p a přirozené číslo n. Těleso o p^{n} prvcích je izomorfní rozkladovému nadtělesu polynomu x^{p^{n}} − x nad Z_{p}.

Důkaz. (⇒) plyne okamžitě z 10.2.

(⇐) Ukážeme, že rozkladové nadtěleso T polynomu x^{p^{n}} − x nad Z_{p} má právě p^{n} prvků. Protože p nedělí p^{n} − 1, nemá polynom x^{p^{n}} − x podle 8.15(3) žádný vícenásobný kořen. Těleso T tedy obsahuje aspoň p^{n} prvků. V důsledku 10.1 je množina Q = {t ∈ T | t^{p^{n}} = t} podtělesem, navíc t^{p^{n}} = t právě když je t kořen polynomu x^{p^{n}} − x, tedy |Q| = p^{n} (opět podle 8.10) a Q = T.

Vezmeme-li nyní libovolně těleso U o p^{n} prvcích, pak pro každé u ∈ U \ {0} u^{p^{n}−1} = 1 podle 2.6, a proto u^{p^{n}} = u pro všechna u ∈ U. Využijeme-li dále 10.2, dostaneme, že všechny prvky U jsou kořenem polynomu x^{p^{n}} − x nad tělesem P = {k × 1| k ∈ N} ≅ Z_{p}, tedy U je rozkladové nadtěleso polynomu x^{p^{n}} − x nad tělesem P. Závěr potom plyne z 9.12 □

Jednoznačně (až na izomorfismus) určené těleso o p^{n} prvcích se zpravidla značí GF (p^{n}) (GF = Galois field).

Věta 10.4. Konečné komutativní těleso T obsahuje podtěleso o q prvcích právě tehdy, když q/|T | a q − 1/|T | − 1. Takové podtěleso je právě jedno.

Důkaz. (⇒) plyne z Lagrangeovy věty (1.13) použité pro grupy T (+) a T \ {0}(·).

(⇐) Podle 10.3 existuje takové prvočíslo p a přirozené číslo n |T | = p^{n}, tedy q = p^{k} pro vhodné přirozené číslo k ≤ n. Díky 8.17 víme, že T \ {0}(·) je cyklická grupa, a proto podle 2.9 existuje její (jednoznažně určená) podgrupa G řádu q − 1. Protože podle 2.8 u^{q−1} = 1 pro každé u ∈ G, obshuje množina Q = G ∪ {0} právě všechny kořeny polynomu x^{p^{n}} − x. Tedy Q = {u ∈ T | u^{q} = u} je podtěleso o q prvcích díky 10.1. Jeho jednoznačnost plyne z 2.8 a 2.9. □

Poznámka 10.5. Necht’ p je prvočíslo a k, n přirozené číslo. Pak k/n právě tehdy, když (p^{k} − 1)/(p^{n} − 1).

Důkaz. (⇒) Jestliže n = kd, snadno spočítáme, že p^{n} − 1 = (p^{k} − 1) ∑_{i=0}^{d−1} p^{ik}.

(⇐) Necht’ (p^{k} − 1)/(p^{n} − 1) a n = kd + r, kde 0 ≤ r < k. Víme, že p^{kd} − 1 = (p^{k} −1) ∑_{i=0}^{d−1} p^{ik}, tedy (p^{k} −1)/((p^{n} −1)−(p^{kd} −1)). Protože (p^{n} −1)−(p^{kd} −1) = p^{kd}(p^{r} − 1) a čísla p^{k} − 1 a p^{kd} jsou nesoudělná, máme (p^{k} − 1)/(p^{r} − 1). Ovšem r < k, proto r = 0. □

Věta 10.6. Pro každé konečné komutativní těleso T a přirozené číslo n existuje nad T ireducibilní polynom stupně n.

Důkaz. Z 10.3 víme, že |T | = p^{k} pro vhodné přirozené k a že existuje těleso U, které má p^{nk} prvků. Navíc (p^{k} − 1)/(p^{nk} − 1) podle 10.5, proto díky 10.4 a 10.3 obsahuje U podtěleso izomorfní T, bez újmy na obecnosti můžeme toto podtěleso s tělesem T ztotožnit. Nyní si stačí uvědomit, že U \ {0}(·) je cyklická grupa, a zvolit nějaký generátor α grupy U \ {0}. Prvek α je podle 9.8(3) algebraický a U \ {0} = ⟨α⟩ ⊆ T (α), proto T (α) = U a deg(m_{α}) = [U : T] = n podle 9.8(1), kde m_{α} je minimální polynom algebraického prvku α nad T. Konečně m_{α} je nad T ireducibilní podle 9.6. □

Poznámka 10.7. Necht’ T je konečné komutativní těleso. Každý ireducibilní polynom stupně n z okruhu T[x] dělí polynom x^{|T |^{n}} − x.

Důkaz. Necht’ m ∈ T[x] ireducibilní polynom stupně n, bez újmy na obecnosti můžeme předpokládat, že je m monický. Položme q = |T | = p^{k} pro vhodné prvočíslo p a vhodné přirozené k a bud’ U těleso o p^{kn} prvcích. Podobně jako v důkazu 10.6 můžeme bez újmy na obecnosti ztotožnit těleso T s izomorfním podtělesem tělesa U, které existuje podle 10.4. Těleso U je podle 10.3 rozkladovým nadtělesem polynomu x^{q^{n}} − x nejen nad tělesem Z_{p}, nýbrž i nad každým větším podtělesem, tedy i nad tělesem T. Dále podle 9.3 je (T[x])_{m} komutativní těleso o p^{kn} prvcích, v němž má polynom m kořen. Protože (T[x])_{m} ≅ U a izomorfismus lze díky 9.12 vzít tak, aby byl na podtělesech T identický, má m kořen v U, označme ho α. Snadno s pomocí 9.6 nahlédneme, že m je minimálním polynomem prvku α nad tělesem T, a protože je α kořenem polynomu x^{q^{n}} − x, máme m/(x^{q^{n}} − x) v okruhu T[x]. □

Věta 10.8. Necht’ T je konečné komutativní těleso, d přirozené číslo a u ∈ T[x] ireducibilní polynom stupně n. Položme q = |T |. Následující tvrzení jsou ekvivalentní:

(a) (x^{q^{n}} − x)/(x^{q^{d}} − x) v T[x],

(b) u/(x^{q^{d}} − x) v T[x],
(c) (q^{n} − 1)/(q^{d} − 1) v Z,
(d) n/d v Z.

Důkaz. (a)⇒(b) z 10.7 plyne, že u/(x^{q^{n}} − x) a z tranzitivity relace / dostáváme závěr.

(b)⇒(c) Opět uvážíme, že rozkladové nadtěleso U polynomu (x^{q^{d}} − x) nad Z_{p} má podle 10.3 právě q^{d} prvků a obsahuje jako podtěleso těleso izomorfní T (a ta můžeme ztotožnit) podle 10.4. Protože u/(x^{q^{d}} − x) existuje nad tělesem U kořen α ∈ U polynomu u. To znamená, že je minimální polynom m_{α} algebraického prvku α nad T asociován s polynomem u a tudíž [T (α) : T] = deg m_{α} = deg u = n podle 9.8(1). Tedy |T (α)| = q^{n} a (q^{n} − 1)/(q^{d} − 1) podle 10.4.

(c)⇒(a) Použijem obdobný argument jako v důkazu 10.5: je-li (q^{d} − 1) = s(q^{n} − 1),pak (x^{q^{d}} − x) = x(x^{q^{n}−1} − 1) ∑_{i=0}^{s−1} x^{i(q^{n}−1)}.

(c)⇔(d) Protože q = p^{r} pro vhodné přirozené r a prvočíslo p podle 10.3, máme ((p^{r})^{n} − 1)/((p^{r})^{d} − 1) ⇔ rn/rd díky 10.5, což zřejmě nastává ⇔ n/d. □

Uvážíme-li, že se pro každé prvočíslo p polynom x^{(p^{n})^{d}} − x ∈ Z_{p}[x] nad svým rozkladovým nadtělesem U podle 8.15(3) rozkládá na různé kořenové činitele, tedy na vzájemně neasociované polynomy, nemohou být vzájemně asociovány ani členy ireducibilního rozkladu x^{(p^{n})^{d}} − x v jakémkoli podtělese tělesa U. Díky předchozí větě dostaneme:

Všimněme si, že je-li p prvočíslo, n přirozené číslo a q = p^{n}, pak je polynom x^{q^{d}} − x právě součinem všech monických ireducibilních polynomů nad tělesem GF (q^{d}) všech stupňů k, které dělí d.

Příklad 10.9. (1) Hledáme-li nerozložitelné polynomy ze Z_{2}[x] stupně 4, víme z 10.7, že všechny musí dělit polynom x^{16} − x, resp. x^{15} − 1. Dále nám 10.8 říká, že nerozložitelný polynom stupně k (≤ 4) dělí polynom x^{16} − x právě když k/4 (tj. právě když existuje podtěleso šestnáctiprvkového tělesa o 2^{k} prvcích). Tudíž polynom x^{16}−x budou dělit právě všechny nerozložitelné polynomy stupně 1, 2 a 4. Jediným nerozložitelným polynomem stupně 2 nad tělesem Z_{2} je polynom x^{2}+x+1. Snadno spočítáme, že x^{16} − x = x(x − 1)(x^{2} + x + 1)(x^{12} + x^{9} + x^{6} + x^{3} + 1), tedy polynom x^{12} + x^{9} + x^{6} + x^{3} + 1 už nutně musí být součinem všech nerozložitelných polynomů stupně 4 (zřejmě existují právě 3). Dopočítáme, že x^{12}+x^{9}+x^{6}+x^{3}+1 = (x^{4} + x^{3} + x^{2} + x + 1)(x^{4} + x^{3} + 1)(x^{4} + x + 1).

(2) Protože těleso o 2^{7} prvcích obsahuje pouze vlastní podtěleso o 2 prvcích (7 je totiž prvočíslo), je polynom x^{128} − x nad Z_{2} součinem právě všech ireducibilních polynomů stupně 1 (takové jsou právě 2) a stupně 7. Proto nad Z_{2} existuje právě 18 = \frac{128−2}{7} nerozložitelných polynomů stupně 7.

(3) Spočítáme pomocí 10.8 neasociované nerozložitelné polynomy stupně šest nad tělesem Z_{3}. Víme, že polynom x^{729} − x se rozkládá na součin všech vzájemně neasociovaných (mají totiž různé kořeny) ireducibilních polynomů stupně k/6, tedy rozklad x^{729} − x na ireducibilní činitele obsahuje právě polynomy stupně 1, 2, 3 a 6. Zřejmě máme právě 3 neasociované ireducibilní polynomy stupně 1 a snadno spočteme (např. stejným postupem pro polynom x^{9} − x), že existují rovněž 3 neasociované neireducibilní polynomy stupně 2. Konečně pomocí rozkladu polynomu x^{27} − x na nerozložitelné polynomy (stejnou metodou) zjistíme, že existuje až na asociovanost 8 = \frac{27−(3·1)}{3} neireducibilních polynomů stupně 3. Tedy snadno dopočítáme, že neasociovaných ireducibilních polynomů stupně 6 nad Z_{3} existuje právě 116 = \frac{729−(3·1+3·2+8·3)}{6}.

11. Volné algebry a variety

Definice. Je-li I množina, budeme říkat zobrazení Ω : I → N typ. Řekneme, že algebra A(α_{i}| i ∈ I) je typu Ω, pokud pro každé i ∈ I je α_{i} právě Ω(i)-ární operací.

Definice. Bud’ Ω : I → N nějaký typ, X množina a necht’ indexovaná množina symbolů operací {α_{i}| i ∈ I} je disjunktní s X. Definujme indukcí posloupnost množin W_{i}:

W_{0} = {α_{i}| i ∈ I, Ω(i) = 0} ∪ X a

W_{n+1} = {(α_{i}, w_{1}, …, w_{Ω(i)})| i ∈ I, w_{j} ∈ W_{n}, Ω(i) ≠ 0} ∪ W_{n}.

Položme W_{Ω}(X) = ⋃_{n∈N} W_{n} a definujme pro každé i ∈ I na množině W_{Ω}(X) Ω(i)-ární operaci α_{i} předpisem α_{i}(w_{1}, …, w_{Ω(i)}) = (α_{i}, w_{1}, …, w_{Ω(i)}). Potom algebru W_{Ω}(X)(α_{i}| i ∈ I) (typu Ω) nazveme (absolutně volnou) algebrou termů nad X typu Ω.

Příklad 11.1. Bud’ X = {x} jednoprvková množina písmen, I = {∗} a Ω(∗) = 1, tedy uvažujeme jednu unární operaci. Potom W_{Ω}(X) = {x, (α_{∗}, x), (α_{∗}, α_{∗}, x), … }, proto je W_{Ω}(X) nekonečná.

Poznámka 11.2. Necht’ Ω : I → N_{0} nějaký typ a X je množina. Potom X generuje algebru termů W_{Ω}(X)(α_{i}| i ∈ I).

Důkaz. Dokážme indukcí podle n, že W_{n} ⊆ ⟨X⟩. Zřejmě W_{0} ⊆ ⟨X⟩. Necht’ W_{n} ⊆ ⟨X⟩. Vezmeme-li i ∈ I, pro něž Ω(i) ≠ 0, a w_{1}, …, w_{Ω(i)} ∈ W_{n} ⊆ ⟨X⟩, pak (α_{i}, w_{1}, …, w_{Ω(i)}) = α_{i}(w_{i}, …, w_{Ω(i)}) ∈ ⟨X⟩, proto W_{n+1} ⊆ ⟨X⟩. □

Poznámka 11.3. Bud’ Ω : I → N_{0} typ, X množina a A(α_{i}| i ∈ I) algebra typu Ω. Pak pro každé zobrazení φ : X → A existuje právě jeden homomorfismus \overline{φ} : W_{Ω}(X) → A tak, že \overline{φ}|_{X} = φ.

Důkaz. Budeme induktivně rozšiřovat zobrazení φ na množiny W_{n}. Nejprve definujme φ_{0} : W_{0} → A předpisem φ_{0}(x) = φ(x) pro všechna x ∈ X a φ_{0}(α_{i}) = α_{i} pro všechna taková i, pro něž Ω(i) = 0. Máme-li definováno φ_{n} : W_{n} → A rozšíříme ho na φ_{n+1} : W_{n+1} → A φ_{n+1}(α_{i}, w_{1}, …, w_{Ω(i)}) = α_{i}(φ_{n}(w_{1}), …, φ_{n}(w_{Ω(i)})), jestliže i ∈ I, Ω(i) ≠ 0 a w_{1}, …, w_{Ω(i)} ∈ W_{n}. Konečně položme \overline{φ} = ⋃_{n} φ_{n}, Z konstrukce je zjevné, že jde o jedinou možnou definici rozšiřujícího homomorfismu. □

Věta 11.4. Každá algebra daného typu Ω je homomorfním obrazem algebry W_{Ω}(X) pro nějakou množinu X.

Důkaz. Stačí vzít za X libovolnou množinu generátorů (například celou algebru) a identitu na X rozšířit podle 11.3 na příslušný homomorfismus. □

Poznámka 11.5. Necht’ Ω je typ a X a Y množiny. Pak je algebra termů W_{Ω}(X) nad X izomorfní algebře termů W_{Ω}(Y) nad Y právě tehdy, když existuje bijekce mezi X a Y (tj. |X| = |Y |).

Důkaz. (⇒) Vezměme nějaký izomorfismus φ : W_{Ω}(X) → W_{Ω}(Y). Nejprve dokážeme, že φ(X) ⊆ Y. Předpokládejme, že existuje x ∈ X, pro které φ(x) = w ∉ Y, tj. bud’ existuje i ∈ I, pro něž Ω(i) = 0 a w = α_{i} nebo existuje n > 0, pro něž w ∈ W_{n} \ W_{n−1}. První možnost je ovšem ve sporu s prostotou φ, protože φ(x) = φ(α_{i}), a protože w = α_{j}(w_{1}, …, w_{Ω(j)}) pro j ∈ I a w_{k} ∈ W_{n−1}, dostáváme x = α_{j}(φ^{−1}(w_{1}), …, φ^{−1}(w_{Ω(j)})) ∉ W_{0}, což rovněž není možné. Tedy φ(X) ⊆ Y a stejným argumentem pro inverzní izomorfismus obdržíme φ^{−1}(Y) ⊆ X, tudíž φ indukuje bijekci mezi X a Y

(⇐) Máme-li bijekci b : X → Y můžeme ji podle 11.3 rozšířit na homomorfismus φ : W_{Ω}(X) → W_{Ω}(Y) a její inverz b^{−1} : Y → X na homomorfismus ψ : W_{Ω}(Y) → W_{Ω}(X). Z jednoznačnosti rozšíření identity na X resp. Y na endomorfismus na W_{Ω}(X), resp. W_{Ω}(Y) plyne, že φψ = Id a ψφ = Id, tedy φ je izomorfismsu. □

Připomeňme definici součinové algebry. Mějme n ∈ N, neprázdný systém množin A_{j}, j ∈ J a systém n-árních operací α_{i} na A_{j}. Definujme operaci ∏_{j∈J} α_{i} na ∏_{j∈J} A_{j} vztahem

[∏_{j∈J} α_{i}(f_{1}, …, f_{Ω(i)})](j) = α_{i}(f_{1}(j), …, f_{Ω(i)}(j)),

kde f_{i} ∈ ∏_{j∈J} A_{j}.

Snadno nahlédneme, že ∏_{j∈J} A_{j}(∏_{j∈J} α_{i}| i ∈ I) opět algebra typu Ω (mluvíme o součinu algeber), je-li A_{j}(α_{i}| i ∈ I) neprázdný systém algeber stejného typu Ω.

Definice. Necht’ Ω je typ a X je nekonečná spočetná množina. Identitou nazveme libovolnou dvojici (u, w) ∈ W_{Ω}(X)×W_{Ω}(X). Řekneme, že algebra A typu Ω splňuje identitu (u, w), pokud pro každý homomorfismus φ : W_{Ω}(X) → A je φ(u) = φ(w). Třídu V algeber typu Ω nazveme varietou, existuje-li množina identit M tak, že V je tvořena právě všemi algebrami typu Ω splňujícími všechny identity z M.

Příklad 11.6. 1) Třída všech grup tvoří varietu (přitom tato varieta splňuje identity (x · (y · z), (x · y) · z), (x · 1, x), (1 · x, x) a (x · x^{−1}, 1)).

2) Třída všech komutativních grup tvoří varietu (k identitám grupy přibyde ještě komutativita: (x · y, y · x)).

3) Třída všech okruhů tvoří varietu.

Věta 11.7 (Birkhoff). Třída V algeber typu Ω je varieta právě tehdy, když je V uzavřená na všechny podalgebry, homomorfní obrazy a součiny algeber z V.

Důkaz. (⇒) Necht’ V je varieta s množinou identit M. Zvolme A ∈ V a vezměme nějakou podalgebru B algebry A. Označme i : B → A inkluzi množin a všimněme si, že je i homomorfismus. Máme-li nyní (u, w) ∈ M a libovolný homomorfismus φ : W_{Ω}(X) → B, pak iφ je homomorfismus W_{Ω}(X) do A, proto iφ(u) = iφ(w). Ovšem i je prosté zobrazení, tedy φ(u) = φ(w).

Nyní vezměme homomorfismus ψ : A → B, kde opět A ∈ V, (u, w) ∈ M a homomorfismus φ : W_{Ω}(X) → ψ(B). Pro každé x ∈ X definujme zobrazení μ : X → A podmínkou μ(x) ∈ ψ(φ(x))^{−1}. Zobrazení μ můžeme podle 11.3 rozšířit na homomorfismus \overline{μ} : X → ψ(B), pro nějž ψ\overline{μ} = φ. Protože \overline{μ}(u) = \overline{μ}(w), dostáváme i φ(u) = ψ\overline{μ}(u) = \overline{μ}(w) = φ(w), tedy ψ(B) ∈ V.

Konečně mějme systém algeber A_{j} ∈ V, kde j ∈ J, a homomorfismus φ : W_{Ω}(X) → ∏_{j∈J} A_{j} a (u, w) ∈ M. Označme π_{k} : ∏_{j∈J} A_{j} → A_{k} pro každé ∈ J přirozenou projekci na k-tou složku a všimněme si, že se jedná o homomorfismus. Protože π_{k}φ(u) = π_{k}φ(w) pro každé ∈ J, je podle definice součinu algeber φ(u) = φ(w).

(⇐) Vezměme množinu všech identit M, které splňuje každá algebra a dále označme U varietu všech algeber splňujících M. Zřejmě V ⊆ U.

Nejprve zvolme libovolnou algebru A ∈ U. Díky 11.4 existuje množina Y a homomorfismus p : W_{Ω}(Y) → A na celou algebru A. Uvážíme množinu R všech kongruencí ρ na W_{Ω}(Y), pro něž W_{Ω}(Y)/ρ ∈ V. Vidíme, že ∏_{ρ∈R} W_{Ω}(Y)/ρ ∈ V podle předpokladu a dále přirozeně definované zobrazení ψ : W_{Ω}(Y) → ∏_{ρ∈R} W_{Ω}(Y)/ρ je homomorfismus. Proto pro kongruenci ρ_{0} = ⋂_{ρ∈R} ρ pomocí 1. věty o izomorfismu dostáváme vztah W_{Ω}(Y)/ρ_{Y} = W_{Ω}(Y)/ker ψ ≅ ψ(W_{Ω}(Y)), tedy W_{Ω}(Y)/ρ_{Y} je podalgebra součinové algebry z V, tedy i W_{Ω}(Y)/ρ_{Y} ∈ V a ρ_{Y} je nejmenší kongruence na W_{Ω}(Y), pro níž W_{Ω}(Y)/ρ_{Y} ∈ V.

Nyní ukážeme, že ρ_{Y} ⊆ ker p. Vezměme (a, b), aby platilo, že p(a) ≠ p(b) a necht’ X je spočetná (stačí samozřejmě konečná) podmnožina Y, která obsahuje všechna písmena termů z a a b. Protože W_{Ω}(X) ⊆ W_{Ω}(Y) a restrikce p na W_{Ω}(X) indukuje homomorfismus W_{Ω}(X) → A, identita (a, b) na A není splněna, proto existuje algebra B ∈ V a takový homomorfismus f : W_{Ω}(X) → B, že f(a) ≠ f(b), který můžeme díky 11.3 rozšířit (na Y \ X zobrazení dodefinujeme libovolně) na homomorfismus f : W_{Ω}(Y) → B. To znamená, že (a, b) ∉ ρ_{Y}.

Konečně použitím 1. a 2.věty o izomorfismu dostáváme, že A ≅ W_{Ω}(Y)/ker p je izomorfní faktorové algebře W_{Ω}(Y)/ρ_{Y}, tedy díky uzavřenosti V na faktory dostáváme, že A ∈ V. □

Příklad 11.8. Třída všech těles není podle Birkhoffovy věty varietou, nebot’ součin dvou těles (např. Z_{2} × Z_{2}) není tělesem.

12. Ireducibilní rozklad polynomů

Definice. Řekneme, že polynom f je bez čtverců, jestliže neexistuje žádný takový polynom g (nad týmž tělesem) kladného stupně, aby g^{2}/f. Je-li f = ∏_{i=1}^{n} f_{i}^{i}, kde všechny polynomy f_{i} jsou bez čtverců, mluvíme o bezčtvercovém rozkladu polynomu f.

Poznámka 12.1. Pro každý polynom nad komutativním tělesem existuje bezčtvercový rozklad.

Důkaz. Bezprostřední důsledek 7.10 spolu s 8.11. □

Poznámka 12.2. Necht’ T je komutativní těleso, f ∈ T [x]. Pak je f bez čtverců právě když 1 je NSD(f, f′).

Důkaz. Postupujeme podobně jako v Poznámce 8.11. Jestliže f = g^{2}h, pak podle 8.10(3) f′ = g · (gh)′ + g′ · gh = g · ((gh)′ + g′h), tedy g/f′.

Předpokládejme, že 1 není NSD(f, f′), tedy podle 7.7 (2) existuje ireducibilní polynom g, který dělí f′ i f, tj. f = g · a, f′ = g · b. Protože g · b = f′ = (g · a)′ = g · a′ + g′ · a a protože g a g′ jsou nesoudělné, dostáváme, že g/a a tedy g^{2}/f. □

Příklad 12.3. [Bezčtvercový rozklad polynomu nad tělesem kladné charakteristiky] Mějme těleso T prvočíselné charakteristiky p a f ∈ T [x]. Označujme nsd(a, b) jednoznačně určený monický polynom, který je NSD(a, b).

Položme c_{1} = nsd(f, f′), g_{1} = \frac{f}{c_{1}} , h_{1} = nsd(c_{1}, g_{1}), a induktivně definujme posloupnosti {c_{i}}, {g_{i}}, {h_{i}}:

c_{i} = \frac{c_{i−1}}{h_{i−1}} , g_{i} = h_{i−1}, h_{i} = nsd(c_{i}, g_{i}).

Necht’ f = ∏_{i=1}^{n} f_{i}^{i} je bezčtvercový rozklad. Potom

f′ = [ ∑_{i∉pN} if′_{i}f_{i}^{i−1} · ∏_{j∉pN∪{i}} f_{j}^{j}] · [ ∏_{i∈pN} f_{i}^{i}],

a proto

c_{1} = nsd(f, f′) = [ ∏_{j∉pN} f_{j}^{j−1}] · [ ∏_{i∈pN} f_{i}^{i}].

Odtud dostáváme, že g_{1} = ∏_{j∉pN} f_{j} a h_{1} = ∏_{j≥2,j∉pN} f_{j}.

Podobně nahlédneme, že c_{k} = [∏_{j≥k,j∉pN} f_{j}^{j−1}] · [∏_{i∈pN} f_{i}^{i}] a že g_{k} = h_{k−1} = ∏_{j≥k,j∉pN} f_{j}. Odtud snadno spočítáme, že \frac{g_{k}}{h_{k}} = f_{k} pokud p nedělí p a \frac{g_{k}}{h_{k}} = 1 v opačném případě. Máme tedy algoritmus k nalezení členů bezčtvercového rozkladu pro všechna i, jež nedělí p. Všimneme-li si, že po konečně krocích dostaneme

c_{n} = [ ∏_{i∈pN} f_{i}^{i}] = ∑_{i} a_{i}x^{ip} = (∑_{i} a_{i}x^{i})^{p}.

Použijeme-li nyní rekurzivně algoritmus na polynom ∑_{i} a_{i}x^{i}, najdeme členy f_{i} bezčtvercový rozklad pro p/i, jestliže p^{2} nedělí i. Dále můžeme pokračovat rekurzí.

Podrobnosti viz [MS].

Poznámka 12.4 (Čínská věta o zbytcích). Mějme konečné komutativní těleso T, navzájem nesoudělné ireducibilní polynomy f_{1}, …, f_{n} ∈ T[x] a položme f = ∏_{i=1}^{n} f_{i}. Pak je zobrazení φ : T[x]/fT [x] → ∏_{i=1}^{n} T [x]/f_{i}T [x] dané předpisem φ([g]_{f}) = ([(g)modf_{1}], … [(g)modf_{n}]) okruhový izomorfismus.

Důkaz. Obdobný jako u Čínské věty o zbytcích pro okruh celých čísel. □

Věta 12.5. Bud’ T konečné komutativní těleso a f monický bezčtvercový polynom. Označme V = T [x]/fT [x] a W = {u ∈ V | u^{|T |} = u}.

(1) V je vektorový prostor nad tělesem T a W jeho podprostor.

(2) Je-li f součinem k ireducibilních polynomů, pak dim_{T} W = k.

(3) Je-li [u]_{f} ∈ W a 1 ≤ deg u ≤ deg f, potom f = ∏_{s∈T} nsd(u − s, f).

(4) Je-li [u_{1}]_{f} … [u_{k}]_{f} báze vektorového prostoru W a g a h dva neasociované ireducibilní faktory f, potom existuje takové i ≤ k a s ∈ T, že g dělí (w_{i} −s) a h nedělí (w_{i} − s).

Důkaz. (1) V je komutativní grupou s přirozeně definovaným násobením skalárem, o němž snadno nahlédneme, že tvoří na V strukturu vektorového prostoru. Abychom dokázali, že je W jeho podprostor, stačí podobně jako v 10.1 využít toho, že zobrazení u → u^{|T |} tvoří endomorfismus na T [x] a tedy i na V = T [x]/fT [x]. Ovšem z 10.3 plyne, že t^{|T |} = t pro každé t ∈ T a (a+b)^{p} = a^{p}+b^{p}, kde a, b ∈ T [x] a |T | = p^{n} pro prvočíslo p, protože je p charakteristika okruhu T [x], tudíž i (a+b)^{p^{n}} = a^{p^{n}}+b^{p^{n}}.

(2) Bud’ f = f_{1} · · · · · f_{k} rozklad f na monické ireducibilní polynomy a označme V_{i} = T [x]/f_{i}T [x] a W_{i} = {u ∈ V_{i}| u^{|T |} = u}. Podle 12.4 je zobrazení φ : V → ∏_{i=1}^{k} V_{i} dané předpisem φ([v]_{f}) = ([(v)mod f_{1}], … [(v)mod f_{n}]) izomorfismus okruhů (a zřejmě i vektorových prostorů) V a ∏_{i=1}^{k} V_{i}. Vidíme, že φ(W) ⊆ ∏_{i=1}^{k} W_{i} (⊆ ∏_{i=1}^{k} V_{i}). Protože dále pro každé (w_{1}, …, w_{k}) ∈ ∏_{i=1}^{k} W_{i}, existuje vzor w ∈ V, tj. φ(w) = (w_{1}, …, w_{k}), přičemž φ(w^{|T |}) = (w_{1}^{|T |}, …, w_{k}^{|T |}) = (w_{1}, …, w_{k}) = φ(w), tedy φ(W) = ∏_{i=1}^{k} W_{i}. Konečně si všimněme, že každý okruh V_{i} je těleso a W_{i} jeho podtěleso o nejvýše |T | prvcích díky 10.1 a zároveň je W_{i} nenulový vektorový |T |- prostor, má tedy právě |T | prvků. Tím jsme ověřili, že |W | = | ∏_{i=1}^{k} W_{i}| = |T |^{k}, proto je dim_{T} (W) = k.

(3) Využijeme-li faktu, že okruhy W_{i} jsou |T |-prvková tělesa a φ indukuje okruhový izomorfismus W a ∏_{i=1}^{k} W_{i}, pro každý prvek w ∈ W dostáváme w^{|T |} − w = ∏_{s∈T} (w − s) = 0, kde ztotožníme prvky tělesa T a rozkladové třídy [sx^{0}]_{f}. Je-li tedy [u]_{f} = w ∈ W, platí, že f/ ∏_{s∈T} (u − s), proto f/ ∏_{s∈T} nsd(u − s, f). Jelikož jsou polynomy u − s a u − t pro t ≠ s nesoudělné, dostáváme ∏_{s∈T} nsd(u − s, f)/f, a protože jsou oba polynomy monické dostáváme dokonce rovnost.

(4) Bez újmy na obecnosti oddělíme například polynomy f_{1} a f_{2}. Protože ω = ([1], [0], …, [0]) ∈ ∏_{i=1}^{k} W_{i}, existuje polynom w, pro nějž [u] ∈ W a φ([u]) = ω. To znamená, že f_{1}/u−1 a f_{2}/u, proto f_{2} nedělí u−1. Podle (3) plyne, že f_{1} nedělí u−s pro žádné s ∈ T \ {1}, tedy a f_{1}f_{2} nedělí u − s pro žádné s ∈ T. Předpokládejme nyní, že pro každé i existuje takové s_{i} ∈ T, že f_{1}f_{2}/(u_{i} − s_{i}) a vezměme T -lineární kombinaci u = ∑_{i=1}^{k} a_{i}u_{i}. Potom f_{1}f_{2}/ ∑_{i=1}^{k} a_{i}(u_{i} − s_{i}) = u − ∑_{i=1}^{k} a_{i}s_{i}, čímž dostáváme spor. Dokázali jsme, že existuje takové i, že f_{1}f_{2} nedělí (u_{i} − s) pro žádné s ∈ T. Nyní zbývá pomocí (3) zvolit s ∈ T, pro nějž f_{1}/(u_{i} − s). □

Příklad 12.6. [Berlekampův algoritmus] Pomocí předchozí věty budeme umět rozložit bezčtvercový polynom nad konečným tělesem, najdeme-li bázi vektorového prostoru W. Položme n = deg f, r = |T | a (x^{r(j−1)})mod f = ∑_{i=1}^{n} q_{ij}x^{i−1} pro každé j = 1, …, n. Nyní sestavíme matici Q = (q_{ij}). Všimneme-li si, že Qv^{T} = v^{T}, právě když (∑_{i<n} v_{i}x^{i})^{r} ≡ (∑_{i<n} v_{i}x^{i}) mod f, kde v = (v_{0}, …, v_{n−1}), stačí nám najít bázi řešení homogenní soustavy rovnic s maticí Q − I_{n}. Podrobnosti viz [MS].

13. Algebraický uzávěr

Definice. Řekneme, že je komutativní těleso U algebraicky uzavřené, jestliže se každý nenulový polynom p ∈ U[x] rozkládá nad U na kořenové činitele. Komutativní těleso U je algebraickým uzávěrem tělesa T, je-li U algebraicky uzavřené těleso, T ⊆ U, a žádné podtěleso V tělesa U, které obsahuje podtěleso T není algebraicky uzavřené.

Věta 13.1. Necht’ T je komutativní těleso. Pak existuje jeho algebraický uzávěr U.

Důkaz. Mějme κ nějaké ordinální číslo (nebo indexujme přirozenými čísly). Nejprve si uvědomíme, že sjednocení řetězce těles ⋃_{α<κ} U_{α}, kde U_{α} je podtěleso U_{β} pro každé α < β, má přirozeně dánu strukturu okruhu (operace jen stále rozšiřujeme) a je dokonce tělesem (inverzní prvek k prvku t ∈ U_{α} najdeme už v U_{α}). Zkonstruujeme posloupnost do sebe zařazených těles T_{i} ⊆ T_{i+1}, položme T_{1} = T.

Každé z těles T_{i} pro i > 1 přitom vytvoříme pomocí transfinitní indukce. Opatřeme nejprve indexy α < κ_{i} všechny polynomy nad T_{i} stupně nejvýše i + 1, t.j. {p_{α}| α < κ_{i}} = {p ∈ T_{i}[x]| deg p ≤ i + 1}. Položíme T_{i0} = T_{i}. Máme-li definováno těleso T_{iα} vezmeme jako těleso T_{iα+1} právě rozkladové nadtěleso polynomu p_{α} ∈ T_{i}[x] ⊆ T_{iα}[x] nad tělesem T_{iα}. Je-li β limitní ordinál položíme T_{iβ} = ⋃_{α<β} T_{iα}. Konečně definujme T_{i+1} = ⋃_{α<κ_{i}} T_{iα}.

Nyní stačí položit U = ⋃_{i∈N} T_{i}. Ukážeme, že U je algebraicky uzavřené. Jeli p ∈ U[x], pak existuje takové i, že jsou všechny koeficienty p v T_{i} (p má jen konečně mnoho různých koeficientů) a navíc deg p ≤ i + 1. To ovšem znamená, že se p rozkládá nad T_{i+1} ⊆ U na kořenové činitele.

Konečně poznamenejme, že algebraicky uzavřená podtělesa U tvoří uzávěrový systém, proto je průnik všech algebraicky uzavřených podtěles U obsahujících T hledaným algebraickým uzávěrem. □

Poznámka 13.2. Žádné konečné komutativní těleso není algebraicky uzavřené.

Důkaz. Je-li T je konečné těleso, polynom 1 + ∏_{t∈T} (x − t) (stupně |T |) nemá v T žádný kořen, tedy T není algebraicky uzavřené. □

Důsledek 13.3. Algebraický uzávěr konečného tělesa je nekonečný.

Všimneme-li si, že polynomů omezeného stupně nad konečným tělesem je jen konečně mnoho a že rozkladové nadtěleso libovolného polynomu nad konečným tělesem je opět konečné podle 9.9, vidíme, že hodnoty κ_{i} i všechna tělesa T_{iα} a T_{i} jsou v důkazu 13.1 konečná. Algebraický uzávěr konečného tělesa tedy leží ve spočetném sjednocení konečných těles, proto musí být spočetný.

[MS] - odkazuje na bakalářskou práci Milana Straky (2006)

http://fox.ucw.cz/papers/factoring/