Matematyka dyskretna 2/Wykład 6: Ciała skończone

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wstęp

Ciała odgrywają olbrzymią rolę we wszystkich prawie dziedzinach matematyki. Chyba najbardziej znanym ciałem jest zbiór liczb rzeczywistych z dodawaniem i mnożenie. Wraz z ciałem liczb zespolonych, ciało liczb rzeczywistych stanowi podstawę Analizy Matematycznej. Ten wykład poświęcony jest podstawowym własnościom ciał skończonych.

Koncepcje ciała stosowali jako pierwsi Niels Abel i Evariste Galois w swoich pracach dotyczących rozwiązywalności równań algebraicznych. W 1893, Heinrich Weber podał pierwszą kompletną definicję abstrakcyjnego ciała. W 1910, Ernst Steinitz opublikował pracę, która dała podstawy współczesnej teorii ciał.

Ciała

Ciało to struktura , gdzie jest zbiorem, i , a i to dwuargumentowe działania na spełniające następujące warunki:

  • jest grupą abelową, nazywaną grupą addytywną ciała,
  • , gdzie , jest grupą abelową, nazywaną grupą multyplikatywną ciała,
  • dla dowolnych .

Ciało jest skończone jeśli zbiór jest skończony, w przeciwnym wypadku jest nieskończone.

Zgodnie z ogólnie przyjętą konwencją posługujemy się następującą notacją:

  • oznacza ,
  • oznacza element odwrotny do w grupie addytywnej ,
  • oznacza ,
  • dla przez oznaczamy element odwrotny do w grupie multyplikatywnej ,
  • , dla , to dodatnie i ujemne wielokrotności elementu , czyli "potęgi" w grupie addytywnej ,
  • , dla i , to dodatnie i ujemne potęgi elementu w grupie multyplikatywnej

Przykład

  • Dla dowolnej liczby pierwszej, jest ciałem skończonym. Rzeczywiście:
    • jest grupą abelową,
    • jest grupą (z uwagi na pierwszość liczby ) abelową,
    • mnożenie jest rozdzielne względem dodawania.
  • nie jest ciałem, gdyż poza i liczby całkowite nie mają elementów odwrotnych względem mnożenia.
  • jest ciałem, gdyż:
    • jest grupa abelową,
    • jest grupą abelową. W szczególności dla dowolnego liczba jest odwrotnością ,
    • mnożenie jest rozdzielne względem dodawania.
  • jest ciałem.

Obserwacja 6.1

Dla elementu ciała mamy .

Dowód

Mamy , co wobec prawa skracania dla grupy daje .

End of proof.gif

Obserwacja 6.2

Dla elementów ciała , jeśli , to lub .

Dowód

Załóżmy, że i . Ponieważ , to ma element odwrotny w , i wtedy .

End of proof.gif

W wykładzie tym pominiemy własności ciała liczb rzeczywistych. Skoncentrujemy naszą uwagę na charakteryzacji ciał skończonych, nazywanych też ciałami Galois. W tym celu potrzebujemy jednak wielu dodatkowych pojęć.

Pierścienie wielomianów

Pierścień to struktura , gdzie jest zbiorem, i , a i to działania dwuargumentowe spełniające następujące warunki:

  • jest grupą abelową,
  • dla dowolnych


Pierścień jest przemienny jeśli dla dowolnych .

Oczywiście każde ciało jest pierścieniem. W pierścieniu mnożenie nie musi być jednak przemienne, a jego elementy nie muszą mieć elementów odwrotnych ze względu na mnożenie . W pierścieniach, tak jak i w ciałach, przemnożone przez cokolwiek pozostaje zerem (niezależnie z której strony mnożymy ). Dowód przebiega analogicznie jak dla ciał.

Obserwacja 6.3

Dla dowolnego pierścienia i



W odróżnieniu od ciał pierścienie mogą posiadać dzielniki zera, czyli niezerowe elementy, których iloczyn daje zero.

Przykład

  • jest pierścieniem przemiennym bez dzielników zera, gdyż:
    • jest grupą abelową
    • mnożenie jest łączne, przemienne i rozdzielne względem dodawania,
    • jest elementem neutralnym ze względu na mnożenie,
    • , o ile tylko .
  • jest pierścieniem przemiennym. Gdy jest liczbą pierwszą, jest nawet ciałem. Gdy jest liczbą złożoną jest tylko pierścieniem i to z dzielnikami zera.
    • na przykład w pierścieniu mamy , czyli i są dzielnikami zera.
  • Niech będzie zbiorem macierzy liczb całkowitych wymiaru , i . Wtedy , gdzie i to dodawanie i mnożenie macierzy, jest pierścieniem ale nieprzemiennym. Rzeczywiście mnożenie macierzy nie jest przemienne, np. dla



Dotychczas przyjmowaliśmy, że wielomian to funkcja , określona np. na zbiorze liczb całkowitych, postaci:



gdzie były współczynnikami wielomianu. Jest to podejście analityczne. Przedstawimy teraz algebraiczny odpowiednik tego pojęcia. Istotną zmianą będzie rozróżnienie formalnego wyrażenia jakim jest wielomian od funkcji wielomianowej (czyli ewaluacji wielomianu). Zobaczymy później, że takie rozróżnienie jest potrzebne, zwłaszcza w pierścieniach i ciałach skończonych.

Wielomian nad pierścieniem to formalne wyrażenie postaci



gdzie , i . Elementy to współczynniki wielomianu. Współczynnik to współczynnik wiodący. Wielomian postaci nazywamy stałą i często utożsamiamy go z odpowiednim elementem pierścienia . Dopuszczamy również wielomian stały (mimo że współczynnik wiodący równy jest ) - jest to wielomian zerowy. Symbole należy traktować jedynie jako etykiety pozycji dla współczynników. Wielomiany równie dobrze można zapisywać w tradycyjnej notacji dla ciągów, czyli .

Wielomiany równe to wielomiany (ciągi) w których kolejne współczynniki są równe.

Zbiór wszystkich wielomianów nad pierścieniem oznaczamy przez .

Suma wielomianów , dla , to wielomian zadany przez



gdzie oraz niezdefiniowane wartości bądź traktujemy jako .

Iloczyn wielomianów , dla , to wielomian zadany przez



Przykład

Suma i iloczyn wielomianów



nad pierścieniem to odpowiednio:



Zauważmy, że zgodnie z nawykami pomijamy symbole , dla , np.: formalnie oznacza .

Elementarny, ale żmudny dowód następnej obserwacji pozostawiamy jako ćwiczenie.

Obserwacja 6.4

Jeśli jest pierścieniem (przemiennym), to jest pierścieniem (przemiennym), gdzie i to operacje sumy i iloczynu wielomianów.

Pierścień wielomianów nad pierścieniem to pierscień .

Przedstawimy teraz całą serię obserwacji dla pierścienia wielomianów, które są analogią do własności pierścienia liczb całkowitych. Będą to pewnego rodzaju uogólnienia dzielenia całkowitego liczb, algorytmu Euklidesa, pojęcia liczby pierwszej i Fundamentalnego Twierdzenia Arytmetyki.

Stopień wielomianu to liczba równa indeksowi jego współczynnika wiodącego. Uwaga: wielomian zerowy ma stopień niezdefiniowany (lub czasem przyjmowany jako ).

Dodając znane nam, "zwykłe" wielomiany, powiedzmy nad lub , wiemy, iż stopień sumy nie przekracza większego ze stopni wielomianów sumowanych. Podobnie iloczyn takich wielomianów zawsze ma stopień równy sumie stopni mnożonych wielomianów. Analogiczne prawo dla dodawania zachodzi dla wielomianów nad dowolnym pierścieniem. Niestety stopień iloczynu wielomianów nad dowolnym pierścieniem może, odbiegając od tych intuicji, być mniejszy niż suma stopni. Winne temu są dzielniki zera. Dlatego czasem pozostaniemy z wielomianami o współczynnikach z jakiegoś ciała.

Obserwacja 6.5

Dla dowolnego pierścienia i niezerowych wielomianów , mamy:



Przykład

