Ciało skończone

Ciało skończone lub ciało Galois – ciało skończonego rzędu, tj. o skończonej liczbie elementów; druga z nazw pochodzi od nazwiska Évariste’a Galois, który znacząco przyczynił się do rozwoju badań nad ciałami skończonymi (zob. Rys historyczny).

Galois wskazał ich zastosowanie w tzw. teorii Galois dającej m.in. definitywną odpowiedź na pytania o rozstrzygnięcie możliwości wykonania klasycznych konstrukcji w geometrii euklidesowej czy też zgrabnie uzasadniającej brak ogólnych wzorów na pierwiastki wielomianów wyższych stopni.

W artykule za naturalne uważa się dodatnie liczby całkowite, ciało proste o $p$ elementach (tzn. rzędu $p,$ gdzie $p$ jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli $\mathbf {F} _{p}$ oraz $\mathbb {Z} /(p);$ inną stosowaną notacją jest $\mathrm {GF} (p)$ (od ang. Galois field, ciało Galois).

Konstrukcja i własności[edytuj | edytuj kod]

Zobacz też: wielomian i pierścień wielomianów.

Niech $p$ będzie liczbą pierwszą, a $\pi$ będzie unormowanym (monicznym) wielomianem nierozkładalnym stopnia $n$ należącym do $\mathbf {F} _{p}[x]$ (tj. zmiennej $x$ o współczynnikach z ciała $\mathbf {F} _{p}$ ). Pierścień $\mathbf {F} _{p}[x]/(\pi )$ (pierścień ilorazowy $\mathbf {F} _{p}[x]$ przez ideał główny generowany przez $\pi ,$ który jest ideałem maksymalnym, co wynika z nierozkładalności i unormowania $\pi$ ) jest wtedy ciałem (reszt) rzędu $p^{n}$ ^[a]. Każde ciało skończone ma rząd wyrażający się naturalną potęgą liczby pierwszej^[b], a ponadto jest izomorficzne z $\mathbf {F} _{p}[x]/(\pi )$ dla pewnej liczby pierwszej $p$ i unormowanego wielomianu nierozkładalnego $\pi$ należącego do $\mathbf {F} _{p}[x]$ (grupa multiplikatywna ciał skończonych jest cykliczna^[c])^[d]^[e].

Dowolne ciało skończone można opisać jako ciało rozkładu wielomianu wyłącznie w zależności od rzędu ciała: ciało skończone o rzędzie $p^{n}$ będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu $x^{p^{n}}-x$ nad ciałem $\mathbf {F} _{p}$ ^[f]; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne^[g]^[h]. Wychodząc stąd, można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej^[i]. Dla dowolnej liczby pierwszej $p$ i naturalnej liczby $n$ istnieje unormowany wielomian nierozkładalny stopnia $n$ należący do $\mathbf {F} _{p}[x]$ ^[j]. Podciała $\mathbf {F} _{p^{n}}$ są rzędu $p^{d},$ gdzie $d|n,$ przy czym istnieje jedno i tylko jedno takie ciało dla każdego $d$ ^[k].

Zbiór pierwiastków wielomianu $x^{p^{n}}-x$ zawiera wszystkie elementy $\mathbf {F} _{p^{n}},$ zatem ciało to jest ciałem rozkładu tego wielomianu rozdzielczego nad ciałem $\mathbf {F} _{p}.$ Stąd ciało $\mathbf {F} _{p^{n}}/\mathbf {F} _{p}$ jest rozszerzeniem Galois – zasadniczą cechą ciał skończonych jest to, iż grupa Galois $\mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p})$ jest cykliczna i ma kanoniczny generator w postaci endomorfizmu Frobeniusa $\varphi _{p}\colon t\mapsto t^{p}$ ^[l]. Jeśli $\pi \in \mathbf {F} _{q}[x]$ jest wielomianem nierozkładalnym stopnia $d$ i ma pierwiastek $\alpha$ w pewnym rozszerzeniu ciała $\mathbf {F} _{q},$ to jego pierwiastki tworzą zbiór złożony z elementów $\alpha ,\alpha ^{p},\alpha ^{p^{2}},\dots ,\alpha ^{p^{d-1}}$ ^[m].

Powyższe twierdzenia można uogólnić, zastępując ciało $\mathbf {F} _{p}$ rzędu wyrażającego się pewną liczbą pierwszą $p$ ogólnym ciałem $\mathbf {F} _{q}$ rzędu $q=p^{n},$ wykorzystując obserwację, iż dla każdego $a\in \mathbf {F} _{q}$ zachodzi $a^{q}=a,$ zatem rolę endomorfizmu Frobeniusa $x\mapsto x^{p}$ dla skończonych rozszerzeń $\mathbf {F} _{p}$ przejmuje odwzorowanie $x\mapsto x^{q}$ dla skończonych rozszerzeń $\mathbf {F} _{q}$ ^[n].

Ciała skończone nie są algebraicznie domknięte^[o] (dla każdego jednak ciała istnieje ciało algebraicznie domknięte je zawierające). Twierdzenie Wedderburna mówi, że każdy skończony pierścień całkowity (w szczególności: pierścień z dzieleniem) jest przemienny, a więc jest ciałem (skończonym); teza zachodzi również dla pierścieni alternatywnych, czyli przy zrezygnowaniu z założenia łączności pierścienia na rzecz jego alternatywności, o czym mówi twierdzenie Artina-Zorna.

Przykłady[edytuj | edytuj kod]

