Ciało skończone


Ciało skończone w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Spis treści

Ciało skończone lub ciało Galoisciało skończonego rzędu, tj. o skończonej liczbie elementów; druga z nazw pochodzi od nazwiska francuskiego matematyka Évariste’a Galois, który znacząco przyczynił się do rozwoju badań nad ciałami skończonymi oraz 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 {\displaystyle p} elementach (tzn. rzędu p , {\displaystyle p,} gdzie p {\displaystyle p} jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli F p {\displaystyle \mathbf {F} _{p}} oraz Z / ( p ) ; {\displaystyle \mathbb {Z} /(p);} inną stosowaną notacją jest G F ( p ) {\displaystyle \mathrm {GF} (p)} (od ang. Galois field, ciało Galois).

Konstrukcja i własności | edytuj kod

 Zobacz też: wielomianpierścień wielomianów.

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

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 {\displaystyle p^{n}} będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu x p n x {\displaystyle x^{p^{n}}-x} nad ciałem F p {\displaystyle \mathbf {F} _{p}} [6]; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne[7][8]. Wychodząc stąd, można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej[9]. Dla dowolnej liczby pierwszej p {\displaystyle p} i naturalnej liczby n {\displaystyle n} istnieje unormowany wielomian nierozkładalny stopnia n {\displaystyle n} należący do F p x {\displaystyle \mathbf {F} _{p}[x]} [10]. Podciała F p n {\displaystyle \mathbf {F} _{p^{n}}} są rzędu p d , {\displaystyle p^{d},} gdzie d | n , {\displaystyle d|n,} przy czym istnieje jedno i tylko jedno takie ciało dla każdego d {\displaystyle d} [11].

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

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

Ciała skończone nie są algebraicznie domknięte[15] (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 kod

Pierścień Z / 7 Z {\displaystyle \mathbb {Z} /7\mathbb {Z} } tworzy ciało 7 {\displaystyle 7} -elementowe; jego elementami są ideały 0 Z , , 6 Z {\displaystyle 0\mathbb {Z} ,\dots ,6\mathbb {Z} } z naturalnie określonymi działaniami (zob. pierścień ilorazowy). Innym ciałem 7 {\displaystyle 7} -elementowym jest pierścień Z 7 {\displaystyle \mathbb {Z} _{7}} o elementach 0 , , 6 {\displaystyle 0,\dots ,6} z działaniami arytmetyki modularnej; ciało to ma tę postać, co Z 7 x / ( x ) = F 7 x / ( x ) . {\displaystyle \mathbb {Z} _{7}[x]/(x)=\mathbf {F} _{7}[x]/(x).} W gruncie rzeczy wszystkie ciała o 7 {\displaystyle 7} elementach mają tę samą strukturę. Pierścień Z 4 {\displaystyle \mathbb {Z} _{4}} nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera 2 ; {\displaystyle 2;} skoro 2 2 = 0 , {\displaystyle 2\cdot 2=0,} to 2 {\displaystyle 2} jest niezerowym elementem nieodwracalnym[16] (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 {\displaystyle 4} -elementowym ciele F 2 x / ( x 2 + x + 1 ) {\displaystyle \mathbf {F} _{2}[x]/(x^{2}+x+1)} (wielomian x 2 + x + 1 {\displaystyle x^{2}+x+1} jest jedynym nierozkładalnym wielomianem drugiego stopnia nad F 2 {\displaystyle \mathbf {F} _{2}} ) przedstawiono niżej:

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

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

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

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

Rys historyczny | edytuj kod

Ciała o rzędzie wyrażającym się liczbą pierwszą, Z / p Z , {\displaystyle \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 F p ( α ) , {\displaystyle \mathbf {F} _{p}(\alpha ),} gdzie α {\displaystyle \alpha } jest pierwiastkiem wielomianu nierozkładalnego π {\displaystyle \pi } zmiennej x {\displaystyle x} nad ciałem F p {\displaystyle \mathbf {F} _{p}} (tzn. należącego do F p x {\displaystyle \mathbf {F} _{p}[x]} ); jest to równoważne rozpatrywaniu F p x / ( π ) . {\displaystyle \mathbf {F} _{p}[x]/(\pi ).} Galois nie pokazał, że w F p x {\displaystyle \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 F p x / ( π ) ; {\displaystyle \mathbf {F} _{p}[x]/(\pi );} twierdzenie opatrzył komentarzem „To interesujący wynik, którego sformułowania nie widziałem nigdzie indziej”[17]. 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”)[18]. Każde skonstruowane ciało postaci F p x / ( π ) . {\displaystyle \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 G F ( q ) {\displaystyle \mathrm {GF} (q)} (od ang. Galois field) stosowana jest często zamiast F q . {\displaystyle \mathbf {F} _{q}.}

Przypisy | edytuj kod

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

Bibliografia | edytuj kod

  • J. Browkin: Teoria ciał. Wyd. 1. T. 49. Warszawa: PWN, 1977, seria: Biblioteka Matematyczna.
  • Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.
  • E.H. Moore: A Doubly-Infnite System of Simple Groups, s. 208–242 w „Mathematical papers read at the International Mathematical Congress held in connection with the World’s Columbian Exposition, Chicago, 1893”; Macmillan & Co., Nowy Jork, 1896.
  • Andrzej Chmielowiec, Ciała charakterystyki 2 – aspekty implementacyjne, 2007
Na podstawie artykułu: "Ciało skończone" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy