Konečná tělesa Poznámka. Konečným tělesem rozumíme těleso mající konečně mnoho prvků. V Algebře I jsme dokázali, že pro každé konečné těleso K platí, že jeho multiplikativní grupa (K×, ·) je cyklická. Příklad. Pro libovolné prvočíslo p je okruh Zp zbytkových tříd modulo p konečné těleso charakteristiky p. Poznámka. Charakteristika libovolného tělesa je nula nebo prvočíslo. Protože každé těleso charakteristiky nula obsahuje podtěleso izomorfní s Q, má každé konečné těleso prvočíselnou charakteristiku. Připomeňme, že každé těleso K charakteristiky p = 0 obsahuje podtěleso izomorfní s tělesem Zp. Můžeme tedy prvky tohoto podtělesa ztotožnit s prvky tělesa Zp a považovat Zp za podtěleso tělesa K. Počet prvků konečného tělesa Věta 1. Nechť K je libovolné konečné těleso charakteristiky p. Pak K je jednoduchým rozšířením tělesa Zp a pro jeho počet prvků platí |K| = pm, kde m = [K : Zp]. Důkaz. Označíme-li c generátor cyklické grupy (K×, ·), platí K = Zp(c). Pak 1, c, c2, . . . , cm−1 je báze vektorového prostoru K nad Zp, a libovolný prvek tělesa K lze napsat ve tvaru r(c) pro jediný polynom r ∈ Zp[x] stupně st r < m. Takových polynomů je právě pm, protože každý z m koeficientů může nabývat libovolné z p hodnot. Věta 2. Nechť K je libovolné konečné těleso mající pm prvků. Pak každý prvek c ∈ K je kořenem polynomu xpm − x ∈ Zp[x]. Důkaz. Jistě je kořenem 0. Každý prvek c ∈ K, c = 0, je prvkem grupy (K×, ·) mající pm − 1 prvků. Z Lagrangeovy věty plyne cpm−1 = 1, a tedy cpm = c. Věta 3. Nechť p je libovolné prvočíslo a m přirozené číslo. Pak rozkladové těleso T polynomu h = xpm − x ∈ Zp[x] nad Zp má právě pm prvků. Důkaz. Nechť K = {t ∈ T; tpm = t} je množina všech kořenů polynomu h v T. Derivace h = pmxpm−1 − 1 = −1 je nesoudělná s polynomem h, a tedy h nemá žádný násobný kořen, proto |K| = pm. Ukážeme, že K je podtěleso tělesa T. Zřejmě 0, 1 ∈ K. Protože umocňujeme v komutativním okruhu na prvočíselnou charakteristiku p, z Algebry I víme, že pro libovolné prvky a, b ∈ T platí (a + b)p = ap + bp. Odtud indukcí (a + b)pn = apn + bpn pro libovolné n ∈ N. Pro libovolné prvky k, h ∈ K platí kpm = k, hpm = h, a tedy (k + h)pm = kpm + hpm = k + h, což znamená k + h ∈ K. Speciálně −1 = 1 + · · · + 1 p−1 ∈ K. Podobně (k · h)pm = kpm · hpm = k · h, odkud k · h ∈ K. Speciálně −k = (−1) · k ∈ K. Je-li k = 0, pak (k−1)pm = (kpm )−1 = k−1, a tedy k−1 ∈ K. Tedy K je těleso o pm prvcích. Rozkladové těleso je nejmenší těleso obsahující všechny kořeny daného polynomu, platí tedy T = K. Konstrukce konečného tělesa o daném prvků Důsledek. Nechť p je libovolné prvočíslo a m přirozené číslo. Pak existuje alespoň jeden normovaný ireducibilní polynom f ∈ Zp[x] stupně st f = m. Důkaz. Těleso T z věty 3 má pm prvků, tedy [T : Zp] = m. Podle věty 1 jde o jednoduché rozšíření T = Zp(c), minimální polynom prvku c nad Zp má stupeň m a je normovaný a ireducibilní. Poznámka. Chceme-li sestrojit těleso o pm prvcích, stačí nalézt normovaný ireducibilní polynom f ∈ Zp[x] stupně st f = m. Hledaným tělesem je pak faktorokruh R = Zp[x]/(f ). Pro prvek c = x + (f ) pak platí R = Zp(c) a minimálním polynomem prvku c je polynom f . Příklad. Sestrojme těleso o 16 prvcích. Polynom f = x4 + x + 1 ∈ Z2[x] je ireducibilní, tedy faktorokruh R = Z2[x]/(f ) je těleso a |R| = 24. Označíme-li c = x + (f ), je R = Z2(c) = {a3c3 + a2c2 + a1c + a0; a0, a1, a2, a3 ∈ Z2}. Při násobení prvků využíváme toho, že c je kořenem polynomu f , tedy platí c4 = c + 1. Konečné těleso je jednoznačně určeno svým počtem prvků (až na izomorfismus) Věta 4. Libovolná konečná tělesa o stejném počtu prvků jsou izomorfní. Důkaz. Nechť R je libovolné těleso mající pm prvků a nechť T je rozkladové těleso polynomu h = xpm − x ∈ Zp[x] nad Zp z věty 3. Ukážeme, že R ∼= T. Podle věty 1 existuje c ∈ R tak, že R = Zp(c). Označme f minimální polynom prvku c nad Zp. Podle věty 2 je c kořenem polynomu h, tedy f | h v Zp[x]. Protože h je v T[x] součinem lineárních činitelů, existuje v T kořen d polynomu f . Máme homomorfismy okruhů ϕc : Zp[x] → R a ϕd : Zp[x] → T, kde pro libovolné g ∈ Zp[x] je ϕc(g) = g(c) ∈ R a ϕd (g) = g(d) ∈ T. Platí ker ϕc = ker ϕd = (f ). Z hlavní věty o faktorokruzích dostáváme diagram: Zp[x] ϕd // ϕc  π %% %% T R Zp[x]/(f )? _˜ϕc oooo ? ˜ϕd OO Protože |R| = |T| ∈ N, je injekce ˜ϕd ◦ ( ˜ϕc)−1 : R → T bijekcí, tedy R ∼= T. Podtělesa konečného tělesa Věta 5. Nechť konečné těleso K charakteristiky p má pm prvků a nechť R je podtěleso tělesa K. Pak R má pd prvků, kde d | m. Důkaz. Podle věty 1 platí m = [K : Zp] = [K : R] · [R : Zp] = [K : R] · d. Věta 6. Nechť K je konečné těleso charakteristiky p mající pm prvků a nechť přirozené číslo d | m. Pak existuje jediné podtěleso R tělesa K mající pd prvků. Důkaz. Podle vět 3 a 4 jsou všechny prvky tělesa K jednoduchými kořeny polynomu xpm − x. Z d | m plyne (pd − 1) | (pm − 1), neboť (pd − 1)(p m d + p m d −d + · · · + pd + 1) = pm − 1. Analogicky (xpd −1 − 1) | (xpm−1 − 1) v Zp[x], a tedy (xpd − x) | (xpm − x). Proto K obsahuje pd kořenů polynomu xpd − x, které podle důkazu věty 3 tvoří podtěleso R tělesa K. Naopak každý prvek podtělesa o pd prvcích musí být podle věty 2 kořenem polynomu xpd − x, je tedy R jediné podtěleso tělesa K o pd prvcích. Rozklad polynomu xpm − x ∈ Zp[x] na ireducibilní činitele Věta 7. Nechť p je prvočíslo, m ∈ N. Polynom h = xpm − x ∈ Zp[x] je roven součinu všech normovaných ireducibilních polynomů v Zp[x], jejichž stupeň d | m. Důkaz. Podle věty 3 má polynom h pouze jednoduché kořeny, v jeho rozkladu na součin normovaných ireducibilních polynomů v Zp[x] má proto každý činitel jen jednoduché kořeny a žádný činitel se neopakuje. Nechť f je libovolný činitel v tomto rozkladu, d = st f . Rozkladové těleso T polynomu h obsahuje všech d jeho kořenů, přitom f je minimálním polynomem svému libovolnému kořenu c ∈ T, proto d = [Zp(c) : Zp], podle věty 5 tedy d | m. Nechť naopak je g ∈ Zp[x] libovolný normovaný ireducibilní polynom stupně d | m. Pak Zp[x]/(g) je konečné těleso o pd prvcích, ve kterém má polynom g kořen, podle vět 6 a 4 je toto těleso izomorfní s podtělesem tělesa T, proto má g také kořen c ∈ T. Minimálním polynomem prvku c je g, a tedy g | h. Počty normovaných ireducibilních polynomů Věta 8. Označme mp,d počet normovaných ireducibilních polynomů v Zp[x] stupně d. Pak pro libovolné m ∈ N platí d|m d · mp,d = pm. Důkaz. Stačí porovnat stupně v rozkladu polynomu h = xpm − x ∈ Zp[x] podle věty 7. Stupeň součinu všech mp,d normovaných ireducibilních polynomů stupně d je d · mp,d . Poznámka. Pomocí věty 8 můžeme počty mp,d určit rekurentně vzhledem k d: mp,1 = p, mp,1 + 2mp,2 = p2 ⇒ mp,2 = 1 2(p2 − p), mp,1 + 3mp,3 = p3 ⇒ mp,3 = 1 3(p3 − p), mp,1 + 2mp,2 + 4mp,4 = p4 ⇒ mp,4 = 1 4(p4 − p2), mp,1 + 5mp,5 = p5 ⇒ mp,5 = 1 5(p5 − p), mp,1+2mp,2+3mp,3+6mp,6 = p6 ⇒ mp,6 = 1 6(p6−p3−p2+p) ... Frobeniův automorfismus Věta 9. Nechť konečné těleso K charakteristiky p má pm prvků. Pak zobrazení ϕ : K → K, určené předpisem ϕ(a) = ap pro každé a ∈ K, je izomorfismus okruhů, je to tedy automorfismus tělesa K. Důkaz. Zřejmě ϕ(1) = 1. Pro každé a, b ∈ K je ϕ(ab) = (ab)p = apbp = ϕ(a)ϕ(b), ϕ(a + b) = (a + b)p = ap + bp = ϕ(a) + ϕ(b), neboť umocňujeme v komutativním okruhu na prvočíselnou charakteristiku. Je tedy ϕ homomorfismus okruhů. Protože jde z tělesa do tělesa, je injektivní. Protože je mezi konečnými množinami o stejném počtu prvků, je i surjektivní. Definice. Izomorfismus ϕ se nazývá Frobeniův automorfismus. Poznámka. Množina všech automorfismů tělesa K tvoří grupu vzhledem k operaci skládání. V této grupě má Frobeniův automorfismus ϕ řád m. Indukcí vůči k dostaneme ϕk(a) = apk . Věta 2 zaručí ϕm = idK , podle věty 3 pro libovolné d | m je {a ∈ T; ϕd (a) = a} podtěleso tělesa T o pd prvcích. Je možné dokázat, že ϕ je generátor grupy všech automorfismů tělesa K. Grupa automorfismů konečného tělesa Věta 10. Nechť konečné těleso K charakteristiky p má pm prvků. Pak grupa všech automorfismů tělesa K je cyklická grupa řádu m, generovaná Frobeniovým automorfismem. Důkaz. Z předchozí poznámky víme, že Frobeniův automorfismus generuje v grupě všech automorfismů tělesa K cyklickou podgrupu řádu m. Stačí tedy ukázat, že automorfismů tělesa K je nejvýše m. Podle věty 1 je K = Zp(c), přičemž minimální polynom f prvku c nad Zp má stupeň m. Ukážeme, že libovolný automorfismus ψ : K → K je jednoznačně určen svou hodnotou na prvku c, označme d = ψ(c). Platí K = Zp(c) = {am−1cm−1 + am−2cm−2 + · · · + a1c + a0; a0, a1, . . . , am−1 ∈ Zp}. Libovolný prvek a ∈ Zp je součtem několika jedniček, proto ψ(a) = a, tedy ψ(am−1cm−1 + am−2cm−2 + · · · + a1c + a0) = am−1dm−1 + am−2dm−2 + · · · + a1d + a0. Podobně f (d) = f (ψ(c)) = ψ(f (c)) = ψ(0) = 0, tedy d je kořen polynomu f . Ovšem polynom v tělese nemůže mít kořenů více než je jeho stupeň.