Suma wielomianów nad skończonym ciałem może mieć stopień silnie mniejszy, niż stopień każdego składnika sumy. Na przykład dla wielomianów pierwszego stopnia i nad ciałem ich suma jest wielomianem stałym. Podobnie iloczyn wielomianów nad skończonym pierścieniem może mieć stopień silnie mniejszy od sumy stopni mnożonych wielomianów. Na przykład, nad pierścieniem wielomiany i są stopnia , podczas gdy ich iloczyn jest stopnia .

Obserwacja 6.6

Dla dowolnego pierścienia i wielomianów , mamy



Jeśli pierścień jest ciałem, a wielomiany są niezerowe, to



Dowód

Pierwsza część wynika wprost z definicji iloczynu wielomianów. Niech teraz współczynnikami wiodącymi wielomianów będą odpowiednio i Wtedy najwyższym zdefiniowanym, -tym, współczynnikiem iloczynu jest . Z Obserwacji 6.2 mamy , zatem jest to współczynnik wiodący.

End of proof.gif

Obserwacja 6.6 jest teoretyczną podstawą dla jednoznacznego dzielenia z resztą w pierścieniu wielomianów nad ciałem. Następny przykład jest modyfikacją algorytmu dzielenia wielomianów nad .

Przykład

Wydzielmy wielomian przez nad ciałem :



Iloraz równy jest , zaś reszta .

Obserwacja 6.7

Dla dowolnych wielomianów nad ciałem , gdzie istnieją unikalne wielomiany takie, że



gdzie lub .

Dowód

Najpierw wykażemy istnienie takich wielomianów. Dla ustalonego wielomianu poprowadzimy indukcję względem stopnia wielomianu . Jeśli , to są szukanymi wielomoanami. Dla mamy



Gdy zaś , zakładamy indukcyjnie, iż dla wszystkich wielomianów stopnia mniejszego niż stopień istnieją postulowane w tezie wielomiany. Niech


dla , ,


oraz



Wtedy współczynnik wielomianu przy jest równy , gdyż



Zatem (lub ) i z założenia indukcyjnego



gdzie lub . Zauważmy, że



czyli szukane wielomany to i .

Dla dowodu jednoznaczności załóżmy, że



gdzie lub dla . Przekształcając ostatnią równość otrzymujemy



Z Obserwacji 6.5 i 6.6, jeśli , to . Natomiast dla mamy . Zatem jedyna możliwość aby równość zaszła to i .

End of proof.gif

Wielomiany nad ciałem

Zajmiemy się teraz dokładniej pierścieniem wielomianów nad ciałem .

Wielomian dzieli (jest dzielnikiem) wielomian (co zapisujemy ), jeśli dla pewnego . Mówimy też wtedy, że jest wielokrotnością .

Okazuje się, iż dowolny niezerowy wielomian stały jest trywialnym dzielnikiem dowolnego wielomianu. W tym sensie wielomiany stałe zachowują się podobnie do liczb w pierścieniu liczb całkowitych.

Obserwacja 6.8

Dowolny, niezerowy wielomian stały nad ciałem dzieli dowolny wielomian nad .

Dowód

Dla dowolnego i wielomianu mamy



End of proof.gif

Obserwacja 6.9

Dla dowolnego ciała i jeśli i to dla pewnego .

Dowód

Załóżmy, że i . Mamy wtedy



Z Obserwacji 6.6 , czyli . Zatem dla pewnego .

End of proof.gif

Największy wspólny dzielnik wielomianów to taki wielomian , że

  • dzieli oraz ,
  • dla dowolnego dzielnika i , wielomian dzieli także .

W przeciwieństwie do liczb całkowitych największy wspólny dzielnik dwu wielomianów nie jest jednoznacznie określony. Wykażemy jednak najpierw, że taki wielomian zawsze istnieje. Pomocne w wykazaniu tego jest pojęcie ideału pierścienia.

Ideał pierścienia to niepusty podzbiór o własnościach:

  • jeśli , to ,
  • jeśli , to dla dowolnego .

Obserwacja 6.10

Przecięcie dowolnej rodziny ideałów pierścienia jest ideałem tego pierścienia.

Ideał generowany przez zbiór to przecięcie wszystkich ideałów zawierających .

Ideał główny to ideał generowany przez zbiór jednoelementowy.

Obserwacja 6.11

W pierścieniu wielomianów nad ciałem każdy ideał jest główny.