Pierścień $\mathbb {Z} /7\mathbb {Z}$ tworzy ciało 7-elementowe; jego elementami są ideały $0\mathbb {Z} ,\dots ,6\mathbb {Z}$ z naturalnie określonymi działaniami (zob. pierścień ilorazowy). Innym ciałem 7-elementowym jest pierścień $\mathbb {Z} _{7}$ o elementach $0,\dots ,6$ z działaniami arytmetyki modularnej; ciało to ma tę postać, co $\mathbb {Z} _{7}[x]/(x)=\mathbf {F} _{7}[x]/(x).$ W gruncie rzeczy wszystkie ciała o 7 elementach mają tę samą strukturę. Pierścień $\mathbb {Z} _{4}$ nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera 2; skoro $2\cdot 2=0,$ to 2 jest niezerowym elementem nieodwracalnym^[p] (a więc przeczy definicji ciała, w którym każdy niezerowy element jest odwracalny). Tabliczki działań dodawania i mnożenia w jedynym (z dokładnością do izomorfizmu) 4-elementowym ciele $\mathbf {F} _{2}[x]/(x^{2}+x+1)$ (wielomian $x^{2}+x+1$ jest jedynym nierozkładalnym wielomianem drugiego stopnia nad $\mathbf {F} _{2}$ ) przedstawiono niżej:

{\begin{array}{c|cccc}+&0&1&x&x+1\\\hline 0&0&1&x&x+1\\1&1&0&x+1&x\\x&x&x+1&0&1\\x+1&x+1&x&1&0\end{array}}\qquad {\begin{array}{c|cccc}\cdot &0&1&x&x+1\\\hline 0&0&0&0&0\\1&0&1&x&x+1\\x&0&x&x+1&1\\x+1&0&x+1&1&x\end{array}}

Odpowiednio 8- i 9-elementowe pierścienie $\mathbb {Z} /2^{3}\mathbb {Z}$ i $\mathbb {Z} /3^{2}\mathbb {Z}$ nie są poprawnymi konstrukcjami ciał – pierścień $\mathbb {Z} /m\mathbb {Z}$ jest ciałem wyłącznie wtedy, gdy $m$ jest liczbą pierwszą – niemniej ciała skończone tych rzędów istnieją: ciałami rzędu 8 są np. $\mathbf {F} _{2}[x]/(x^{3}+x+1)$ oraz $\mathbf {F} _{2}[x]/(x^{3}+x^{2}+1),$ a przykładami ciał rzędu 9 są np. $\mathbf {F} _{3}[x]/(x^{2}+1),$ bądź $\mathbf {F} _{3}[x]/(x^{2}+x+2)$ albo $\mathbf {F} _{3}[x]/(x^{2}+2x+2)$ – są to wszystkie ciała postaci $\mathbf {F} _{p}[x]/(\pi )$ dla unormowanego wielomianu $\pi \in \mathbf {F} _{p}[x]$ dla $p=3$ i $n=\deg \pi =2,$ czyli rzędu $p^{n}=9;$ innym ciałem rzędu 9 jest $\mathbb {Z} [i]/(3),$ które jest izomorficzne z $\mathbf {F} _{3}[x]/(x^{2}+1),$ a nawet wszystkimi innymi ciałami rzędu 9. Wielomian $x^{3}-2$ jest nierozkładalny w $\mathbf {F} _{7}[x],$ zatem $\mathbf {F} _{7}[x]/(x^{3}-2)$ jest ciałem rzędu $7^{3}=343.$

Zbiór niezerowych elementów ciała $\mathbf {F} _{3}[x]/(x^{2}+1)$ tworzy grupę (cykliczną) rzędu 8; element $x$ nie generuje tej grupy – jego kolejnymi potęgami są $x,\ x^{2}=-1=2,\ x^{3}=2x,\ x^{4}=2x^{2}=-2=1,$ jednakże element $x+1$ jest jej generatorem – jego kolejne potęgi to $x+1,\ 2x,\ 2x+1,\ 2,\ 2x+2,\ x,\ x+2,\ 1$ (w pozostałych ciałach rzędu 9 w „modelu wielomianowym”, generatorem grupy multiplikatywnej jest $x$ ).

Wielomian $T^{3}+T^{2}+1$ jest nierozkładalny w $\mathbf {F} _{2}[x];$ jednym z jego pierwiastków w ciele $F=\mathbf {F} _{2}[x]/(x^{3}+x^{2}+1)$ jest element $x,$ dwoma pozostałymi są $x^{2},\ x^{4}.$ Ponieważ $x^{3}+x^{2}+1=0$ w $F,$ to $x^{3}=x^{2}+1$ (gdyż $-1=1$ ), zatem $x^{4}=x^{3}+x=(x^{2}+1)+x=x^{2}+x+1,$ skąd wynika, że pierwiastki $T^{3}+T^{2}+1=0$ w $F$ można zapisać jako $x,\ x^{2},\ x^{2}+x+1.$ Element $x+1$ jest jednym z pierwiastków $T^{3}+T+1$ w $F;$ dwoma pozostałymi są $(x+1)^{2}=x^{2}+1$ oraz $(x+1)^{4}=(x^{2}+1)^{2}=x^{4}+1=(x^{2}+x+1)+1=x^{2}+x.$

Element $x^{2}+x+2$ ciała $\mathbf {F} _{7}[x]/(x^{3}-2)$ ma wielomian minimalny $T^{3}+T^{2}+6T+5$ nad $\mathbf {F} _{7}.$ Pozostałymi dwoma pierwiastkami tego wielomianu są nad $(x^{2}+x+2)^{7}$ oraz $(x^{2}+x+2)^{49};$ potęgi tych elementów można zredukować, korzystając z tożsamości $x^{3}=2,$ mianowicie: $(x^{2}+x+2)^{7}=2x^{2}+4x+2$ oraz $(x^{2}+x+2)^{49}=4x^{2}+2x+2.$

Rys historyczny[edytuj | edytuj kod]

Ciała o rzędzie wyrażającym się liczbą pierwszą, $\mathbb {Z} /p\mathbb {Z} ,$ były przedmiotem badań wielu pionierów teorii liczb, m.in. Pierre’a de Fermata, Leonharda Eulera, Josepha Louisa Lagrange’a, Adriena-Marie Legendre’a, czy Carla Friedricha Gaussa. Pierwszym matematykiem piszącym o innych ciałach skończonych był Évariste Galois, który przedstawił o nich pracę w 1830 roku (ciałami o rzędach niewyrażających się liczbami pierwszymi zajmował się wcześniej Gauss, co odkryto jednak dopiero po jego śmierci w 1855 roku, wydając jego prace na ten temat w 1863 roku, lecz przeszły one bez większego echa).

