Ciała skończone

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

  • \( (\mathbb{R},+,\cdot,0,1) \) i \( (\mathbb{Q},+,\cdot,0,1) \) mają charakterystykę nieskończoną (czasami przyjmuje się \( 0 \)),
  • charakterystyka \( \mathbb{Z}_p \) równa jest \( p \), gdyż tyle razy trzeba do siebie dodać \( 1 \), aby otrzymać \( 0 \) w \( \mathbb{Z}_p \).

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

(*)dla każdego \( d|q-1 \) liczba elementów \( f\in F^* \) spełniających \( f^d=1 \) wynosi \( d \).

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:

  • dowolne ciało skończone ma \( p^k \) elementów, dla pewnej liczby pierwszej \( p \) i \( k\geq1 \),
  • grupa addytywna dowolnego ciała \( p^k \)-elementowego jest izomorficzna z \( ({\mathbf {Z}_p})^n \),
  • grupa multyplikatywna dowolnego ciała \( p^k \)-elementowego jest izomorficzna z \( {\mathbf {Z}_{p^k-1}} \).

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:

  • jeśli \( a,b \in F \), to \( (a+b)^{p^n} = a^{p^n}+b^{p^n} \),
  • jeśli \( w(x) \in \mathbb{Z}_p[x] \), to \( w(x^{p^n}) = w(x)^{p^n} \),

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) \).

  • \( {\bf GF}(4) \):
    • \( 4=2^2 \) zatem potrzebujemy nierozkładalnego wielomianu stopnia \( 2 \) nad \( {\bf \mathbb{Z}_2} \).

W jednym z poprzednich przykładów widzieliśmy, iż jest tylko jeden taki wielomian:

\( x^2+x+1. \)

    • elementami konstruowanego ciała są \( 4 \) klasy reszt z dzielenia wielomianów nad \( {\bf \mathbb{Z}_2} \) przez \( x^2+x+1 \), o reprezentantach: \( 0,1,x,x+1 \).
    • oto tabelki działań dla ciała \( {\bf GF}(4) \)

\( \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} \)

  • \( {\bf GF}(9) \).
    • \( 9=3^2 \), potrzebujemy zatem nierozkładalnego wielomianu stopnia \( 2 \) nad \( \mathbb{Z}_3 \). Możemy tak jak wcześniej wygenerować wszystkie wielomiany rozkładalne stopnia \( 2 \) nad \( \mathbb{Z}_3 \) i wziąć dowolny spoza tej listy. Jednak jest to bardzo żmudne. Dlatego podajemy od razu nierozkładalny wielomian: \( x^2+2x+2 \). Na szczęście łatwo sprawdzić, że rzeczywiście podany wielomian jest nierozkładalny. Gdyby był rozkładalny musiałby mieć w rozkładzie czynniki stopnia \( 1 \), których istnienie łatwo zweryfikować przy pomocy Twierdzenia Bezout:
      • \( 0^2+2\cdot0+2=2 \),
      • \( 1^2+2\cdot1+2=2 \),
      • \( 2^2+2\cdot2+2=1 \),

zatem rzeczywiście wielomian \( x^2+2x+2 \) jest nierozkładalny nad \( \mathbb{Z}_3 \).

  • elementy konstruowanego ciała to \( 9 \) klas reszt z dzielenia wielomianów nad \( {\bf \mathbb{Z}_3} \) przez \( x^2+2x+2 \), o reprezentantach: \( 0,1,2,x,x+1,x+2, 2x,2x+1, 2x+2 \)