Dowód

Niech będzie ideałem pierścienia . Jeśli składa się tylko z wielomianu zerowego, to , jako generowany przez , jest główny. Niech teraz będzie niezerowym wielomianem z o minimalnym stopniu. Pokażemy, że generuje ideał . Istotnie, niech . Wydzielając przez otrzymujemy



gdzie lub . Zatem bo i . Ale ma minimalny stopień wśród wielomianów w . Zatem . To oznacza, iż , czyli generuje .

End of proof.gif

Obserwacja 6.12

Dowolne dwa wielomiany nad ciałem mają największy wspólny dzielnik. Ponadto dla dowolnych największych wspólnych dzielników i zachodzi dla pewnego .

Dowód

Niech będzie ideałem pierścienia generowanym przez . Wtedy . Z drugiej strony, na podstawie Obserwacji 6.11, ideał jest główny. Niech więc generuje Postulujemy, iż jest największym wspólnym dzielnikiem i . Ponieważ a jest zbiorem wielokrotności , to i . Ponadto, dla dowolnego wspólnego dzielnika i mamy , gdyż dla pewnych .

Dla dowodu drugiej części załóżmy, że są największymi wspólnymi dzielnikami i . Wtedy mamy i i z Obserwacji 6.9 dla pewnego .

End of proof.gif

Wniosek 6.13

Dla dowolnych wielomianów nad ciałem jeśli jest największym wspólnym dzielnikiem , to dla pewnych .

Dowód

W dowodzie Obserwacji 6.12 wykazaliśmy, iż wszystkie największe wspólne dzielniki i są w ideale generowanym przez , co jest równoważne z tezą wniosku.

End of proof.gif

Wielomian unormowany nad ciałem to wielomian, którego współczynnik wiodący równy jest . Oczywiście dowolny, niezerowy wielomian może być przedstawiony w postaci , gdzie , a jest wielomianem unormowanym tego samego stopnia co .

Wniosek 6.14

Dla dowolnych wielomianów nad ciałem istnieje dokładnie jeden unormowany największy wspólny dzielnik .

Algorytm Euklidesa pozwalający na znalezienie największego wspólnego dzielnika dwu liczb całkowitych, może być łatwo rozszerzony z pierścienia liczb całkowitych na pierścienie wielomianów.

Algorytm Euklidesa dla wielomianów.

Dane są wielomiany nad ciałem . Dla obliczenia największego wspólnego dzielnika wykonujemy następującą sekwencję dzieleń:



Ponieważ stopnie wielomianów dają ciąg silnie malejący, to po skończonej liczbie kroków uda nam się przeprowadzić dzielenie bez reszty. Ostatnia (niezerowa) reszta okazuje się być szukanym wielomianem - największym wspólnym dzielnikiem i .

Z ostatniej równości wynika, iż dzieli . Przedostatnia równość implikuje, że dzieli także , itd., zatem i . Ponadto dowolny dzielnik i dzieli , bo . Ponieważ dzieli i , to ma podstawie drugiej równości dzieli też . Idąc wzdłuż kolejnych równości dostajemy .

Analogicznie jak w przypadku pierścienia liczb całkowitych, algorytm Euklidesa może posłużyć do wskazania wielomianów takich, że .

Przykład

Znajdźmy największy wspólny dzielnik wielomianów i nad ciałem używając algorytmu Euklidesa dla wielomianów:

Pomocnicza tabelka elementów odwrotnych względem mnożenia:



  • obliczamy pierwszą resztę wydzielając i :
  • ; liczymy następną resztę wydzielając przez :
  • , czyli jest największym wspólnym dzielnikiem wyjściowych wielomianów,

Kulminacją naszych rozważań o pierścieniach wielomianów będzie odpowiednika Fundamentalnego Twierdzenia Arytmetyki. Odpowiednikiem liczb pierwszych w pierścieniu wielomianów są oczywiście wielomiany nierozkładalne na iloczyn wielomianów o silnie mniejszym stopniu.

Wielomian nierozkładalny nad ciałem to taki niezerowy wielomian , dla którego implikuje, że jest stały lub jest stały.