Galois konstruował ciała skończone jako rozszerzenia pojedyncze $\mathbf {F} _{p}(\alpha ),$ gdzie $\alpha$ jest pierwiastkiem wielomianu nierozkładalnego $\pi$ zmiennej $x$ nad ciałem $\mathbf {F} _{p}$ (tzn. należącego do $\mathbf {F} _{p}[x]$ ); jest to równoważne rozpatrywaniu $\mathbf {F} _{p}[x]/(\pi ).$ Galois nie pokazał, że w $\mathbf {F} _{p}[x]$ istnieje wielomian nierozkładalny dowolnego stopnia.

W 1893 roku na Międzynarodowym Kongresie Matematycznym w Chicago Eliakim Hastings Moore dowiódł, że każde ciało skończone jest izomorficzne z ciałem postaci $\mathbf {F} _{p}[x]/(\pi );$ twierdzenie opatrzył komentarzem „Nigdzie indziej nie widziałem sformułowania tego interesującego wyniku”^[1]. Moore był pierwszą osobą, która użyła angielskiego słowa field (dosł. „pole”) w sensie algebraicznym, choć traktował je jako synonim niemieckiego endlicher Körper (dosł. „ciało skończone”)^[2]. Każde skonstruowane ciało postaci $\mathbf {F} _{p}[x]/(\pi ).$ nazywał on ciałem Galois, były więc one dla niego konkretnymi modelami wszystkich ciał skończonych. W informatyce wyrażenie Moore’a „ciało Galois” jest synonimem ciała skończonego, a stosowana przez niego notacja $\mathrm {GF} (q)$ (od ang. Galois field) stosowana jest często zamiast $\mathbf {F} _{q}.$

Uwagi[edytuj | edytuj kod]

↑ Warstwy modulo $\pi$ są reprezentowane za pomocą reszt $c_{0}+c_{1}x+\ldots +c_{n-1}x^{n-1},$ gdzie $c_{i}\in \mathbf {F} _{p},$ przy czym jest ich $p^{n}.$ Ponieważ $\pi$ jest nierozkładalny, to korzystając z tego samego argumentu, co przy dowodzie, iż $\mathbb {Z} /(m)$ jest ciałem dla $m$ będącego liczbą pierwszą, pierścień $\mathbf {F} _{p}[x]/(\pi )$ jest ciałem.
↑ Charakterystyka ciała skończonego $F$ jest liczbą pierwszą, gdyż jądro homomorfizmu $\mathbb {Z} \to F$ jest niezerowe (z uwagi na nieskończony rząd $\mathbb {Z}$ i skończony $F$ ) i jest postaci $(m)=m\mathbb {Z}$ dla pewnej liczby całkowitej $m>0,$ zatem $\mathbb {Z} /(m)$ zanurza się w $F$ jako podpierścień; każdy podpierścień ciała jest dziedziną, zatem $m$ musi być liczbą pierwszą, oznaczaną dalej $p.$ Skoro $\mathbb {Z} /(p)\hookrightarrow F$ jest zanurzeniem, to $F$ można traktować jako przestrzeń liniową nad $\mathbb {Z} /(p),$ skończonego wymiaru $n=[F\colon \mathbb {Z} /(p)]:=\dim _{\mathbb {Z} /(p)}(F)$ (gdyż $F$ jest zbiorem skończonym). Każdy element $F$ można wtedy zapisać jednoznacznie w bazie $(e_{i})$ nad $\mathbb {Z} /(p)$ jako kombinację liniową $c_{1}e_{1}+\ldots +c_{n}e_{n}$ dla $c_{i}\in \mathbb {Z} /(p);$ liczba tych kombinacji wynosi $p^{n}.$
↑ Lemat: Jeśli ciało $F$ jest skończone, to jego grupa multiplikatywna $F^{*}$ jest cykliczna.
Dowód lematu: Niech $k$ oznacza największy rząd elementu w grupie $F^{*};$ z teorii skończonych grup abelowych wynika, że rząd dowolnego jej elementu dzieli rząd maksymalny, zatem dla dowolnego $t\in F^{*}$ zachodzi $t^{k}=1.$ Stąd wszystkie elementy grupy $F^{*}$ są pierwiastkami $x^{k}-1.$
Niech $q=|F|;$ liczba pierwiastków wielomianu jest równa co najwyżej stopniowi wielomianu, a ponieważ $x^{k}-1$ ma $q-1$ pierwiastków w $F,$ to $q-1\leqslant k.$ Skoro $k$ jest rzędem elementu w $F^{*}$ będącej grupą rzędu $q-1,$ to $k|(q-1),$ a więc $k=q-1,$ skąd wynika, że w $F$ istnieją elementy rzędu $q-1,$ co oznacza, iż $F^{*}$ jest cykliczna.
↑ Niech $F$ będzie ciałem skończonym o $p^{n}$ elementach (z twierdzenia wyżej) i dane będzie zanurzenie ciał $\mathbf {F} _{p}\hookrightarrow F.$ Niech $\gamma$ będzie generatorem grupy cyklicznej $F^{*}$ (z powyższego lematu). Ewaluacja $\mathrm {ev} _{\gamma }\colon \mathbf {F} _{p}[x]\to F$ wielomianu dla elementu $\gamma$ dana wzorem $\mathrm {ev} _{\gamma }(f)=f(\gamma )$ jest homomorfizmem pierścieni. Ponieważ każdy element $F$ jest zerem lub potęgą $\gamma$ (tzn. $0=\mathrm {ev} _{\gamma }(0)$ oraz $\gamma ^{r}=\mathrm {ev} _{\gamma }(x^{r})$ dla dowolnego $r\geqslant 0$ ), to $\mathrm {ev} _{\gamma }$ jest epimorfizmem („na”), zatem $\mathbf {F} _{p}[x]/\ker \mathrm {ev} _{\gamma }\simeq F.$ Skoro jądro $\mathrm {ev} _{\gamma }$ jest ideałem maksymalnym w $\mathbf {F} _{p}[x],$ to musi być ono równe $(\pi )$ dla pewnego unormowanego wielomianu nierozkładalnego $\pi$ należącego do $\mathbf {F} _{p}[x].$
↑ Twierdzenie to nie zapewnia o istnieniu ciał rzędów wyrażających się za pomocą wszystkich potęg liczb pierwszych; mówi jedynie, iż jeśli istnieje ciało rzędu $p^{n},$ to jest ono izomorficzne z $\mathbf {F} _{p}[x]/(\pi );$ odpowiedni dowód istnienia przedstawiono dalej.
↑ Niech $F$ będzie ciałem rzędu $p^{n};$ z dowodu twierdzenia o rzędzie ciała skończonego wynika, że $F$ zawiera podciało rzędu $p$ izomorficzne z $\mathbf {F} _{p},$ jest nim podpierścień $F$ generowany przez 1. Dla każdego $t\in F$ zachodzi $t^{p^{n}}=t;$ otóż jeśli $t\neq 0,$ to $t^{p^{n}-1}=1,$ gdyż $F^{*}=F\setminus \{0\}$ jest grupą multiplikatywną rzędu $p^{n}-1$ i wtedy tożsamość wynika z obustronnego pomnożenia równania przez $t,$ co jest również prawdą w przypadku, gdy $t=0.$ Każdy element $F$ jest pierwiastkiem $x^{p^{n}}-x,$ zatem $F$ jest ciałem rozkładu tego wielomianu nad ciałem $\mathbf {F} _{p}.$
↑ Wynika to wprost z izomorficzności ciał rozkładu ustalonego wielomianu nad $\mathbf {F} _{p}.$
↑ Analogiczne twierdzenie dla skończonych grup lub pierścieni jest fałszywe: tak $\mathbb {Z} /(4),$ jak i $\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ są rzędu 4, lecz są nieizomorficzne jako grupy addytywne (odpowiednio grupa cykliczna i grupa czwórkowa Kleina) i pierścienie przemienne.
↑ Twierdzenie: Dla dowolnych liczb pierwszej $p$ i naturalnej $n$ istnieje ciało rzędu $p^{n}.$
Dowód: Niech $F$ będzie rozszerzeniem ciała $\mathbf {F} _{p}$ nad którym wielomian $x^{p^{n}}-x$ rozkłada się na czynniki liniowe (tzn. pewnym rozszerzeniem ciała rozkładu tego wielomianu; istnienie tego rodzaju rozszerzenia wynika z ogólnej teorii ciał). Pierwiastki wspomnianego wielomianu tworzą zbiór $S=\left\{t\in F\colon t^{p^{n}}=t\right\}$ o $p^{n}$ elementach, gdyż wielomian $x^{p^{n}}-x$ jest rozdzielczy: $\left(x^{p^{n}}-x\right)'=p^{n}x^{(p^{n}-1)}-1=-1,$ gdyż $p=0$ w $F,$ zatem $x^{p^{n}}-x$ i jego pochodna nie mają wspólnych pierwiastków; wielomian ten rozkłada się na czynniki liniowe nad $F$ i jest stopnia $p^{n},$ zatem ma $p^{n}$ pierwiastków w $F.$
Zbiór $S$ tworzy ciało – wynika to wprost z własności endomorfizmu Frobeniusa $x\mapsto x^{p}.$ Mianowicie: zamkniętość ze względu na mnożenie i odwracanie (niezerowych rozwiązań) jest trywialna, z kolei zamkniętość ze względu na dodawanie i branie elementów przeciwnych wynika stąd, iż $S$ jest grupą addytywną: skoro $p=0$ w $F,$ to dla dowolnych elementów $a,b\in F$ zachodzi równość $(a+b)^{p}=a^{p}+b^{p}$ (wyrazy mieszane rozwinięcia dwumianu Newtona $(a+b)^{p}$ mają współczynniki ${\tbinom {p}{k}}$ będące wielokrotnościami $p,$ zatem są równe zeru), co dowodzi addytywności endomorfizmu Frobeniusa, skąd wynika także addytywność jego $n$ -tej iteracji $x\mapsto x^{p^{n}}.$ Zbiór $S$ jest grupą ze względu na dodawanie jako zbiór punktów stałych tej właśnie funkcji addytywnej.
↑ Z powyższego twierdzenia wynika istnienie abstrakcyjnego ciała rzędu $p^{n},$ a z twierdzenia wyżej musi być ono izomorficzne z ciałem $\mathbf {F} _{p}[x]/(\pi )$ dla pewnego $\pi \in \mathbf {F} _{p}[x].$
↑ Niech $F$ będzie ciałem spełniającym $\mathbf {F} _{p}\subseteq F\subseteq \mathbf {F} _{p^{n}}$ i niech $d=[F\colon \mathbf {F} _{p}]$ tak, iż $|F|=p^{d},$ a $d$ dzieli $[\mathbf {F} _{p^{n}}\colon \mathbf {F} _{p}]=n.$ Opisanie $F$ wyłącznie w zależności od $|F|$ zagwarantuje jedyność podciała tego rzędu w $\mathbf {F} _{p^{n}}.$ Skoro $F^{*}$ jest rzędu $p^{d}-1,$ to dla każdego $t\in F^{*}$ zachodzi $t^{p^{d}-1}=1,$ zatem $t^{p^{d}}=t,$ również dla $t=0.$ Wielomian $x^{p^{d}}-x$ ma co najwyżej $p^{d}$ pierwiastków w $\mathbf {F} _{p^{n}},$ a ponieważ $F$ jest zbiorem $p^{d}$ różnych pierwiastków, jest $F=\{t\in \mathbf {F} _{p^{n}}\colon t^{p^{d}}=t\};$ (zależna tylko od liczby elementów) postać tego zbioru dowodzi jego jednoznaczności. Przechodząc do dowodu, iż dla każdego $d|n$ istnieje podciało ciała $\mathbf {F} _{p^{n}}$ rzędu $p^{d}{:}$ zbiór $\{t\in \mathbf {F} _{p^{n}}\colon t^{p^{d}}=t\}$ jest ciałem na mocy tego samego argumentu, co dla zbioru $S$ w dowodzie twierdzenia o istnieniu; wykazanie, iż ma on $p^{d}$ elementów polega na wskazaniu $p^{d}-1$ niezerowych elementów w $\mathbf {F} _{p^{n}}$ spełniających $t^{p^{d}-1}=1.$ Otóż niech $\gamma$ będzie generatorem $\mathbf {F} _{p^{n}}^{*},$ czyli ma rząd $p^{n}-1;$ ponieważ $d|n,$ tj. $(p^{d}-1)$ dzieli $p^{n}-1,$ to $\alpha :=\gamma ^{(p^{n}-1)/(p^{d}-1)}$ jest rzędu $p^{d}-1.$ Wszystkie potęgi $\alpha ^{k}$ dla $0\leqslant k\leqslant p^{d}-2$ spełniają $t^{p^{d}}-1=1.$
↑ Dla dowolnego $a\in \mathbf {F} _{p}$ zachodzi $a^{p}=a,$ zatem $\mathbf {F} _{p}$ jest zbiorem punktów stałych funkcji $\varphi _{p}\colon \mathbf {F} _{p^{n}}\to \mathbf {F} _{p^{n}};$ funkcja ta jest homomorfizmem ciał i jest różnowartościowa (wszystkie homomorfizmy ciał są monomorfizmami), a także „na”, jako że $\mathbf {F} _{p^{n}}$ jest skończone (innymi słowy endomorfizm Frobeniusa jest automorfizmem). Stąd $\varphi _{p}\in \mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p}).$ Rząd tej grupy Galois wynosi $[\mathbf {F} _{p^{n}}:\mathbf {F} _{p}]=n;$ wystarczy wykazać, że $\varphi _{p}$ jest rzędu $n,$ co oznaczać będzie, iż jest generatorem tej grupy. Niech dla $r\geqslant 0$ będzie $\varphi _{p}^{r}(t)=t^{p^{r}}.$ Wówczas jeśli $\varphi _{p}^{r}$ jest elementem neutralnym tej grupy, to $t^{p^{r}}=t$ dla wszystkich $t\in \mathbf {F} _{p^{n}}.$ Wielomian $x^{p^{r}}-x$ ma co najwyżej $p^{r}$ pierwiastków, zatem $p^{n}<p^{r},$ czyli $n<r.$ Wynika stąd, iż $\varphi _{p}$ ma w $\mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p})$ rząd równy co najmniej $n;$ z drugiej strony grupa ta ma rząd co najwyżej $n,$ zatem $\varphi _{p}$ musi być także rzędu $n.$
↑ Każde skończone ciało rzędu wyrażającego się potęgą liczby pierwszej $p$ jest rozszerzeniem Galois nad $\mathbf {F} _{p}.$ W szczególności dotyczy to ciała $\mathbf {F} _{p}(\alpha ),$ a pozostałe pierwiastki $\pi$ można otrzymać z $\alpha ,$ działając na ten element grupą $\mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p}).$ Ponieważ grupa ta jest generowana przez endomorfizm Frobeniusa, to pierwiastki $\pi$ należą do zbioru $\alpha ,\alpha ^{p},\alpha ^{p^{2}},\dots$ Zbiór ten jest skończony, gdyż $\alpha ^{p^{d}}=\alpha ,$ co wynika stąd, iż $\mathbf {F} _{p}(\alpha )\simeq \mathbf {F} _{p}[x]/(\pi )$ jest rzędu $p^{d}.$ Wielomian $\pi$ jest rozdzielczy, ponieważ jego pierwiastki należą do rozszerzenia Galois $\mathbf {F} _{p}(\alpha )$ ciała $\mathbf {F} _{p},$ a skoro ma on stopień $d,$ to parami różne elementy $\alpha ,\alpha ^{p},\alpha ^{p^{2}},\dots ,\alpha ^{p^{d-1}}$ tworzą zbiór jego pierwiastków.
↑ Twierdzenie: Dla dowolnej liczby naturalnej $n$ istnieje unormowany wielomian nierozkładalny stopnia $n$ należący do $\mathbf {F} _{q}[x].$
Twierdzenie: Między $\mathbf {F} _{q}$ a $\mathbf {F} _{q^{n}}$ istnieje jedno i tylko jedno ciało rzędu $q^{d}$ dla każdego $d|n;$ jest ono postaci $\left\{t\in \mathbf {F} _{q^{n}}\colon t^{q^{d}}=t\right\}.$
Twierdzenie: Dla dowolnej liczby naturalnej $n$ ciało $\mathbf {F} _{q^{n}}/\mathbf {F} _{q}$ jest rozszerzeniem Galois, a jego grupa Galois $\mathrm {Gal} (\mathbf {F} _{q^{n}}/\mathbf {F} _{q})$ jest cykliczna, przy czym jej generatorem jest przekształcenie $\varphi _{q}\colon t\mapsto t^{q}.$
Twierdzenie: Jeśli $\pi \in \mathbf {F} _{q}[x]$ jest wielomianem nierozkładalnym stopnia $d$ i ma pierwiastek $\alpha$ w pewnym rozszerzeniu ciała $\mathbf {F} _{q},$ to zbiór elementów $\alpha ,\alpha ^{q},\alpha ^{q^{2}},\dots ,\alpha ^{q^{d-1}}$ zawiera wszystkie jego pierwiastki.
↑ Jeśli $F=\{a_{1},\dots ,a_{r}\}$ jest ciałem skończonym, to wartość wielomianu $(x-a_{1})\dots (x-a_{r})+1$ dla dowolnego elementu $x\in F$ jest równa 1 (jego funkcja wielomianowa jest stale równa 1), skąd wielomian ten nie ma pierwiastków w $F.$
↑ Jeśli (w ciele $\mathbb {Z} _{4}$ ) element $a$ byłby elementem odwrotnym do 2, to (z definicji) $2\cdot a=1;$ jednakże wtedy $2=2\cdot 1=2\cdot (2\cdot a)=(2\cdot 2)\cdot a=0\cdot a=0,$ czyli 2 nie może mieć elementu odwrotnego.

