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ło to struktura \( {\bf F}=(F,+,\cdot,0,1) \), gdzie \( F \) jest zbiorem, \( 0,1\in F \) i \( 0\neq1 \), a \( + \) i \( \cdot \) to dwuargumentowe działania na \( F \) spełniające następujące warunki:
Ciało \( {\bf F}=(F,+,\cdot,0,1) \) jest skończone jeśli zbiór \( F \) jest skończony, w przeciwnym wypadku \( {\bf F} \) jest nieskończone.
Zgodnie z ogólnie przyjętą konwencją posługujemy się następującą notacją:
Przykład
Obserwacja 6.1
Dla elementu \( x \) ciała \( {\bf F}=(F,+,\cdot,0,1) \) mamy \( x\cdot0=0 \).
Dowód
Mamy \( x\cdot0=x\cdot(0+0)=x\cdot0+x\cdot0 \), co wobec prawa skracania dla grupy \( (F,+,0) \) daje \( 0=x\cdot0 \).
Obserwacja 6.2
Dla elementów \( x,y\in F \) ciała \( {\bf F}=(F,+,\cdot,0,1) \), jeśli \( xy=0 \), to \( x=0 \) lub \( y=0 \).
Dowód
Załóżmy, że \( xy=0 \) i \( x\neq0 \). Ponieważ \( x\in F^* \), to \( x \) ma element odwrotny w \( (F^*,\cdot,1) \), i wtedy \( y=1\cdot y=(x^{-1}x)y=x^{-1}(xy)=x^{-1}\cdot0=0 \).
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ścień to struktura \( {\mathbf R}=(R,+,\cdot,0,1) \), gdzie \( R \) jest zbiorem, \( 0,1\in R \) i \( 0\neq1 \), a \( + \) i \( \cdot \) to działania dwuargumentowe spełniające następujące warunki:
\( \begin{align*} x\cdot(y\cdot z) & =(x\cdot y)\cdot z \\ (x+y)\cdot z & =x\cdot z+y\cdot z, \\ x\cdot(y+z) & =x\cdot y+x\cdot z, \\ 1\cdot x & =x\cdot1=x. \end{align*} \)
Pierścień \( {\mathbf R}=(R,+,\cdot,0,1) \) jest przemienny jeśli \( xy=yx \) dla dowolnych \( x,y\in R \).
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 \( \cdot \). W pierścieniach, tak jak i w ciałach, \( 0 \) przemnożone przez cokolwiek pozostaje zerem (niezależnie z której strony mnożymy \( 0 \)). Dowód przebiega analogicznie jak dla ciał.
Obserwacja 6.3
Dla dowolnego pierścienia \( {\mathbf R}=(R,+,\cdot,0,1) \) i \( x\in R \)
\( x\cdot0=0\cdot x=0. \)
W odróżnieniu od ciał pierścienie mogą posiadać dzielniki zera, czyli niezerowe elementy, których iloczyn daje zero.
Przykład
\( \left(\begin{array} {cc}3 & 1 \\ 0 & 4\end{array} \right)\cdot\left(\begin{array} {cc}4 & 2 \\ 5 & 5\end{array} \right)=\left(\begin{array} {cc}17 & 11 \\ 20 & 20\end{array} \right),\qquad \left(\begin{array} {cc}4 & 2 \\ 5 & 5\end{array} \right)\cdot\left(\begin{array} {cc}3 & 1 \\ 0 & 4\end{array}\right )=\left(\begin{array} {cc}12 & 12 \\ 15 & 25\end{array} \right). \)
Dotychczas przyjmowaliśmy, że wielomian to funkcja \( f(x) \), określona np. na zbiorze liczb całkowitych, postaci:
\( f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0, \)
gdzie \( a_i \) 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 \( a(x) \) nad pierścieniem \( {\mathbf R}=(R,+,\cdot,0,1) \) to formalne wyrażenie postaci
\( a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0, \)
gdzie \( n\in\mathbb{N} \), \( a_i\in R \) i \( a_n\neq0 \). Elementy \( a_i \) to współczynniki wielomianu. Współczynnik \( a_n \) to współczynnik wiodący. Wielomian postaci \( a_0 \) nazywamy stałą i często utożsamiamy go z odpowiednim elementem pierścienia \( {\mathbf R} \). Dopuszczamy również wielomian stały \( a_0=0 \) (mimo że współczynnik wiodący równy jest \( 0 \)) - jest to wielomian zerowy. Symbole \( x^i \) 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 \( (a_n,\ldots,a_0) \).
Wielomiany równe to wielomiany (ciągi) w których kolejne współczynniki są równe.
Zbiór wszystkich wielomianów nad pierścieniem \( {\mathbf R} \) oznaczamy przez \( R[x] \).
Suma wielomianów \( a(x),b(x)\in {R}[x] \), dla \( a(x)=a_mx^m+\ldots+a_0 \), \( b(x)=b_nx^n+\ldots+b_0 \) to wielomian \( a(x)+b(x)\in{R}[x] \) zadany przez
\( a(x)+b(x)=(a_k+b_k)x^k+(a_{k-1}+b_{k-1})x^{k-1}+\ldots+(a_0+b_0), \)
gdzie \( k=\max(m,n) \) oraz niezdefiniowane wartości \( a_i \) bądź \( b_i \) traktujemy jako \( 0 \).
Iloczyn wielomianów \( a(x),b(x)\in {R}[x] \), dla \( a(x)=a_mx^m+\ldots+a_0 \), \( b(x)=b_nx^n+\ldots+b_0 \) to wielomian \( a(x)\cdot b(x)\in {R}[x] \) zadany przez
\( \begin{align*} a(x)\cdot b(x) & =(a_mb_n)x^{m+n}+(a_{m-1}b_n+a_mb_{n-1})x^{m+n-1}+\ldots \\ & +(\sum_{j=0}^ia_jb_{i-j})x^i+\ldots+(a_1b_0+a_0b_1)x+(a_0+b_0). \end{align*} \)
Przykład
Suma i iloczyn wielomianów
\( a(x)=3x^2+2x,\qquad b(x)=2x+3. \)
nad pierścieniem \( (\mathbb{Z}_4,+,\cdot,0,1) \) to odpowiednio:
\( \begin{align*} a(x)+b(x) & =(3+0)x^2+(2+2)x+(0+3)=3x^2+3, \\ a(x)\cdot b(x) & =(3+0)x^3+(0\cdot0+2\cdot2+3\cdot3)x^2+(0\cdot2+2\cdot3)x+(0+3) \\ & =3x^3+x^2+2x+3. \end{align*} \)
Zauważmy, że zgodnie z nawykami pomijamy symbole \( x^i \), dla \( a_i=0 \), np.: \( 3x^2+3 \) formalnie oznacza \( 3x^2+0x+3 \).
Elementarny, ale żmudny dowód następnej obserwacji pozostawiamy jako ćwiczenie.
Obserwacja 6.4
Jeśli \( {\mathbf R} \) jest pierścieniem (przemiennym), to \( {\mathbf R}[x]=(R[x],+,\cdot,0,1) \) jest pierścieniem (przemiennym), gdzie \( + \) i \( \cdot \) to operacje sumy i iloczynu wielomianów.
Pierścień wielomianów nad pierścieniem \( {\mathbf R} \) to pierscień \( {\mathbf R[x]}=({R}[x],+,\cdot,0,1) \).
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 \( a(x) \) to liczba \( {\sf deg}(a(x)) \) równa indeksowi jego współczynnika wiodącego. Uwaga: wielomian zerowy ma stopień niezdefiniowany (lub czasem przyjmowany jako \( -\infty \)).
Dodając znane nam, "zwykłe" wielomiany, powiedzmy nad \( \mathbb{Z} \) lub \( \mathbb{R} \), 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 \( {\mathbf R} \) i niezerowych wielomianów \( a(x),b(x)\in{\mathbf R}[x] \), mamy:
\( {\sf deg}(a(x)+b(x))\leq\max({\sf deg}(a(x)),{\sf deg}(b(x)) ). \)
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 \( 2x+1 \) i \( 3x+1 \) nad ciałem \( \mathbb{Z}_5 \) ich suma \( (2x+1)+(3x+1)= 2 \) 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 \( \mathbb{Z}_6 \) wielomiany \( 3x^3+2x^2-1 \) i \( 2x^2+1 \) są stopnia \( 2 \), podczas gdy ich iloczyn \( 6x^5+3x^3+4x^4+2x^2-2x^2-1=4x^4+3x^3-1 \) jest stopnia \( 4 \).
Obserwacja 6.6
Dla dowolnego pierścienia \( {\mathbf R} \) i wielomianów \( a(x),b(x)\in{\mathbf R}[x] \), mamy
\( {\sf deg}(a(x)\cdot b(x))\leq {\sf deg}(a(x))+{\sf deg}(b(x)). \)
Jeśli pierścień \( {\mathbf R} \) jest ciałem, a wielomiany są niezerowe, to
\( {\sf deg}(a(x)\cdot b(x))= {\sf deg}(a(x))+{\sf deg}(b(x)). \)
Dowód
Pierwsza część wynika wprost z definicji iloczynu wielomianów. Niech teraz współczynnikami wiodącymi wielomianów \( a(x),b(x) \) będą odpowiednio \( a_m \) i \( b_n \) Wtedy najwyższym zdefiniowanym, \( (m+n) \)-tym, współczynnikiem iloczynu jest \( a_mb_n \). Z Obserwacji 6.2 mamy \( a_mb_n\neq0 \), zatem jest to współczynnik wiodący.
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 \( \mathbb{R} \).
Przykład
Wydzielmy wielomian \( x^5+5x^4+5x^3+x+5 \) przez \( x^2+4 \) nad ciałem \( {\bf \mathbb{Z}_7} \):
\( \begin{array} {lrrrrrr} & x^3 & +5x^2 & +x & +1 \\ \hline x^2+4| & x^5 & +5x^4 & +5x^3 & +0x^2 & +x & +5 \\ & x^5 & & +4x^3 \\ \hline & & 5x^4 & +x^3 & +0x^2 & +x & +5 \\ & & 5x^4 & & +6x^2 \\ \hline & & & x^3 & +x^2 & +x & +5 \\ & & & x^3 & & +4x \\ \hline & & & & x^2 & +4x & +5 \\ & & & & x^2 & & +4 \\ \hline & & & & & 4x & +1 \end{array} \)
Iloraz równy jest \( x^3+5x^2+x+1 \), zaś reszta \( 4x+1 \).
Obserwacja 6.7
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \), gdzie \( b(x)\neq0 \) istnieją unikalne wielomiany \( q(x),r(x)\in{\bf F}[x] \) takie, że
\( a(x)=q(x)b(x)+r(x), \)
gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(b(x)) \).
Dowód
Najpierw wykażemy istnienie takich wielomianów. Dla ustalonego wielomianu \( b(x) \) poprowadzimy indukcję względem stopnia wielomianu \( a(x) \). Jeśli \( a(x)=0 \), to \( q(x)=r(x)=0 \) są szukanymi wielomoanami. Dla \( {\sf deg}(a(x)) < {\sf deg}(b(x)) \) mamy
\( a(x)=0\cdot b(x)+a(x). \)
Gdy zaś \( {\sf deg}(a(x))\geq{\sf deg}(b(x)) \), zakładamy indukcyjnie, iż dla wszystkich wielomianów stopnia mniejszego niż stopień \( a(x) \) istnieją postulowane w tezie wielomiany. Niech
\( a(x)=a_mx^m +\ldots+a_0,\qquad b(x)=b_nx^n+\ldots+b_0\qquad \) dla \( a_m\neq 0 \), \( b_n\neq 0 \),
oraz
\( a'(x)=a(x)-a_mb_n^{-1}x^{m-n}b(x). \)
Wtedy współczynnik wielomianu \( a'(x) \) przy \( x^{m} \) jest równy \( 0 \), gdyż
\( a'_m=a_m-a_mb_n^{-1}b_n=0. \)
Zatem \( {\sf deg}(a'(x)) < {\sf deg}(a(x)) \) (lub \( a'(x)=0 \)) i z założenia indukcyjnego
\( a'(x)=q'(x)b(x)+r(x), \)
gdzie \( {\sf deg}(r(x)) < {\sf deg}(b(x)) \) lub \( r(x)=0 \). Zauważmy, że
\( a(x)=(q'(x)+a_mb_n^{-1}x^m)b(x)+r(x), \)
czyli szukane wielomany to \( q(x)=q'(x)+a_mb_n^{-1}x^m \) i \( r(x) \).
Dla dowodu jednoznaczności załóżmy, że
\( a(x)=q_0(x)b(x)+r_0(x)=q_1(x)b(x)+r_1(x), \)
gdzie \( r_i(x)=0 \) lub \( {\sf deg}(r_i(x)) < {\sf deg}(b(x)) \) dla \( i=0,1 \). Przekształcając ostatnią równość otrzymujemy
\( (q_0(x)-q_1(x))b(x)=r_1(x)-r_0(x). \)
Z Obserwacji 6.5 i 6.6, jeśli \( q_0(x)\neq q_1(x) \), to \( {\sf deg}((q_0(x)-q_1(x))b(x))\geq{\sf deg}(b(x)) \). Natomiast dla \( r_0(x)\neq r_1(x) \) mamy \( {\sf deg}(r_1(x)-r_0(x)) < {\sf deg}(b(x)) \). Zatem jedyna możliwość aby równość zaszła to \( q_0(x)=q_1(x) \) i \( r_0(x)=r_1(x) \).
Zajmiemy się teraz dokładniej pierścieniem \( {\bf F}[x] \) wielomianów nad ciałem \( {\bf F} \).
Wielomian \( b(x) \) dzieli (jest dzielnikiem) wielomian \( a(x) \) (co zapisujemy \( b(x)|a(x) \)), jeśli \( a(x)=q(x)b(x) \) dla pewnego \( q(x)\in{\bf F}[x] \). Mówimy też wtedy, że \( q(x) \) jest wielokrotnością \( b(x) \).
Okazuje się, iż dowolny niezerowy wielomian stały jest trywialnym dzielnikiem dowolnego wielomianu. W tym sensie wielomiany stałe zachowują się podobnie do liczb \( -1,1 \) w pierścieniu liczb całkowitych.
Obserwacja 6.8
Dowolny, niezerowy wielomian stały nad ciałem \( {\bf F} \) dzieli dowolny wielomian nad \( {\bf F} \).
Dowód
Dla dowolnego \( c\in F^* \) i wielomianu \( a(x)\in{\mathbf F}[x] \) mamy
\( a(x)=(c^{-1}a(x))\cdot c. \)
Obserwacja 6.9
Dla dowolnego ciała \( {\bf F} \) i \( a(x),b(x)\in{\mathbf F}[x] \) jeśli \( a(x)|b(x) \) i \( b(x)|a(x) \) to \( a(x)=c\cdot b(x) \) dla pewnego \( c\in F^* \).
Dowód
Załóżmy, że \( a(x)=q(x)b(x) \) i \( b(x)=q'(x)a(x) \). Mamy wtedy
\( a(x)=q(x)b(x)=q(x)q'(x)a(x). \)
Z Obserwacji 6.6 \( {\sf deg}(a(x)) ={\sf deg}(q(x))+{\sf deg}(q'(x))+{\sf deg}(a(x)) \), czyli \( {\sf deg}(q(x))={\sf deg}(q'(x))=0 \). Zatem \( a(x)=c\cdot b(x) \) dla pewnego \( c\in F^* \).
Największy wspólny dzielnik wielomianów \( a(x),b(x)\in{\bf F}[x] \) to taki wielomian \( g(x) \), ż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 \( (R,+,\cdot,0,1) \) to niepusty podzbiór \( I\subseteq R \) o własnościach:
Obserwacja 6.10
Przecięcie dowolnej rodziny ideałów pierścienia jest ideałem tego pierścienia.
Ideał generowany przez zbiór \( X\subseteq R \) to przecięcie wszystkich ideałów zawierających \( X \).
Ideał główny to ideał generowany przez zbiór jednoelementowy.
Obserwacja 6.11
W pierścieniu wielomianów \( {\mathbf F}[x] \) nad ciałem \( {\bf F} \) każdy ideał jest główny.
Dowód
Niech \( I \) będzie ideałem pierścienia \( {\bf F}[x] \). Jeśli \( I \) składa się tylko z wielomianu zerowego, to \( I \), jako generowany przez \( {\{ {0} \} } \), jest główny. Niech teraz \( g(x) \) będzie niezerowym wielomianem z \( I \) o minimalnym stopniu. Pokażemy, że \( {\{ {g(x)} \} } \) generuje ideał \( I \). Istotnie, niech \( p(x)\in I \). Wydzielając \( p(x) \) przez \( g(x) \) otrzymujemy
\( p(x)=q(x)g(x)+r(x), \)
gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(g(x)) \). Zatem \( r(x)\in I \) bo \( r(x)=p(x)-q(x)g(x) \) i \( p(x),q(x)g(x)\in I \). Ale \( g(x) \) ma minimalny stopień wśród wielomianów w \( I \). Zatem \( r(x)=0 \). To oznacza, iż \( p(x)=q(x)g(x) \), czyli \( {\{ {g(x)} \} } \) generuje \( I \).
Obserwacja 6.12
Dowolne dwa wielomiany \( a(x),b(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) mają największy wspólny dzielnik. Ponadto dla dowolnych \( g(x),h(x) \) największych wspólnych dzielników \( a(x) \) i \( b(x) \) zachodzi \( g(x)=c\cdot h(x) \) dla pewnego \( c\in F \).
Dowód
Niech \( I \) będzie ideałem pierścienia \( {\mathbf F[x]} \) generowanym przez \( {\{ {a(x),b(x)} \} } \). Wtedy \( I={\{ {a'(x)a(x)+b'(x)b(x): a'(x),b'(x)\in{\mathbf F}[x]} \} } \). Z drugiej strony, na podstawie Obserwacji 6.11, ideał \( I \) jest główny. Niech więc \( g(x) \) generuje \( I \) Postulujemy, iż \( g(x) \) jest największym wspólnym dzielnikiem \( a(x) \) i \( b(x) \). Ponieważ \( a(x),b(x)\in I \) a \( I \) jest zbiorem wielokrotności \( g(x) \), to \( g(x)|a(x) \) i \( g(x)|b(x) \). Ponadto, dla dowolnego \( d(x) \) wspólnego dzielnika \( a(x) \) i \( b(x) \) mamy \( d(x)|g(x) \), gdyż \( g(x)=a'(x)a(x)+b'(x)b(x) \) dla pewnych \( a'(x),b'(x)\in{\mathbf F}[x] \).
Dla dowodu drugiej części załóżmy, że \( g(x),h(x)\in{\mathbf F}[x] \) są największymi wspólnymi dzielnikami \( a(x) \) i \( b(x) \). Wtedy mamy \( g(x)|h(x) \) i \( h(x)|g(x) \) i z Obserwacji 6.9 \( g(x)=c\cdot h(x) \) dla pewnego \( c\in F \).
Wniosek 6.13
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \) jeśli \( g(x) \) jest największym wspólnym dzielnikiem \( a(x),b(x) \), to \( g(x)=\lambda(x)a(x)+\mu(x)b(x) \) dla pewnych \( \lambda(x),\mu(x)\in{\mathbf F}[x] \).
Dowód
W dowodzie Obserwacji 6.12 wykazaliśmy, iż wszystkie największe wspólne dzielniki \( a(x) \) i \( b(x) \) są w ideale generowanym przez \( {\{ {a(x),b(x)} \} } \), co jest równoważne z tezą wniosku.
Wielomian unormowany nad ciałem \( {\bf F} \) to wielomian, którego współczynnik wiodący równy jest \( 1 \). Oczywiście dowolny, niezerowy wielomian \( p(x) \) może być przedstawiony w postaci \( p(x)=c\cdot u(x) \), gdzie \( c\in F \), a \( u(x) \) jest wielomianem unormowanym tego samego stopnia co \( p(x) \).
Wniosek 6.14
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \) istnieje dokładnie jeden unormowany największy wspólny dzielnik \( a(x),b(x) \).
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.
Dane są wielomiany \( a(x),b(x) \) nad ciałem \( {\bf F} \). Dla obliczenia największego wspólnego dzielnika wykonujemy następującą sekwencję dzieleń:
\( \begin{align*} a(x) & =b(x)q_0(x)+r_0(x), \\ b(x) & =r_0(x)q_1(x)+r_1(x), \\ r_0(x) & =r_1(x)q_2(x)+r_2(x), \\ & \ldots & \\ r_{n-2} & =r_{n-1}(x)q_n(x)+r_n(x), \\ r_{n-1} & =r_n(x)q_{n+1}(x). \end{align*} \)
Ponieważ stopnie wielomianów \( r_i \) dają ciąg silnie malejący, to po skończonej liczbie kroków uda nam się przeprowadzić dzielenie bez reszty. Ostatnia (niezerowa) reszta \( r_n(x) \) okazuje się być szukanym wielomianem - największym wspólnym dzielnikiem \( a(x) \) i \( b(x) \).
Z ostatniej równości wynika, iż \( r_n(x) \) dzieli \( r_{n-1}(x) \). Przedostatnia równość implikuje, że \( r_n(x) \) dzieli także \( r_{n-2}(x) \), itd., zatem \( r_n(x)|a(x) \) i \( r_n(x)|b(x) \). Ponadto dowolny \( d(x) \) dzielnik \( a(x) \) i \( b(x) \) dzieli \( r_0(x) \), bo \( r_0(x)=a(x)-q_0(x)b(x) \). Ponieważ \( d(x) \) dzieli \( b(x) \) i \( r_0(x) \), to ma podstawie drugiej równości \( d(x) \) dzieli też \( r_1(x) \). Idąc wzdłuż kolejnych równości dostajemy \( d(x)|r_n(x) \).
Analogicznie jak w przypadku pierścienia liczb całkowitych, algorytm Euklidesa może posłużyć do wskazania wielomianów \( \lambda(x),\mu(x) \) takich, że \( \lambda(x)a(x)+\mu(x)b(x)=r_n(x) \).
Przykład
Znajdźmy największy wspólny dzielnik wielomianów \( 5x^3+3x^2+5x+5 \) i \( 3x^2+1 \) nad ciałem \( \mathbb{Z}_7 \) używając algorytmu Euklidesa dla wielomianów:
Pomocnicza tabelka elementów odwrotnych względem mnożenia:
\( \begin{array} {|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline n^{-1} & - & 1 & 4 & 5 & 2 & 3 & 6 \\ \hline \end{array} \)
\( \begin{array} {crrrr} & 4x & +1 \\ \hline 3x^2+1| & 5x^3 & +3x^2 & +5x & +5 \\ & 5x^3 & & +4x \\ \hline & & 3x^2 & +x & +5 \\ & & 3x^2 & & +1 \\ \hline & & & x & +4 \end{array} \)
\( \begin{array} {crrr} & 3x & +2 \\ \hline x+4| & 3x^2 & & +1 \\ & 3x^2 & +5x \\ \hline & & 2x & +1 \\ & & 2x & +1 \\ \hline & & & 0 \end{array} \)
\( \begin{align*} x+4 & =(5x^3+3x^2+5x+5)-(4x+1)(3x^2+1) \\ & =(5x^3+3x^2+5x+5)+(3x+6)(3x^2+1). \end{align*} \)
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 \( {\bf F} \) to taki niezerowy wielomian \( p(x) \), dla którego \( p(x)=a(x)b(x) \) implikuje, że \( a(x) \) jest stały lub \( b(x) \) jest stały.
Przykład
\( x,\qquad x+1. \)
\( x\cdot x=x^2,\qquad x\cdot(x+1)=x^2+x,\qquad (x+1)\cdot(x+1)=x^2+1. \)
\( x^2+x+1. \)
Obserwacja 6.15 [lemat Euklidesa dla wielomianów]
Dla dowolnych wielomianów \( a(x),b(x),p(x) \) nad ciałem \( {\bf F} \), jeśli \( p(x) \) jest nierozkładalny i \( p(x)|a(x)b(x) \), to \( p(x)|a(x) \) lub \( p(x)|b(x) \).
Dowód
Załóżmy, że \( p(x) \) nie dzieli \( a(x) \). Z nierozkładalności \( p(x) \) wiemy, że największym wspólnym dzielnikiem \( p(x) \) i \( a(x) \) jest dowolna stała, w szczególności \( 1\in{\bf F}[x] \). Z Wniosku 6.13 mamy \( \lambda(x)p(x)+\mu(x)a(x)=1 \) dla pewnych \( \lambda(x),\mu(x)\in{\bf F}[x] \). Mnożąc obie strony równości przez \( b(x) \) otrzymujemy
\( \lambda(x)p(x)b(x)+\mu(x)a(x)b(x)=b(x). \)
Zauważmy, że \( p(x) \) dzieli lewą stronę równości. Musi zatem dzielić i prawą.
Rozkład wielomianu unormowanego \( u(x) \) nad \( {\bf F} \) na nierozkładalne, unormowane czynniki to przedstawienie go w postaci \( u(x)=u_0(x)\cdot\ldots\cdot u_{n-1}(x) \), gdzie wszystkie \( u_i\in{\bf F}[x] \) 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 \( p(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) to przedstawienie go w postaci \( p(x)=c\cdot u(x) \), gdzie \( c\in F \) a \( u(x) \) jest wielomianem unormowanym, i później rozłożenie \( u(x) \) na nierozkładalne, unormowane czynniki.
Obserwacja 6.16
Dowolny, niezerowy, unormowany wielomian nad ciałem \( {\bf F} \) ma jednoznaczny (z dokładnością do kolejności czynników) rozkład na nierozkładalne, unormowane czynniki.
Dowód
Indukcja po stopniu wielomianu \( u(x) \). Dla \( {\sf deg}(u(x))\leq1 \) wielomian \( u(x) \) jest nierozkładalny i sam stanowi swój jedyny rozkład. Rozważmy zatem dowolny \( u(x) \) stopnia \( n+1 \) i rozważmy jego dwa rozkłady na nierozkładalne czynniki
\( a_0(x)\cdot\ldots\cdot a_{m-1}(x)=u(x)=b_0(x)\cdot\ldots\cdot b_{n-1}(x). \)
Widzimy, iż \( a_0(x)|b_0(x)\cdot\ldots\cdot b_{n-1}(x) \). Z nierozkładalności \( a_0(x) \) i lematu Euklidesa mamy, iż \( a_0(x)|b_i(x) \) dla pewnego \( i \). Z nierozkładalności \( b_i(x) \) i faktu, iż \( a_0(x) \) i \( b_i(x) \) są unormowane otrzymujemy \( a_0(x)=b_i(x) \). Dzieląc obie strony równości przez ten wielomian \( a_0(x) \) otrzymujemy wielomian istotnie mniejszego stopnia. Zatem z założenia indukcyjnego ma on jednoznaczny rozkład, co kończy dowód.
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 \( p(x)=p_nx^n+\ldots+p_0 \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) to funkcja \( \overline{p}:F\longrightarrow F \) zadana przez
\( \overline{p}(x)=p_nx^n+\ldots+p_1x+p_0. \)
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 \( {\bf \mathbb{Z}_2} \) i ich ewaluacje:
\( a(x)=x^2,\qquad b(x)=x^4+x^3+x^2, \)
\( \begin{array} {rclrcl} \overline{a}(0) & =0^2+0=0, & \overline{b}(0) & =0^2+0=0, \\ \overline{a}(1) & =1^2+1=0, & \overline{b}(1) & =1^2+1=0. \end{array} \)
Zatem \( a(x)\neq b(x) \) ale \( \overline{a}(x)=\overline{b}(x) \).
Obserwacja 6.17 [Bezout]
Dla dowolnego wielomianu \( p(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) i \( c\in F \) następujące warunki są równoważne:
Dowód
Załóżmy najpierw, iż \( x-c|p(x) \). Zatem \( p(x)=q(x)(x-c) \) dla pewnego \( q(x)\in{\bf F}[x] \). Ewaluacja wielomianu \( p(x) \) na elemencie \( c \) daje \( \overline{p}(c)=\overline{q}(c)\cdot(c-c)=0 \).
Dla dowodu implikacji odwrotnej załóżmy, że \( \overline{p}(c)=0 \). Dzieląc \( p(x) \) przez \( x-c \) otrzymujemy
\( p(x)=q(x)(x-c)+r(x), \)
dla pewnych \( q(x),r(x) \) gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(x-c)=1 \). Zatem \( r(x) \) jest wielomianem stałym i jego ewaluacja \( \overline{r} \) to funkcja stała, przyjmująca zawsze tę samą wartość \( r \in F \). Wtedy
\( 0=\overline{p}(c)=\overline{q}(c)\cdot(c-c)+r =r, \)
czyli \( r(x) \) jest wielomianem zerowym i \( x-c|p(x) \).
Pierwiastek wielomianu \( p(x) \) nad ciałem \( {\bf F} \) to taki element \( c\in F \), że \( \overline{p}(c)=0 \).
Przykład
Posługując się twierdzeniem Bezout znajdźmy rozkład wielomianu \( 3x^2+12x+8 \) nad ciałem \( {\bf \mathbb{Z}_{13}} \).
Pomocnicza tabela elementów odwrotnych w grupie multyplikatywnej \( (\mathbb{Z}_{13}^*,\cdot,1) \):
\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline n^{-1} & - & 1 & 7 & 9 & 10 & 8 & 11 & 2 & 5 & 3 & 4 & 6 & 12 \\ \hline \end{array} \)
\( \begin{align*} 3x^2+12x+8 & =3\cdot(3^{-1}\cdot3x^2+3^{-1}\cdot12x+3^{-1}\cdot8) \\ & =3(x^2+4x+7) \end{align*} \)
Obserwacja 6.18
Wielomian stopnia \( n \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) ma co najwyżej \( n \) pierwiastków.
Dowód
Załóżmy, że \( c_0,c_1,\ldots,c_{m-1}\in F \) są wszystkimi pierwiastkami wielomianu \( p(x) \) stopnia \( n \). Wtedy z Obserwacji 6.17 mamy \( x-c_i|p(x) \) dla \( i\in{\{ {0,\ldots,m-1} \} } \). Ponieważ \( x-c_i \) są nierozkładalne, z jednoznaczności rozkładu mamy
\( p(x)=c\cdot(x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x), \)
dla pewnego \( c\in F \) i unormowanego wielomianu \( q(x) \). Ale wtedy Obserwacja 6.6 daje \( n={\sf deg}(p(x))={\sf deg}((x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x))\geq m \).
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 \).