Przykład

  • dla dowolnego ciała następujące wielomiany nad są nierozkładalne:
    • wszystkie niezerowe wielomiany stałe, gdyż dla dowolnego wielomianu stałego jeśli , to i muszą być stałe (z Obserwacji 6.6),
    • wszystkie wielomiany stopnia (tzw. wielomiany liniowe), gdyż dla dowolnego liniowego jeśli , to , czyli dokładnie jeden z wielomianów ma stopień tzn. jest stały.
  • Wielomiany nierozkładalne stopnia nad ciałem .
    • wielomian rozkładalny stopnia , to wielomian powstały przez wymnożenie dwóch wielomianów stopnia ,
    • lista wszystkich wielomianów stopnia nad :
    • lista wszystkich iloczynów wielomianów stopnia pierwszego nad , czyli lista wszystkich wielomianów rozkładalnych stopnia :
    • tylko jeden wielomian stopnia nad nie wystąpił na powyższej liście:

Obserwacja 6.15 [lemat Euklidesa dla wielomianów]

Dla dowolnych wielomianów nad ciałem , jeśli jest nierozkładalny i , to lub .

Dowód

Załóżmy, że nie dzieli . Z nierozkładalności wiemy, że największym wspólnym dzielnikiem i jest dowolna stała, w szczególności . Z Wniosku 6.13 mamy dla pewnych . Mnożąc obie strony równości przez otrzymujemy



Zauważmy, że dzieli lewą stronę równości. Musi zatem dzielić i prawą.

End of proof.gif

Rozkład wielomianu unormowanego nad na nierozkładalne, unormowane czynniki to przedstawienie go w postaci , gdzie wszystkie są nierozkładalne i unormowane. Każdy, niezerowy, unormowany wielomian ma taki rozkład - wystarczy rozbijać kolejne rozkładalne czynniki na iloczyn wielomianów o mniejszym stopniu (wszystkie będą unormowane).

Rozkład dowolnego wielomianu nad ciałem to przedstawienie go w postaci , gdzie a jest wielomianem unormowanym, i później rozłożenie na nierozkładalne, unormowane czynniki.

Obserwacja 6.16

Dowolny, niezerowy, unormowany wielomian nad ciałem ma jednoznaczny (z dokładnością do kolejności czynników) rozkład na nierozkładalne, unormowane czynniki.

Dowód

Indukcja po stopniu wielomianu . Dla wielomian jest nierozkładalny i sam stanowi swój jedyny rozkład. Rozważmy zatem dowolny stopnia i rozważmy jego dwa rozkłady na nierozkładalne czynniki



Widzimy, iż . Z nierozkładalności i lematu Euklidesa mamy, iż dla pewnego . Z nierozkładalności i faktu, iż i są unormowane otrzymujemy . Dzieląc obie strony równości przez ten wielomian otrzymujemy wielomian istotnie mniejszego stopnia. Zatem z założenia indukcyjnego ma on jednoznaczny rozkład, co kończy dowód.

End of proof.gif

Powyższa obserwacja nie daje niestety żadnych wskazówek jak znaleźć rozkład wielomianu. W ogólności jest to bardzo trudny problem. Istnieją jednak proste kryteria znajdowania pewnych szczególnych czynników rozkładu. W szczególności przedstawiamy warunek konieczny i wystarczający na to, by w rozkładzie wystąpił czynnik liniowy (tzn. wielomian pierwszego stopnia). Najpierw jednak musimy wprowadzić zapowiadane już pojęcie ewaluacji wielomianu.

Ewaluacja wielomianu nad ciałem to funkcja zadana przez



Dlaczego rozróżniamy wielomian od jego ewaluacji? Okazuje się, iż różne wielomiany mogą mieć taką samą ewaluację.

Przykład

Zgodnie z definicją dwa wielomiany są równe tylko wtedy, gdy wszystkie odpowiednie ich współczynniki są takie same. Rozważmy zatem dwa różne wielomiany nad ciałem i ich ewaluacje:




Zatem ale .

Obserwacja 6.17 [Bezout]

Dla dowolnego wielomianu nad ciałem i następujące warunki są równoważne:

  • ,
  • .

Dowód

Załóżmy najpierw, iż . Zatem dla pewnego . Ewaluacja wielomianu na elemencie daje .