Przypisy[edytuj | edytuj kod]

↑ Moore 1893 ↓, s. 211: „This interesting result I have not seen stated elsewhere.”.
↑ Moore 1893 ↓, s. 208.

Bibliografia[edytuj | edytuj kod]

Eliakim Hastings Moore. A doubly-infinite system of simple groups. „Mathematical papers read at the International Mathematical Congress held in connection with the World’s Columbian Exposition, Chicago, 1893”, s. 208–242, 1896. Nowy Jork: Macmillan & Co.. [dostęp 2020-10-10].

Literatura dodatkowa[edytuj | edytuj kod]

Jerzy Browkin: Teoria ciał. Wyd. 1. T. 49. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, seria: Biblioteka Matematyczna.
Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.

Linki zewnętrzne[edytuj | edytuj kod]

Eric W.E.W. Weisstein Eric W.E.W., Finite Field, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).

[1] Warstwy modulo $\pi$ są reprezentowane za pomocą reszt $c_{0}+c_{1}x+\ldots +c_{n-1}x^{n-1},$ gdzie $c_{i}\in \mathbf {F} _{p},$ przy czym jest ich $p^{n}.$ Ponieważ $\pi$ jest nierozkładalny, to korzystając z tego samego argumentu, co przy dowodzie, iż $\mathbb {Z} /(m)$ jest ciałem dla $m$ będącego liczbą pierwszą, pierścień $\mathbf {F} _{p}[x]/(\pi )$ jest ciałem.

