Wracamy teraz do ciał skończonych. Jedyne ciała skończone jakie poznaliśmy do tej pory to \( (\mathbb{Z}_p,+,\cdot,0,1) \), gdzie \( p \) jest liczbą pierwszą. Czy istnieją inne ciała skończone? Jaką liczność mogą mieć inne ciała skończone? Czy wszystkie ciała liczności \( p \) są izomorficzne z ciałem \( \mathbb{Z}_p \)? Odpowiedzi na te pytania poznamy w pozostałej części wykładu.
Charakterystyka ciała \( {\bf F}=(F,+,\cdot,0,1) \) to rząd elementu \( 1 \) w grupie addytywnej \( (F,+,0) \). Oczywiście, jeśli ciało jest skończone to jego charakterystyka też jest skończona. Co więcej, ponieważ rząd elementu musi dzielić rząd grupy, to charakterystyka ciała skończonego \( {\bf F} \) dzieli \( \vert \).
Przykład
Obserwacja 6.19
Charakterystyka ciała skończonego jest liczbą pierwszą.
Dowód
Dla dowodu nie wprost załóżmy, że charakterystyka pewnego ciała jest liczbą złożoną \( n=pq \). Wtedy
\( 0=(\underbrace{1+\ldots+1}_{n\ razy}) =(\underbrace{1+\ldots+1}_{p\ razy})\cdot(\underbrace{1+\ldots+1}_{q\ razy}). \)
Ponieważ \( p,q < n \) oba czynniki prawej strony ostatniej równości są niezerowe, to są one dzielnikami zera. Sprzeczność z Obserwacją 6.2.
Obserwacja 6.20
Grupa addytywna dowolnego ciała skończonego \( {\bf F}=(F,+,\cdot,0,1) \) jest izomorficzna z \( ({\mathbf {Z}_p})^k \) dla pewnej liczby pierwszej \( p \) i \( k\geq 1 \). Zatem \( \vert=p^k \).
Dowód
Niech \( {\bf F}=(F,+,\cdot,0,1) \) będzie ciałem o charakterystyce \( p \). Z Obserwacji 6.19, \( p \) jest liczbą pierwszą. Niech \( {\bf 2},{\bf 3},\ldots,{\bf p-1}\in F \) będą zadane przez
\( \begin{align*} {\bf 2} & =1+1, \\ {\bf 3} & =1+1+1, \\ & \ldots & \\ {\bf p-1} & =\underbrace{1+\ldots+1}_{p\ razy}. \end{align*} \)
Ponieważ \( 1 \) ma rząd \( p \) w grupie \( (F,+,0) \), to \( {\bf 2},\ldots,{\bf p-1} \) są parami różne. Ponadto zbiór \( ({\{ {0,1,{\bf 2},\ldots,{\bf p-1}} \} },+,\cdot,0,1) \) jest zamknięty na dodawanie i mnożenie. A zatem jest podciałem ciała \( {\bf F} \), i to izomorficznym z ciałem \( \mathbb{Z}_p \).
Samo natomiast ciało \( {\bf F} \) można traktować jako przestrzeń wektorową nad swoim podciałem \( \mathbb{Z}_p \). Zatem, jako taka właśnie przestrzeń wektorowa, \( {\bf F} \) jest izomorficzna z \( \mathbb{Z}_p^k \), gdzie \( k \) jest wymiarem \( {\bf F} \) nad \( \mathbb{Z}_p \). Stąd w szczególności grupa addytywna ciała \( {\bf F} \) jest izomorficzna z produktem \( k \) kopii grupy \( \mathbb{Z}_p \).
Obserwacja 6.21
Grupa multyplikatywna ciała skończonego jest cykliczna.
Dowód
Niech \( (F,+,\cdot,0,1) \) będzie ciałem o \( q \) elementach. Jednym z warunków równoważnych cykliczności grupy multyplikatywnej \( (F^*,\cdot,1) \) jest to, że
Ponieważ rząd elementu grupy dzieli rząd grupy, to
\( f^{q-1}=1\qquad \) dla dowolnego \( f \in F^* \).
To oznacza, że wszystkie elementy \( F^* \) są pierwiastkami wielomianu \( x^{q-1}-1 \). Niech teraz \( d|q-1 \), czyli \( q-1=dk \) dla pewnego \( k \). Łatwo sprawdzić, iż
\( x^{q-1}-1=(x^d-1)(x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1). \)
Z Obserwacji 6.18 wielomian \( x^d-1 \) ma co najwyżej \( d \) pierwiastków, a \( x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1 \) ma co najwyżej \( d(k-1) \). Jednak ich iloczyn \( x^{q-1}-1 \) ma dokładnie \( q-1 \) pierwiastków, więc oba wielomiany mają odpowiednio \( d \) i \( d(k-1) \) pierwiastków.
Fakt, iż \( x^d-1 \) ma dokładnie \( d \) pierwiastków to dokładnie warunek (*).
Podsumowując nasze rozważania, pokazaliśmy, że:
W tym kontekście nie jest zbyt zaskakujące, iż dowolne dwa ciała \( p^k \)-elementowe okażą się być izomorficzne. W dowodzie Obserwacji 6.20 widzieliśmy, że ciało skończone charakterystyki \( p \) zawiera ciało izomorficzne z \( \mathbb{Z}_p \). Odtąd będziemy więc zakładać, że \( \mathbb{Z}_p \) jest po prostu podciałem takiego ciała.
Dla lepszego zrozumienia grupy i multyplikatywnej ciała przeanalizujemy jeszcze pojęcie pokrewne do pojęcia rzędu elementu \( a \). W ciele skończonym, o \( p^k \) elementach, rząd \( r \) elementu \( a \) dzieli rząd \( p^k-1 \) grupy multyplikatywnej, w szczególności \( {\sf NWD}(p,r)=1 \). Ale również lista
\( a, a^p, a^{p^2}, a^{p^3},\ldots \)
nie może być nieskończona. Wyrazy na niej muszą się powtarzać. Co więcej, \( a^{p^i} = a^{p^j} \) wtedy i tylko wtedy, gdy \( p^i-p^j \) dzieli się przez rząd \( r \) elementu \( a \). Niech więc \( i < j \) czyli \( a^{p^i(p^{j-i} -1)}=1 \). Wtedy \( r \mid p^i(p^{j-i} -1) \) i wobec \( {\sf NWD}(p,r)=1 \) mamy \( p^{j-i} \equiv_r 1 \). Niech \( s \) będzie multyplikatywnym rzędem liczby \( p \) modulo \( r \), tzn najmniejsza taka liczba naturalną \( s \), że \( p^s \equiv_r 1 \). Wtedy mamy
\( a^{p^i} = a^{p^j} \) wtedy i tylko wtedy, gdy \( i \equiv_s j \).
A zatem nasza lista redukuje się do:
\( a, a^p, a^{p^2}, a^{p^3},\ldots, a^{p^{s-1}}. \)
Stopień elementu \( a\neq 0 \) ciała charakterystyki \( p \) to najmniejsza liczba \( d \), dla której \( a^{p^{s}}=a \).
Wniosek 6.22
W skończonym ciele o \( p^k \) elementach, stopień każdego elemetu jest dzielnikiem liczby \( k \).
Obserwacja 6.23
Dla dowolnego ciała \( {\bf F} \) charakterystyki \( p \) oraz \( n\in\mathbb{N} \) mamy:
Dowód
Tak jak w ciele liczb rzeczywistych, można łatwo pokazać, że
\( (a+b)^p = \sum_{i=0}^p {p \choose i}a^ib^{p-i}. \)
To, wraz z faktem, że \( p \) jako liczba pierwsza dzieli wszystkie współczynniki dwumianowe poza \( {p \choose 0} \) i \( {p \choose p} \) oraz, że \( {\bf F} \) ma charakterystykę \( p \), daje \( (a+b)^p = a^p+b^p \). Łatwa indukcja względem \( n \) pokazuje teraz punkt pierwszy.
Dla dowodu punktu drugiego załóżmy, że \( w(x)=\sum_i c_i x^i \). Mamy wtedy \( w(x)^{p^n} = \sum_i c_i^{p^n} x^{ip^n} = \sum_i c_i x^{ip^n} = w(x^{p^n}) \), gdzie równość \( c_i^{p^n} = c_i \) użyta w środkowym przejściu wynika z faktu, że \( c_i\in \mathbb{Z}_p \).
Obserwacja 6.24
Niech \( {\bf F} \) będzie ciałem skończonym charakterystyki \( p \). Wtedy dla dowolnego \( a\in F^* \) istnieje dokładnie jeden unormowany i nierozkładalny wielomian \( w_a(x) \in \mathbb{Z}_p[x] \) taki, że w ciele \( {\bf F} \) zachodzi \( w_a(a)=0 \). Wielomian ten to:
\( w_a(a) = \prod_{i=0}^{d-1} (x-a^{p^i}), \)
gdzie \( d \) jest stopniem elementu \( a \).
Dowód
Wielomian \( w_a \) zdefiniowany w wypowiedzi obserwacji używa współczynników z ciała \( {\bf F} \), które nie muszą być w ciele \( \mathbb{Z}_p \). Aby zobaczyć, że w istocie po wymnożeniu dostajemy współczynniki z \( \mathbb{Z}_p \) niech \( w_a(x)= \sum_{i=0}^{d-1} c_i x^i \). Zauważmy, że zgodnie z Obserwacją 6.23
\( w_a(x)^p = w_a(x^p) = \sum_{i=0}^{d-1} c_i^p x^{ip}. \)
Z drugiej strony fakt, że \( d \) jest stopniem elementu \( a \), czyli równość \( a^{p^d} = a= a^{p^0} \), daje środkowe przejście w ciągu:
\( w_a(x)^p = \prod_{i=0}^{d-1} (x-a^{p^i})^p =\prod_{i=0}^{d-1} (x^p-a^{p^{i+1}}) =\prod_{i=0}^{d-1} (x^p-a^{p^{i}}) =w_a(x^p)=\sum_{i=0}^{d-1} c_i x^{ip} \)
Przyrównując więc teraz współczynniki, dostajemy \( c_i^p=c_i \). Oznacza to, że \( c_0,\ldots,c_{d-1} \in F \) są pierwiastkami wielomianu \( x^p-x \in {\bf F}[x] \). Ponieważ wszystkie elementy z ciała \( \mathbb{Z}_p \subseteq {\bf F} \) są już pierwiastkami tego wielomianu stopnia \( p \), to \( c_0,\ldots,c_{d-1} \) muszą być wśród nich, a zatem \( c_0,\ldots,c_{d-1} \in \mathbb{Z}_p \).
Oczywiście wielomian \( w_a(x) \) jest unormowany. By zobaczyć, że jest nierozkładalny, załóżmy, że \( w_a(x)=p(x)q(x) \). Skoro \( w_a(a)=0 \), to bez straty ogólności możemy założyć, że \( p(a)=0 \). Ale gdyby wielomian \( p(x) \) miał współczynniki w podciele \( \mathbb{Z}_p \), to wobec Obserwacji 6.23 mielibyśmy \( p(a^{p^{d-1}}) = p(a^{p^{d-2}})= \ldots = p(a^{p^2})=p(a^p) = p(a)=0 \), czyli
\( a^{p^{d-1}}, a^{p^{d-2}},\ldots,a^{p^2}, a^p, a \)
byłyby różnymi pierwiastkami wielomianu \( p(x) \), skąd \( {\sf deg}(p(x))=d={\sf deg}(w_a(x)) \) i wielomian \( q(x) \) jest stały.
Pozostaje pokazać, że \( w_a(x) \) jest jedynym wielomianem spełniającym warunki podane w Obserwacji. Niech więc \( v(a) \) będzie takim wielomianem. Wtedy, ponieważ \( v(x) \) ma współczynniki w \( \mathbb{Z}_p \), to wraz z \( a \) również potęgi \( a^p, a^{p^2},\ldots, a^{p^{d-2}}, a^{p^{d-1}} \) są pierwiastkami wielomianu \( v(x) \). To na mocy Twierdzenia Bezout daje, że \( w_a(x) \) dzieli \( v(x) \). Ponieważ jednak \( v(x) \) jest nierozkładalny (nad \( \mathbb{Z}_p \)), to \( v(x) = c \cdot w_a(x) \) dla pewnego \( c\in \mathbb{Z}_p \). Ale skoro obydwa wielomiany \( v(x) \) i \( w_a(x) \) sa unormowane, to \( c=1 \) i \( v(x)=w_a(x) \).
Następne twierdzenie wskaże nam jak konstruować ciała liczności \( p^k \) dla \( k>1 \). Dla niezerowego wielomianu \( q(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) rozważmy dwuargumentową relację \( \sim_{q(x)} \) na zbiorze \( F \) zadaną przez
\( a(x)\sim_{q(x)}b(x) \textrm{ wtedy i tylko wtedy, gdy } q(x)|a(x)-b(x). \)
Łatwo sprawdzić, iż \( \sim_{q(x)} \) jest relacja równoważności zachowującą dodawanie i mnożenie wielomianów. W istocie jest to kongruencja wyznaczona przez ideał główny pierścienia wielomianów \( {\bf F}[x] \) generowany wielomianem \( q(x) \). Zbiór klas równoważności tworzy więc pierścień ilorazowy \( {\bf F}[x]/q(x) \).
Twierdzenie 6.25
Jeśli \( q(x) \) jest nierozkładalnym wielomianem stopnia \( k \) nad ciałem \( \mathbb{Z}_p \), to pierścień ilorazowy \( \mathbb{Z}_p[x]/q(x) \) jest \( p^k \)-elementowym ciałem.
Dowód
Po pierwsze w każdej klasie równoważności relacji \( \sim_{q(x)} \) jest jakiś wielomian stopnia mniejszego niż \( k \). Istotnie, gdy \( p(x)=a(x)\cdot q(x)+r(x) \), gdzie \( r(x) \) jest wielomianem zerowym lub stopnia mniejszego niż \( k \), to \( p(x) \sim_{q(x)} r(x) \). Ponadto, różne wielomiany stopnia mniejszego niż \( k \) nie mogą być \( \sim_{q(x)} \) równoważne. A zatem każda klasa równoważności jest wyznaczona przez dokładnie jeden wielomian stopnia mniejszego niż \( k \). Wielomianów takich jest tyle co wektorów postaci \( (a_{k-1},\ldots,a_0) \), gdzie \( a_i\in\mathbb{Z}_p \). A więc \( \sim_{q(x)} \) ma dokładnie \( p^k \) klas równoważności.
Pozostało sprawdzić, że (przemienny) pierścień ilorazowy jest ciałem, tzn. każdy jego niezerowy element jest odwracalny. W tym miejscu kluczowa jest nierozkładalność wielomianu \( q(x) \).
Niech więc \( a(x) \) będzie niezerowym wielomianem stopnia mniejszego od \( k \). Z nierozkładalności \( q(x) \) wiemy, że \( 1\in\mathbb{Z}_p[x] \) jest największym wspólnym dzielnikiem \( a(x) \) i \( q(x) \). Z Wniosku 6.13 istnieją \( \lambda(x),\mu(x)\in{\bf F}[x] \) takie, że
\( \lambda(x)a(x)+\mu(x)q(x)=1. \)
To oczywiście oznacza, że
\( \lambda(x)a(x) \sim_{q(x)} 1, \)
czyli klasa \( [\lambda]_{q(x)} \) jest odwrotna do \( [a(x)]_{q(x)} \).
Ciało reszt modulo nierozkładalny wielomian \( w(x)\in \mathbb{Z}_p[x] \), to ciało ilorazowe \( \mathbb{Z}_p[x]/q(x) \) opisane w Twierdzeniu 6.25.
Twierdzenie 6.26
Jeśli dwa skończone ciała są równoliczne, to są izomorficzne.
Dowód
Niech ciała \( {\bf F} \) i \( {\bf G} \) mają \( p^k \) elementów. Przez \( a \) oznaczmy generator grupy multyplikatywnej ciała \( {\bf F} \). Wtedy stopień elementu \( a \) wynosi \( k \). Pokażemy, że \( {\{ {1,a,a^2, \ldots, a^{k-1}} \} } \) stanowi bazę dla przestrzeni wektorowej \( {\bf F} \) nad \( \mathbb{Z}_p \). Istotnie, gdyby zbiór ten był liniowo zależny, to \( \sum_{i=0}^{k-1} c_i a^i =0 \) dla pewnych współczynników \( c_i\in\mathbb{Z}_p \). Ale wtedy wielomian \( \sum_{i=0}^{k-1} c_i x^i \) miałby w swoim rozkładzie pewien nierozkładalny i unormowany wielomian \( w'(x) \) stopnia co najwyżej \( k-1 \) taki, że \( w'(a)=0 \). To jednak na mocy Twierdzenia 6.24 nie jest możliwe, bo jedyny taki wielomian w \( \mathbb{Z}_p[x] \) to \( w_a(x) \) stopnia \( k \). Ponieważ liniowo niezależny zbiór \( {\{ {1,a,a^2, \ldots, a^{k-1}} \} } \) ma liczność równa wymiarowi przestrzeni wektorowej \( {\bf F} \) nad \( \mathbb{Z}_p \), to jest jej bazą.
Podobnie, startując od generatora \( b \) grupy multyplikatywnej ciała \( {\bf G} \), dostaniemy bazę \( {\{ {1,b,b^2, \ldots, b^{k-1}} \} } \) przestrzeni wektorowej \( {\bf G} \) nad \( \mathbb{Z}_p \). Teraz łatwo już sprawdzić, że jedyne odwzorowanie liniowe \( F \longrightarrow G \) posyłające \( a^i \) w \( b^i \) jest izomorfizmem nie tylko przestrzeni wektorowych, ale i ciał \( {\bf F} \) i \( {\bf G} \).
Twierdzenie 6.25 pozwala na konstrukcję ciał skończonych o \( p^k \) elementach, gdzie \( p \) jest liczbą pierwszą i \( k>1 \), o ile tylko mamy nierozkładalny wielomian \( k \)-tego stopnia nad \( \mathbb{Z}_p \). Fakt, iż taki wielomian istnieje dla dowolnej liczby pierwszej \( p \) i dowolnego \( k\geq 1 \) jest nietrywialny i jego dowód przeprowadzimy w serii ćwiczeń do tego wykładu.
Twierdzenie 6.27
Dla dowolnej liczby pierwszej \( p \) i \( k\geq1 \) istnieje nierozkładalny wielomian \( k \)-tego stopnia nad ciałem \( \mathbb{Z}_p \).
Wniosek 6.28
Dla dowolnej liczby pierwszej \( p \) i \( k\geq 1 \) istnieje dokładnie jedno, z dokładnością do izomorfizmu, ciało \( p^n \)-elementowe.
Ciało Galois \( {\bf GF}(q) \), gdzie \( q=p^k \) jest potęgą liczby pierwszej, to jedyne z dokładnością do izomorfizmu ciało \( q \)-elementowe.
Przykład
Opiszemy ciała \( {\bf GF}(4) \) i \( {\bf GF}(9) \).
W jednym z poprzednich przykładów widzieliśmy, iż jest tylko jeden taki wielomian:
\( x^2+x+1. \)
\( \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} \)
\( \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} \)
zatem rzeczywiście wielomian \( x^2+2x+2 \) jest nierozkładalny nad \( \mathbb{Z}_3 \).