Dla dowodu implikacji odwrotnej załóżmy, że . Dzieląc przez otrzymujemy



dla pewnych gdzie lub . Zatem jest wielomianem stałym i jego ewaluacja to funkcja stała, przyjmująca zawsze tę samą wartość . Wtedy



czyli jest wielomianem zerowym i .

End of proof.gif

Pierwiastek wielomianu nad ciałem to taki element , że .

Przykład

Posługując się twierdzeniem Bezout znajdźmy rozkład wielomianu nad ciałem .

Pomocnicza tabela elementów odwrotnych w grupie multyplikatywnej :



  • najpierw sprowadzamy nasz wielomian do postaci unormowanej:
  • z Obserwacji 6.16 wiemy, iż wielomian ma jednoznaczny rozkład na unormowane wielomiany nierozkładalne. Ponieważ jest to wielomian drugiego stopnia, więc jeśli jest rozkładalny, musi mieć w rozkładzie dwa czynniki pierwszego stopnia.
  • czynniki pierwszego stopnia możemy znaleźć za pomocą Obserwacji 6.17. Szukamy zatem pierwiastków wielomianu ewaluując go na kolejnych :
    • ,
    • ,
    • ,
    • ,
    • , czyli dzieli . Pozostały czynnik rozkładu możemy znaleźć wydzielając przez lub ewaluując ten wielomian na pozostałych elementach ciała.
    • , zatem i jest to jedyny rozkład na nierozkładalne, unormowane czynniki.
  • .

Obserwacja 6.18

Wielomian stopnia nad ciałem ma co najwyżej pierwiastków.

Dowód

Załóżmy, że są wszystkimi pierwiastkami wielomianu stopnia . Wtedy z Obserwacji 6.17 mamy dla . Ponieważ są nierozkładalne, z jednoznaczności rozkładu mamy



dla pewnego i unormowanego wielomianu . Ale wtedy Obserwacja 6.6 daje .

End of proof.gif

Ciała skończone

Wracamy teraz do ciał skończonych. Jedyne ciała skończone jakie poznaliśmy do tej pory to , gdzie 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 są izomorficzne z ciałem ? Odpowiedzi na te pytania poznamy w pozostałej części wykładu.

Charakterystyka ciała to rząd elementu w grupie addytywnej . 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 dzieli .

Przykład

  • i mają charakterystykę nieskończoną (czasami przyjmuje się ),
  • charakterystyka równa jest , gdyż tyle razy trzeba do siebie dodać , aby otrzymać w .

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ą . Wtedy



Ponieważ oba czynniki prawej strony ostatniej równości są niezerowe, to są one dzielnikami zera. Sprzeczność z Obserwacją 6.2.

End of proof.gif

Obserwacja 6.20

Grupa addytywna dowolnego ciała skończonego jest izomorficzna z dla pewnej liczby pierwszej i . Zatem .

Dowód

Niech będzie ciałem o charakterystyce . Z Obserwacji 6.19, jest liczbą pierwszą. Niech będą zadane przez



Ponieważ ma rząd w grupie , to są parami różne. Ponadto zbiór jest zamknięty na dodawanie i mnożenie. A zatem jest podciałem ciała , i to izomorficznym z ciałem .

Samo natomiast ciało można traktować jako przestrzeń wektorową nad swoim podciałem . Zatem, jako taka właśnie przestrzeń wektorowa, jest izomorficzna z , gdzie jest wymiarem nad . Stąd w szczególności grupa addytywna ciała jest izomorficzna z produktem kopii grupy .

End of proof.gif

Obserwacja 6.21

Grupa multyplikatywna ciała skończonego jest cykliczna.

Dowód

Niech będzie ciałem o elementach. Jednym z warunków równoważnych cykliczności grupy multyplikatywnej jest to, że

(*)dla każdego liczba elementów spełniających wynosi .

Ponieważ rząd elementu grupy dzieli rząd grupy, to


dla dowolnego .


To oznacza, że wszystkie elementy są pierwiastkami wielomianu . Niech teraz , czyli dla pewnego . Łatwo sprawdzić, iż