[2] Charakterystyka ciała skończonego $F$ jest liczbą pierwszą, gdyż jądro homomorfizmu $\mathbb {Z} \to F$ jest niezerowe (z uwagi na nieskończony rząd $\mathbb {Z}$ i skończony $F$ ) i jest postaci $(m)=m\mathbb {Z}$ dla pewnej liczby całkowitej $m>0,$ zatem $\mathbb {Z} /(m)$ zanurza się w $F$ jako podpierścień; każdy podpierścień ciała jest dziedziną, zatem $m$ musi być liczbą pierwszą, oznaczaną dalej $p.$ Skoro $\mathbb {Z} /(p)\hookrightarrow F$ jest zanurzeniem, to $F$ można traktować jako przestrzeń liniową nad $\mathbb {Z} /(p),$ skończonego wymiaru $n=[F\colon \mathbb {Z} /(p)]:=\dim _{\mathbb {Z} /(p)}(F)$ (gdyż $F$ jest zbiorem skończonym). Każdy element $F$ można wtedy zapisać jednoznacznie w bazie $(e_{i})$ nad $\mathbb {Z} /(p)$ jako kombinację liniową $c_{1}e_{1}+\ldots +c_{n}e_{n}$ dla $c_{i}\in \mathbb {Z} /(p);$ liczba tych kombinacji wynosi $p^{n}.$

[3] Lemat: Jeśli ciało $F$ jest skończone, to jego grupa multiplikatywna $F^{*}$ jest cykliczna.
Dowód lematu: Niech $k$ oznacza największy rząd elementu w grupie $F^{*};$ z teorii skończonych grup abelowych wynika, że rząd dowolnego jej elementu dzieli rząd maksymalny, zatem dla dowolnego $t\in F^{*}$ zachodzi $t^{k}=1.$ Stąd wszystkie elementy grupy $F^{*}$ są pierwiastkami $x^{k}-1.$
Niech $q=|F|;$ liczba pierwiastków wielomianu jest równa co najwyżej stopniowi wielomianu, a ponieważ $x^{k}-1$ ma $q-1$ pierwiastków w $F,$ to $q-1\leqslant k.$ Skoro $k$ jest rzędem elementu w $F^{*}$ będącej grupą rzędu $q-1,$ to $k|(q-1),$ a więc $k=q-1,$ skąd wynika, że w $F$ istnieją elementy rzędu $q-1,$ co oznacza, iż $F^{*}$ jest cykliczna.

[4] Niech $F$ będzie ciałem skończonym o $p^{n}$ elementach (z twierdzenia wyżej) i dane będzie zanurzenie ciał $\mathbf {F} _{p}\hookrightarrow F.$ Niech $\gamma$ będzie generatorem grupy cyklicznej $F^{*}$ (z powyższego lematu). Ewaluacja $\mathrm {ev} _{\gamma }\colon \mathbf {F} _{p}[x]\to F$ wielomianu dla elementu $\gamma$ dana wzorem $\mathrm {ev} _{\gamma }(f)=f(\gamma )$ jest homomorfizmem pierścieni. Ponieważ każdy element $F$ jest zerem lub potęgą $\gamma$ (tzn. $0=\mathrm {ev} _{\gamma }(0)$ oraz $\gamma ^{r}=\mathrm {ev} _{\gamma }(x^{r})$ dla dowolnego $r\geqslant 0$ ), to $\mathrm {ev} _{\gamma }$ jest epimorfizmem („na”), zatem $\mathbf {F} _{p}[x]/\ker \mathrm {ev} _{\gamma }\simeq F.$ Skoro jądro $\mathrm {ev} _{\gamma }$ jest ideałem maksymalnym w $\mathbf {F} _{p}[x],$ to musi być ono równe $(\pi )$ dla pewnego unormowanego wielomianu nierozkładalnego $\pi$ należącego do $\mathbf {F} _{p}[x].$

[5] Twierdzenie to nie zapewnia o istnieniu ciał rzędów wyrażających się za pomocą wszystkich potęg liczb pierwszych; mówi jedynie, iż jeśli istnieje ciało rzędu $p^{n},$ to jest ono izomorficzne z $\mathbf {F} _{p}[x]/(\pi );$ odpowiedni dowód istnienia przedstawiono dalej.

[6] Niech $F$ będzie ciałem rzędu $p^{n};$ z dowodu twierdzenia o rzędzie ciała skończonego wynika, że $F$ zawiera podciało rzędu $p$ izomorficzne z $\mathbf {F} _{p},$ jest nim podpierścień $F$ generowany przez 1. Dla każdego $t\in F$ zachodzi $t^{p^{n}}=t;$ otóż jeśli $t\neq 0,$ to $t^{p^{n}-1}=1,$ gdyż $F^{*}=F\setminus \{0\}$ jest grupą multiplikatywną rzędu $p^{n}-1$ i wtedy tożsamość wynika z obustronnego pomnożenia równania przez $t,$ co jest również prawdą w przypadku, gdy $t=0.$ Każdy element $F$ jest pierwiastkiem $x^{p^{n}}-x,$ zatem $F$ jest ciałem rozkładu tego wielomianu nad ciałem $\mathbf {F} _{p}.$

[7] Wynika to wprost z izomorficzności ciał rozkładu ustalonego wielomianu nad $\mathbf {F} _{p}.$

[8] Analogiczne twierdzenie dla skończonych grup lub pierścieni jest fałszywe: tak $\mathbb {Z} /(4),$ jak i $\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ są rzędu 4, lecz są nieizomorficzne jako grupy addytywne (odpowiednio grupa cykliczna i grupa czwórkowa Kleina) i pierścienie przemienne.

[9] Twierdzenie: Dla dowolnych liczb pierwszej $p$ i naturalnej $n$ istnieje ciało rzędu $p^{n}.$
Dowód: Niech $F$ będzie rozszerzeniem ciała $\mathbf {F} _{p}$ nad którym wielomian $x^{p^{n}}-x$ rozkłada się na czynniki liniowe (tzn. pewnym rozszerzeniem ciała rozkładu tego wielomianu; istnienie tego rodzaju rozszerzenia wynika z ogólnej teorii ciał). Pierwiastki wspomnianego wielomianu tworzą zbiór $S=\left\{t\in F\colon t^{p^{n}}=t\right\}$ o $p^{n}$ elementach, gdyż wielomian $x^{p^{n}}-x$ jest rozdzielczy: $\left(x^{p^{n}}-x\right)'=p^{n}x^{(p^{n}-1)}-1=-1,$ gdyż $p=0$ w $F,$ zatem $x^{p^{n}}-x$ i jego pochodna nie mają wspólnych pierwiastków; wielomian ten rozkłada się na czynniki liniowe nad $F$ i jest stopnia $p^{n},$ zatem ma $p^{n}$ pierwiastków w $F.$
Zbiór $S$ tworzy ciało – wynika to wprost z własności endomorfizmu Frobeniusa $x\mapsto x^{p}.$ Mianowicie: zamkniętość ze względu na mnożenie i odwracanie (niezerowych rozwiązań) jest trywialna, z kolei zamkniętość ze względu na dodawanie i branie elementów przeciwnych wynika stąd, iż $S$ jest grupą addytywną: skoro $p=0$ w $F,$ to dla dowolnych elementów $a,b\in F$ zachodzi równość $(a+b)^{p}=a^{p}+b^{p}$ (wyrazy mieszane rozwinięcia dwumianu Newtona $(a+b)^{p}$ mają współczynniki ${\tbinom {p}{k}}$ będące wielokrotnościami $p,$ zatem są równe zeru), co dowodzi addytywności endomorfizmu Frobeniusa, skąd wynika także addytywność jego $n$ -tej iteracji $x\mapsto x^{p^{n}}.$ Zbiór $S$ jest grupą ze względu na dodawanie jako zbiór punktów stałych tej właśnie funkcji addytywnej.

[10] Z powyższego twierdzenia wynika istnienie abstrakcyjnego ciała rzędu $p^{n},$ a z twierdzenia wyżej musi być ono izomorficzne z ciałem $\mathbf {F} _{p}[x]/(\pi )$ dla pewnego $\pi \in \mathbf {F} _{p}[x].$

[11] Niech $F$ będzie ciałem spełniającym $\mathbf {F} _{p}\subseteq F\subseteq \mathbf {F} _{p^{n}}$ i niech $d=[F\colon \mathbf {F} _{p}]$ tak, iż $|F|=p^{d},$ a $d$ dzieli $[\mathbf {F} _{p^{n}}\colon \mathbf {F} _{p}]=n.$ Opisanie $F$ wyłącznie w zależności od $|F|$ zagwarantuje jedyność podciała tego rzędu w $\mathbf {F} _{p^{n}}.$ Skoro $F^{*}$ jest rzędu $p^{d}-1,$ to dla każdego $t\in F^{*}$ zachodzi $t^{p^{d}-1}=1,$ zatem $t^{p^{d}}=t,$ również dla $t=0.$ Wielomian $x^{p^{d}}-x$ ma co najwyżej $p^{d}$ pierwiastków w $\mathbf {F} _{p^{n}},$ a ponieważ $F$ jest zbiorem $p^{d}$ różnych pierwiastków, jest $F=\{t\in \mathbf {F} _{p^{n}}\colon t^{p^{d}}=t\};$ (zależna tylko od liczby elementów) postać tego zbioru dowodzi jego jednoznaczności. Przechodząc do dowodu, iż dla każdego $d|n$ istnieje podciało ciała $\mathbf {F} _{p^{n}}$ rzędu $p^{d}{:}$ zbiór $\{t\in \mathbf {F} _{p^{n}}\colon t^{p^{d}}=t\}$ jest ciałem na mocy tego samego argumentu, co dla zbioru $S$ w dowodzie twierdzenia o istnieniu; wykazanie, iż ma on $p^{d}$ elementów polega na wskazaniu $p^{d}-1$ niezerowych elementów w $\mathbf {F} _{p^{n}}$ spełniających $t^{p^{d}-1}=1.$ Otóż niech $\gamma$ będzie generatorem $\mathbf {F} _{p^{n}}^{*},$ czyli ma rząd $p^{n}-1;$ ponieważ $d|n,$ tj. $(p^{d}-1)$ dzieli $p^{n}-1,$ to $\alpha :=\gamma ^{(p^{n}-1)/(p^{d}-1)}$ jest rzędu $p^{d}-1.$ Wszystkie potęgi $\alpha ^{k}$ dla $0\leqslant k\leqslant p^{d}-2$ spełniają $t^{p^{d}}-1=1.$

[12] Dla dowolnego $a\in \mathbf {F} _{p}$ zachodzi $a^{p}=a,$ zatem $\mathbf {F} _{p}$ jest zbiorem punktów stałych funkcji $\varphi _{p}\colon \mathbf {F} _{p^{n}}\to \mathbf {F} _{p^{n}};$ funkcja ta jest homomorfizmem ciał i jest różnowartościowa (wszystkie homomorfizmy ciał są monomorfizmami), a także „na”, jako że $\mathbf {F} _{p^{n}}$ jest skończone (innymi słowy endomorfizm Frobeniusa jest automorfizmem). Stąd $\varphi _{p}\in \mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p}).$ Rząd tej grupy Galois wynosi $[\mathbf {F} _{p^{n}}:\mathbf {F} _{p}]=n;$ wystarczy wykazać, że $\varphi _{p}$ jest rzędu $n,$ co oznaczać będzie, iż jest generatorem tej grupy. Niech dla $r\geqslant 0$ będzie $\varphi _{p}^{r}(t)=t^{p^{r}}.$ Wówczas jeśli $\varphi _{p}^{r}$ jest elementem neutralnym tej grupy, to $t^{p^{r}}=t$ dla wszystkich $t\in \mathbf {F} _{p^{n}}.$ Wielomian $x^{p^{r}}-x$ ma co najwyżej $p^{r}$ pierwiastków, zatem $p^{n}<p^{r},$ czyli $n<r.$ Wynika stąd, iż $\varphi _{p}$ ma w $\mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p})$ rząd równy co najmniej $n;$ z drugiej strony grupa ta ma rząd co najwyżej $n,$ zatem $\varphi _{p}$ musi być także rzędu $n.$

[13] Każde skończone ciało rzędu wyrażającego się potęgą liczby pierwszej $p$ jest rozszerzeniem Galois nad $\mathbf {F} _{p}.$ W szczególności dotyczy to ciała $\mathbf {F} _{p}(\alpha ),$ a pozostałe pierwiastki $\pi$ można otrzymać z $\alpha ,$ działając na ten element grupą $\mathrm {Gal} (\mathbf {F} _{p^{n}}/\mathbf {F} _{p}).$ Ponieważ grupa ta jest generowana przez endomorfizm Frobeniusa, to pierwiastki $\pi$ należą do zbioru $\alpha ,\alpha ^{p},\alpha ^{p^{2}},\dots$ Zbiór ten jest skończony, gdyż $\alpha ^{p^{d}}=\alpha ,$ co wynika stąd, iż $\mathbf {F} _{p}(\alpha )\simeq \mathbf {F} _{p}[x]/(\pi )$ jest rzędu $p^{d}.$ Wielomian $\pi$ jest rozdzielczy, ponieważ jego pierwiastki należą do rozszerzenia Galois $\mathbf {F} _{p}(\alpha )$ ciała $\mathbf {F} _{p},$ a skoro ma on stopień $d,$ to parami różne elementy $\alpha ,\alpha ^{p},\alpha ^{p^{2}},\dots ,\alpha ^{p^{d-1}}$ tworzą zbiór jego pierwiastków.

[14] Twierdzenie: Dla dowolnej liczby naturalnej $n$ istnieje unormowany wielomian nierozkładalny stopnia $n$ należący do $\mathbf {F} _{q}[x].$
Twierdzenie: Między $\mathbf {F} _{q}$ a $\mathbf {F} _{q^{n}}$ istnieje jedno i tylko jedno ciało rzędu $q^{d}$ dla każdego $d|n;$ jest ono postaci $\left\{t\in \mathbf {F} _{q^{n}}\colon t^{q^{d}}=t\right\}.$
Twierdzenie: Dla dowolnej liczby naturalnej $n$ ciało $\mathbf {F} _{q^{n}}/\mathbf {F} _{q}$ jest rozszerzeniem Galois, a jego grupa Galois $\mathrm {Gal} (\mathbf {F} _{q^{n}}/\mathbf {F} _{q})$ jest cykliczna, przy czym jej generatorem jest przekształcenie $\varphi _{q}\colon t\mapsto t^{q}.$
Twierdzenie: Jeśli $\pi \in \mathbf {F} _{q}[x]$ jest wielomianem nierozkładalnym stopnia $d$ i ma pierwiastek $\alpha$ w pewnym rozszerzeniu ciała $\mathbf {F} _{q},$ to zbiór elementów $\alpha ,\alpha ^{q},\alpha ^{q^{2}},\dots ,\alpha ^{q^{d-1}}$ zawiera wszystkie jego pierwiastki.

[15] Jeśli $F=\{a_{1},\dots ,a_{r}\}$ jest ciałem skończonym, to wartość wielomianu $(x-a_{1})\dots (x-a_{r})+1$ dla dowolnego elementu $x\in F$ jest równa 1 (jego funkcja wielomianowa jest stale równa 1), skąd wielomian ten nie ma pierwiastków w $F.$

[16] Jeśli (w ciele $\mathbb {Z} _{4}$ ) element $a$ byłby elementem odwrotnym do 2, to (z definicji) $2\cdot a=1;$ jednakże wtedy $2=2\cdot 1=2\cdot (2\cdot a)=(2\cdot 2)\cdot a=0\cdot a=0,$ czyli 2 nie może mieć elementu odwrotnego.

[17] Moore 1893 ↓, s. 211: „This interesting result I have not seen stated elsewhere.”.

[18] Moore 1893 ↓, s. 208.

[a]

[b]

[c]

[d]

[e]

[f]

[g]

[h]

[i]

[j]

[k]

[l]

[m]

[n]

[o]

[p]

[1]

[2]