Z Obserwacji 6.18 wielomian ma co najwyżej pierwiastków, a ma co najwyżej . Jednak ich iloczyn ma dokładnie pierwiastków, więc oba wielomiany mają odpowiednio i pierwiastków.

Fakt, iż ma dokładnie pierwiastków to dokładnie warunek (*).

End of proof.gif

Podsumowując nasze rozważania, pokazaliśmy, że:

  • dowolne ciało skończone ma elementów, dla pewnej liczby pierwszej i ,
  • grupa addytywna dowolnego ciała -elementowego jest izomorficzna z ,
  • grupa multyplikatywna dowolnego ciała -elementowego jest izomorficzna z .

W tym kontekście nie jest zbyt zaskakujące, iż dowolne dwa ciała -elementowe okażą się być izomorficzne. W dowodzie Obserwacji 6.20 widzieliśmy, że ciało skończone charakterystyki zawiera ciało izomorficzne z . Odtąd będziemy więc zakładać, że 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 . W ciele skończonym, o elementach, rząd elementu dzieli rząd grupy multyplikatywnej, w szczególności . Ale również lista



nie może być nieskończona. Wyrazy na niej muszą się powtarzać. Co więcej, wtedy i tylko wtedy, gdy dzieli się przez rząd elementu . Niech więc czyli . Wtedy i wobec mamy . Niech będzie multyplikatywnym rzędem liczby modulo , tzn najmniejsza taka liczba naturalną , że . Wtedy mamy


wtedy i tylko wtedy, gdy

.


A zatem nasza lista redukuje się do:



Stopień elementu ciała charakterystyki to najmniejsza liczba , dla której .

Wniosek 6.22

W skończonym ciele o elementach, stopień każdego elemetu jest dzielnikiem liczby .

Obserwacja 6.23

Dla dowolnego ciała charakterystyki oraz mamy:

  • jeśli , to ,
  • jeśli , to ,

Dowód

Tak jak w ciele liczb rzeczywistych, można łatwo pokazać, że



To, wraz z faktem, że jako liczba pierwsza dzieli wszystkie współczynniki dwumianowe poza i oraz, że ma charakterystykę , daje . Łatwa indukcja względem pokazuje teraz punkt pierwszy.

Dla dowodu punktu drugiego załóżmy, że . Mamy wtedy , gdzie równość użyta w środkowym przejściu wynika z faktu, że .

End of proof.gif

Obserwacja 6.24

Niech będzie ciałem skończonym charakterystyki . Wtedy dla dowolnego istnieje dokładnie jeden unormowany i nierozkładalny wielomian taki, że w ciele zachodzi . Wielomian ten to:



gdzie jest stopniem elementu .

Dowód

Wielomian zdefiniowany w wypowiedzi obserwacji używa współczynników z ciała , które nie muszą być w ciele . Aby zobaczyć, że w istocie po wymnożeniu dostajemy współczynniki z niech . Zauważmy, że zgodnie z Obserwacją 6.23



Z drugiej strony fakt, że jest stopniem elementu , czyli równość , daje środkowe przejście w ciągu:



Przyrównując więc teraz współczynniki, dostajemy . Oznacza to, że są pierwiastkami wielomianu . Ponieważ wszystkie elementy z ciała są już pierwiastkami tego wielomianu stopnia , to muszą być wśród nich, a zatem .

Oczywiście wielomian jest unormowany. By zobaczyć, że jest nierozkładalny, załóżmy, że . Skoro , to bez straty ogólności możemy założyć, że . Ale gdyby wielomian miał współczynniki w podciele , to wobec Obserwacji 6.23 mielibyśmy , czyli



byłyby różnymi pierwiastkami wielomianu , skąd i wielomian jest stały.

Pozostaje pokazać, że jest jedynym wielomianem spełniającym warunki podane w Obserwacji. Niech więc będzie takim wielomianem. Wtedy, ponieważ ma współczynniki w , to wraz z również potęgi są pierwiastkami wielomianu . To na mocy Twierdzenia Bezout daje, że dzieli . Ponieważ jednak jest nierozkładalny (nad ), to dla pewnego . Ale skoro obydwa wielomiany i sa unormowane, to i .

End of proof.gif

Następne twierdzenie wskaże nam jak konstruować ciała liczności dla . Dla niezerowego wielomianu nad ciałem rozważmy dwuargumentową relację na zbiorze zadaną przez



Łatwo sprawdzić, iż 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 generowany wielomianem . Zbiór klas równoważności tworzy więc pierścień ilorazowy .

Twierdzenie 6.25

Jeśli jest nierozkładalnym wielomianem stopnia nad ciałem , to pierścień ilorazowy jest -elementowym ciałem.

Dowód

Po pierwsze w każdej klasie równoważności relacji jest jakiś wielomian stopnia mniejszego niż . Istotnie, gdy , gdzie jest wielomianem zerowym lub stopnia mniejszego niż , to . Ponadto, różne wielomiany stopnia mniejszego niż nie mogą być równoważne. A zatem każda klasa równoważności jest wyznaczona przez dokładnie jeden wielomian stopnia mniejszego niż . Wielomianów takich jest tyle co wektorów postaci , gdzie . A więc ma dokładnie 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 .

Niech więc będzie niezerowym wielomianem stopnia mniejszego od . Z nierozkładalności wiemy, że jest największym wspólnym dzielnikiem i . Z Wniosku 6.13 istnieją takie, że



To oczywiście oznacza, że



czyli klasa jest odwrotna do .

End of proof.gif

Ciało reszt modulo nierozkładalny wielomian , to ciało ilorazowe 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 i mają elementów. Przez oznaczmy generator grupy multyplikatywnej ciała . Wtedy stopień elementu wynosi . Pokażemy, że stanowi bazę dla przestrzeni wektorowej nad . Istotnie, gdyby zbiór ten był liniowo zależny, to dla pewnych współczynników . Ale wtedy wielomian miałby w swoim rozkładzie pewien nierozkładalny i unormowany wielomian stopnia co najwyżej taki, że . To jednak na mocy Twierdzenia 6.24 nie jest możliwe, bo jedyny taki wielomian w to stopnia . Ponieważ liniowo niezależny zbiór ma liczność równa wymiarowi przestrzeni wektorowej nad , to jest jej bazą.

Podobnie, startując od generatora grupy multyplikatywnej ciała , dostaniemy bazę przestrzeni wektorowej nad . Teraz łatwo już sprawdzić, że jedyne odwzorowanie liniowe posyłające w jest izomorfizmem nie tylko przestrzeni wektorowych, ale i ciał i .

End of proof.gif

Twierdzenie 6.25 pozwala na konstrukcję ciał skończonych o elementach, gdzie jest liczbą pierwszą i , o ile tylko mamy nierozkładalny wielomian -tego stopnia nad . Fakt, iż taki wielomian istnieje dla dowolnej liczby pierwszej i dowolnego jest nietrywialny i jego dowód przeprowadzimy w serii ćwiczeń do tego wykładu.

Twierdzenie 6.27

Dla dowolnej liczby pierwszej i istnieje nierozkładalny wielomian -tego stopnia nad ciałem .

Wniosek 6.28

Dla dowolnej liczby pierwszej i istnieje dokładnie jedno, z dokładnością do izomorfizmu, ciało -elementowe.

Ciało Galois , gdzie jest potęgą liczby pierwszej, to jedyne z dokładnością do izomorfizmu ciało -elementowe.

Przykład

Opiszemy ciała i .

  • :
    • zatem potrzebujemy nierozkładalnego wielomianu stopnia nad .

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

    • elementami konstruowanego ciała są klasy reszt z dzielenia wielomianów nad przez , o reprezentantach: .
    • oto tabelki działań dla ciała


  • .
    • , potrzebujemy zatem nierozkładalnego wielomianu stopnia nad . Możemy tak jak wcześniej wygenerować wszystkie wielomiany rozkładalne stopnia nad i wziąć dowolny spoza tej listy. Jednak jest to bardzo żmudne. Dlatego podajemy od razu nierozkładalny wielomian: . 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 , których istnienie łatwo zweryfikować przy pomocy Twierdzenia Bezout:
      • ,
      • ,
      • ,

zatem rzeczywiście wielomian jest nierozkładalny nad .

    • elementy konstruowanego ciała to klas reszt z dzielenia wielomianów nad przez , o reprezentantach: