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

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 $\mathbf{𝐅}=(F,+,\cdot ,0,1)$, gdzie $F$ jest zbiorem, $0,1\in F$ i $0\ne 1$, a $+$ i $\cdot$ to dwuargumentowe działania na $F$ spełniające następujące warunki:

• $(F,+,0)$ jest grupą abelową, nazywaną grupą addytywną ciała,

• $(F^{*},\cdot ,1)$, gdzie $F^{*}=F-\left\{0\right\}$, jest grupą abelową,

nazywaną grupą multyplikatywną ciała,

• $x\cdot (y+z)=x\cdot y+x\cdot z$ dla dowolnych $x,y,z\in F$.

Ciało $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ jest skończone jeśli zbiór $F$ jest skończony, w przeciwnym wypadku $\mathbf{𝐅}$ jest nieskończone.

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

• $xy$ oznacza $x\cdot y$,

• $(-x)$ oznacza element odwrotny do $x$ w grupie addytywnej $(F,+,0)$,

• $x-y$ oznacza $x+(-y)$,

• dla $x\ne 0$ przez $x^{-1}$ oznaczamy element odwrotny do $x$

w grupie multyplikatywnej $(F^{*},\cdot ,1)$,

• $nx$, dla $n\in \mathbb{\mathbb{Z}}$, to dodatnie i ujemne wielokrotności elementu $x$,

czyli "potęgi" w grupie addytywnej $(F,+)$,

• $x^n$, dla $x\ne 0$ i $n\in \mathbb{\mathbb{Z}}$,

to dodatnie i ujemne potęgi elementu $x$ w grupie multyplikatywnej $(F^{*},\cdot ,1)$

Przykład

• Dla dowolnej $p$ liczby pierwszej,

$({\mathbb{\mathbb{Z}}}_p,+,\cdot ,0,1)$ jest ciałem skończonym. Rzeczywiście:

• • $({\mathbb{\mathbb{Z}}}_p,+,0)$ jest grupą abelową,

• • $({\mathbb{\mathbb{Z}}}_p^{*},\cdot ,1)$ jest grupą (z uwagi na pierwszość liczby $p$) abelową,

• • mnożenie jest rozdzielne względem dodawania.

• $(\mathbb{\mathbb{Z}},+,\cdot ,0,1)$ nie jest ciałem,

gdyż poza $-1$ i $1$ liczby całkowite nie mają elementów odwrotnych względem mnożenia.

• $(\mathbb{\mathbb{Q}},+,\cdot ,0,1)$ jest ciałem, gdyż:

• • $(\mathbb{\mathbb{Q}},+,0)$ jest grupa abelową,

• • $(\mathbb{\mathbb{Q}},\cdot ,1)$ jest grupą abelową.

W szczególności dla dowolnego $q\in Q^{*}$ liczba $\frac{1}{q}$ jest odwrotnością $q$,

• • mnożenie jest rozdzielne względem dodawania.

• $(\mathbb{ℝ},+,\cdot ,0,1)$ jest ciałem.

Obserwacja

Dla elementu $x$ ciała $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ mamy $x\cdot 0=0$.

Dowód

Mamy $x\cdot 0=x\cdot (0+0)=x\cdot 0+x\cdot 0$, co wobec prawa skracania dla grupy $(F,+,0)$ daje $0=x\cdot 0$.

Obserwacja

Dla elementów $x,y\in F$ ciała $\mathbf{𝐅}=(F,+,\cdot ,0,1)$, jeśli $xy=0$, to $x=0$ lub $y=0$.

Dowód

Załóżmy, że $xy=0$ i $x\ne 0$. 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}\cdot 0=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ścienie wielomianów

Pierścień to struktura $\mathbf{𝐑}=(R,+,\cdot ,0,1)$, gdzie $R$ jest zbiorem, $0,1\in R$ i $0\ne 1$, a $+$ i $\cdot$ to działania dwuargumentowe spełniające następujące warunki:

• $(R,+,0)$ jest grupą abelową,

• dla dowolnych $x,y,z\in R$

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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. \endaligned}

Pierścień $\mathbf{𝐑}=(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

Dla dowolnego pierścienia $\mathbf{𝐑}=(R,+,\cdot ,0,1)$ i $x\in R$

$x\cdot 0=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

• $(\mathbb{\mathbb{Z}},+,\cdot ,0,1)$ jest pierścieniem przemiennym bez dzielników zera, gdyż:

• • $(\mathbb{\mathbb{Z}},+,0)$ jest grupą abelową

• • mnożenie jest łączne, przemienne i rozdzielne względem dodawania,

• • $1$ jest elementem neutralnym ze względu na mnożenie,

• • $ab\ne 0$, o ile tylko $a,b\in \mathbb{\mathbb{Z}}-\left\{0\right\}$.

• $({\mathbb{\mathbb{Z}}}_n,+,\cdot ,0,1)$ jest pierścieniem przemiennym.

Gdy $n$ jest liczbą pierwszą, jest nawet ciałem. Gdy $n$ jest liczbą złożoną jest tylko pierścieniem i to z dzielnikami zera.

• • na przykład w pierścieniu

${\mathbb{\mathbb{Z}}}_{15}=({\mathbb{\mathbb{Z}}}_{15},+,\cdot ,0,1)$ mamy $3\cdot 5=0$, czyli $3$ i $5$ są dzielnikami zera.

• Niech $M$ będzie zbiorem macierzy liczb całkowitych wymiaru $2\times 2$,

$0_M=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)$ i $1_M=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$. Wtedy $(M,+,\cdot ,0_M,1_M)$, gdzie $+$ i $\cdot$ to dodawanie i mnożenie macierzy, jest pierścieniem ale nieprzemiennym. Rzeczywiście mnożenie macierzy nie jest przemienne, np. dla

$\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),\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_n{x}^n+a_{n-1}{x}^{n-1}+\dots +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,+,\cdot ,0,1)$ to formalne wyrażenie postaci

$a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_0,$

gdzie $n\in \mathbb{\mathbb{N}}$, $a_i\in R$ i $a_n\ne 0$. 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{𝐑}$. 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,\dots ,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{𝐑}$ oznaczamy przez $R[x]$.

Suma wielomianów $a(x),b(x)\in R[x]$, dla $a(x)=a_m{x}^m+\dots +a_0$, $b(x)=b_n{x}^n+\dots +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}+\dots +(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_m{x}^m+\dots +a_0$, $b(x)=b_n{x}^n+\dots +b_0$ to wielomian $a(x)\cdot b(x)\in R[x]$ zadany przez

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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). \endaligned}

Przykład

Suma i iloczyn wielomianów

$a(x)=3x^2+2x,b(x)=2x+3.$

nad pierścieniem $({\mathbb{\mathbb{Z}}}_4,+,\cdot ,0,1)$ to odpowiednio:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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. \endaligned}

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

Jeśli $\mathbf{𝐑}$ jest pierścieniem (przemiennym), to $\mathbf{𝐑}[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{𝐑}$ to pierscień $\mathbf{𝐑}[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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x))} równa indeksowi jego współczynnika wiodącego. Uwaga: wielomian zerowy ma stopień niezdefiniowany (lub czasem przyjmowany jako $-\mathrm{\infty }$).

Dodając znane nam, "zwykłe" wielomiany, powiedzmy nad $\mathbb{\mathbb{Z}}$ lub $\mathbb{ℝ}$, 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

Dla dowolnego pierścienia $\mathbf{𝐑}$ i niezerowych wielomianów $a(x),b(x)\in \mathbf{𝐑}[x]$, mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x)+b(x))\leqslant\max\left({\sf deg}(a(x)),{\sf deg}(b(x)) \right). }

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{\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{\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

Dla dowolnego pierścienia $\mathbf{𝐑}$ i wielomianów $a(x),b(x)\in \mathbf{𝐑}[x]$, mamy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x)\cdot b(x))\leq {\sf deg}(a(x))+{\sf deg}(b(x)). }

Jeśli pierścień $\mathbf{𝐑}$ jest ciałem, a wielomiany są niezerowe, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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_m{b}_n$. Z Obserwacji Uzupelnic obserwacja - brak dzielnikow zera| mamy $a_m{b}_n\ne 0$, zatem jest to współczynnik wiodący.

Obserwacja Uzupelnic obserwacja - stopien iloczynu| 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{ℝ}$.

Przykład

Wydzielmy wielomian $x^5+5x^4+5x^3+x+5$ przez $x^2+4$ nad ciałem ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟕}}$:

$\begin{array}{lrrrr}& x^3& +5x^2& +x& +1\\ x^2+4|& x^5& +5x^4& +5x^3& +0x^2& +x& +5\\ & x^5& & +4x^3\\ & & 5x^4& +x^3& +0x^2& +x& +5\\ & & 5x^4& & +6x^2\\ & & & x^3& +x^2& +x& +5\\ & & & x^3& & +4x\\ & & & & x^2& +4x& +5\\ & & & & x^2& & +4\end{array}$

Iloraz równy jest $x^3+5x^2+x+1$, zaś reszta $4x+1$.

Obserwacja

Dla dowolnych wielomianów $a(x),b(x)$ nad ciałem $\mathbf{𝐅}$, gdzie $b(x)\ne 0$ istnieją unikalne wielomiany $q(x),r(x)\in \mathbf{𝐅}[x]$ takie, że

$a(x)=q(x)b(x)+r(x),$

gdzie $r(x)=0$ lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x))<{\sf deg}(b(x))} mamy

$a(x)=0\cdot b(x)+a(x).$

Gdy zaś Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x))\geqslant{\sf deg}(b(x))} , zakładamy indukcyjnie, iż dla wszystkich wielomianów stopnia mniejszego niż stopień $a(x)$ istnieją postulowane w tezie wielomiany. Niech

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a(x)=a_mx^m +\ldots+a_0,\qquad b(x)=b_nx^n+\ldots+b_0\qquad\textrm{dla } a_m$,$b_nParser nie mógł rozpoznać (błąd składni): {\displaystyle }, }

oraz

$a^{\prime }(x)=a(x)-a_m{b}_n^{-1}{x}^{m-n}b(x).$

Wtedy współczynnik wielomianu $a^{\prime }(x)$ przy $x^m$ jest równy $0$, gdyż

$a{\text{'}}_m=a_m-a_m{b}_n^{-1}{b}_n=0.$

Zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a'(x))<{\sf deg}(a(x))} (lub $a^{\prime }(x)=0$) i z założenia indukcyjnego

$a^{\prime }(x)=q^{\prime }(x)b(x)+r(x),$

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(r(x))<{\sf deg}(b(x))} lub $r(x)=0$. Zauważmy, że

$a(x)=(q^{\prime }(x)+a_m{b}_n^{-1}{x}^m)b(x)+r(x),$

czyli szukane wielomany to $q(x)=q^{\prime }(x)+a_m{b}_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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Uzupelnic obserwacja - stopien sumy| i Uzupelnic obserwacja - stopien iloczynu|, jeśli $q_0(x)\ne q_1(x)$, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}((q_0(x)-q_1(x))b(x))\geqslant{\sf deg}(b(x))} . Natomiast dla $r_0(x)\ne r_1(x)$ mamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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)$.

Wielomiany nad ciałem

Zajmiemy się teraz dokładniej pierścieniem $\mathbf{𝐅}[x]$ wielomianów nad ciałem $\mathbf{𝐅}$.

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 \mathbf{𝐅}[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

Dowolny, niezerowy wielomian stały nad ciałem $\mathbf{𝐅}$ dzieli dowolny wielomian nad $\mathbf{𝐅}$.

Dowód

Dla dowolnego $c\in F^{*}$ i wielomianu $a(x)\in \mathbf{𝐅}[x]$ mamy

$a(x)=(c^{-1}a(x))\cdot c.$

Obserwacja

Dla dowolnego ciała $\mathbf{𝐅}$ i $a(x),b(x)\in \mathbf{𝐅}[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^{\prime }(x)a(x)$. Mamy wtedy

$a(x)=q(x)b(x)=q(x)q^{\prime }(x)a(x).$

Z Obserwacji Uzupelnic obserwacja - stopien iloczynu| Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(a(x)) ={\sf deg}(q(x))+{\sf deg}(q'(x))+{\sf deg}(a(x))} , czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 \mathbf{𝐅}[x]$ to taki wielomian $g(x)$, że

• $g(x)$ dzieli $a(x)$ oraz $b(x)$,

• dla dowolnego $d(x)$ dzielnika $a(x)$ i $b(x)$,

wielomian $d(x)$ dzieli także $g(x)$.

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:

• jeśli $x,y\in I$, to $x+y\in I$,

• jeśli $x\in I$, to $rx\in I$ dla dowolnego $r\in R$.

Obserwacja

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

W pierścieniu wielomianów $\mathbf{𝐅}[x]$ nad ciałem $\mathbf{𝐅}$ każdy ideał jest główny.

Dowód

Niech $I$ będzie ideałem pierścienia $\mathbf{𝐅}[x]$. Jeśli $I$ składa się tylko z wielomianu zerowego, to $I$, jako generowany przez $\left\{0\right\}$, jest główny. Niech teraz $g(x)$ będzie niezerowym wielomianem z $I$ o minimalnym stopniu. Pokażemy, że $\left\{g(x)\right\}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 $\left\{g(x)\right\}$ generuje $I$.

Obserwacja

Dowolne dwa wielomiany $a(x),b(x)$ nad ciałem $\mathbf{𝐅}=(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{𝐅}[x]$ generowanym przez $\left\{a(x),b(x)\right\}$. Wtedy $I=\left\{a^{\prime }(x)a(x)+b^{\prime }(x)b(x):a^{\prime }(x),b^{\prime }(x)\in \mathbf{𝐅}[x]\right\}$. Z drugiej strony, na podstawie Obserwacji Uzupelnic obserwacja - idealy w pierscieniach wielomianow|, 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^{\prime }(x)a(x)+b^{\prime }(x)b(x)$ dla pewnych $a^{\prime }(x),b^{\prime }(x)\in \mathbf{𝐅}[x]$.

Dla dowodu drugiej części załóżmy, że $g(x),h(x)\in \mathbf{𝐅}[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 Uzupelnic obserwacja - wielomiany na wzajem sie dzielace| $g(x)=c\cdot h(x)$ dla pewnego $c\in F$.

Wniosek

Dla dowolnych wielomianów $a(x),b(x)$ nad ciałem $\mathbf{𝐅}$ 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{𝐅}[x]$.

Dowód

W dowodzie Obserwacji Uzupelnic obserwacja - jednoznacznosc nwd| wykazaliśmy, iż wszystkie największe wspólne dzielniki $a(x)$ i $b(x)$ są w ideale generowanym przez $\left\{a(x),b(x)\right\}$, co jest równoważne z tezą wniosku.

Wielomian unormowany nad ciałem $\mathbf{𝐅}$ 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

Dla dowolnych wielomianów $a(x),b(x)$ nad ciałem $\mathbf{𝐅}$ 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.

Algorytm Euklidesa dla wielomianów.

Dane są wielomiany $a(x),b(x)$ nad ciałem $\mathbf{𝐅}$. Dla obliczenia największego wspólnego dzielnika wykonujemy następującą sekwencję dzieleń:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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). \endaligned}

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{\mathbb{Z}}}_7$ używając algorytmu Euklidesa dla wielomianów:

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

$\begin{array}{cccccccc}n& 0& 1& 2& 3& 4& 5& 6\\ n^{-1}& -& 1& 4& 5& 2& 3& 6\end{array}$

• obliczamy pierwszą resztę wydzielając $5x^3+3x^2+5x+5$ i $3x^2+1$:

$\begin{array}{crr}& 4x& +1\\ 3x^2+1|& 5x^3& +3x^2& +5x& +5\\ & 5x^3& & +4x\\ & & 3x^2& +x& +5\\ & & 3x^2& & +1\end{array}$

• $r_0=x+4$; liczymy następną resztę wydzielając $3x^2+1$ przez $x+4$:

$\begin{array}{crr}& 3x& +2\\ x+4|& 3x^2& & +1\\ & 3x^2& +5x\\ & & 2x& +1\\ & & 2x& +1\end{array}$

• $r_1=0$, czyli $r_0=x+4$ jest największym wspólnym dzielnikiem

wyjściowych wielomianów,

• wskaźniki $\lambda (x),\mu (x)\in {\mathbb{\mathbb{Z}}}_7[x]$

z Wniosku Uzupelnic wniosek - wskazniki przy nwd| obliczamy następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x+4&=&(5x^3+3x^2+5x+5)-(4x+1)(3x^2+1)\\ &=&(5x^3+3x^2+5x+5)+(3x+6)(3x^2+1). \endaligned}

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 $\mathbf{𝐅}$ 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

• dla dowolnego ciała $\mathbf{𝐅}$

następujące wielomiany nad $\mathbf{𝐅}$ są nierozkładalne:

• • wszystkie niezerowe wielomiany stałe,

gdyż dla dowolnego wielomianu stałego $p(x)$ jeśli $p(x)=a(x)b(x)$, to $a(x)$ i $b(x)$ muszą być stałe (z Obserwacji Uzupelnic obserwacja - stopien iloczynu|),

• • wszystkie wielomiany stopnia $1$ (tzw. wielomiany liniowe),

gdyż dla dowolnego liniowego $p(x)$ jeśli $p(x)=a(x)b(x)$, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1={\sf deg}(p(x))={\sf deg}(a(x))+{\sf deg}(b(x))} , czyli dokładnie jeden z wielomianów $a(x),b(x)$ ma stopień $0$ tzn. jest stały.

• Wielomiany nierozkładalne stopnia $2$ nad ciałem ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$.

• • wielomian rozkładalny stopnia $2$,

to wielomian powstały przez wymnożenie dwóch wielomianów stopnia $1$,

• • lista wszystkich wielomianów stopnia $1$ nad ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$:

$x,x+1.$

• • lista wszystkich iloczynów wielomianów stopnia pierwszego nad ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$,

czyli lista wszystkich wielomianów rozkładalnych stopnia $2$:

$x\cdot x=x^2,x\cdot (x+1)=x^2+x,(x+1)\cdot (x+1)=x^2+1.$

• • tylko jeden wielomian stopnia $2$ nad ${\mathbf{Z}}_{\mathbf{𝟐}}$

nie wystąpił na powyższej liście:

$x^2+x+1.$

Obserwacja lemat Euklidesa dla wielomianów

Dla dowolnych wielomianów $a(x),b(x),p(x)$ nad ciałem $\mathbf{𝐅}$, 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 \mathbf{𝐅}[x]$. Z Wniosku Uzupelnic wniosek - wskazniki przy nwd| mamy $\lambda (x)p(x)+\mu (x)a(x)=1$ dla pewnych $\lambda (x),\mu (x)\in \mathbf{𝐅}[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 $\mathbf{𝐅}$ na nierozkładalne, unormowane czynniki to przedstawienie go w postaci $u(x)=u_0(x)\cdot \dots \cdot u_{n-1}(x)$, gdzie wszystkie $u_i\in \mathbf{𝐅}[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 $\mathbf{𝐅}=(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

Dowolny, niezerowy, unormowany wielomian nad ciałem $\mathbf{𝐅}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(u(x))\leqslant1} 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 \dots \cdot a_{m-1}(x)=u(x)=b_0(x)\cdot \dots \cdot b_{n-1}(x).$

Widzimy, iż $a_0(x)|b_0(x)\cdot \dots \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_n{x}^n+\dots +p_0$ nad ciałem $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ to funkcja $\bar{p}:F⟶F$ zadana przez

$\bar{p}(x)=p_n{x}^n+\dots +p_{1}x+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 ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$ i ich ewaluacje:

$a(x)=x^2,b(x)=x^4+x^3+x^2,$ $\begin{array}{rclrcl}\bar{a}(0)& =& 0^2+0=0,& \bar{b}(0)& =& 0^2+0=0,\\ \bar{a}(1)& =& 1^2+1=0,& \bar{b}(1)& =& 1^2+1=0.\end{array}$

Zatem $a(x)\ne b(x)$ ale $\bar{a}(x)=\bar{b}(x)$.

Obserwacja Bezout

Dla dowolnego wielomianu $p(x)$ nad ciałem $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ i $c\in F$ następujące warunki są równoważne:

• $x-c|p(x)$,

• $\bar{p}(c)=0$.

Dowód

Załóżmy najpierw, iż $x-c|p(x)$. Zatem $p(x)=q(x)(x-c)$ dla pewnego $q(x)\in \mathbf{𝐅}[x]$. Ewaluacja wielomianu $p(x)$ na elemencie $c$ daje $\bar{p}(c)=\bar{q}(c)\cdot (c-c)=0$.

Dla dowodu implikacji odwrotnej załóżmy, że $\bar{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}(r(x))<{\sf deg}(x-c)=1} . Zatem $r(x)$ jest wielomianem stałym i jego ewaluacja $\bar{r}$ to funkcja stała, przyjmująca zawsze tę samą wartość $r\in F$. Wtedy

$0=\bar{p}(c)=\bar{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 $\mathbf{𝐅}$ to taki element $c\in F$, że $\bar{p}(c)=0$.

Przykład

Posługując się twierdzeniem Bezout znajdźmy rozkład wielomianu $3x^2+12x+8$ nad ciałem ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟏}\mathbf{𝟑}}$.

Pomocnicza tabela elementów odwrotnych w grupie multyplikatywnej $({\mathbb{\mathbb{Z}}}_{13}^{*},\cdot ,1)$:

$\begin{array}{cccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ n^{-1}& -& 1& 7& 9& 10& 8& 11& 2& 5& 3& 4& 6& 12\end{array}$

• najpierw sprowadzamy nasz wielomian do postaci unormowanej:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 3x^2+12x+8&=&3\cdot(3^{-1}\cdot3x^2+3^{-1}\cdot12x+3^{-1}\cdot8)\\ &=&3(x^2+4x+7) \endaligned}

• z Obserwacji Uzupelnic obserwacja - jednoznaczny rozklad| wiemy,

iż wielomian $x^2+4x+7$ 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 Uzupelnic obserwacja - wkw na pierwiastek|. Szukamy zatem pierwiastków wielomianu $x^2+4x+7$ ewaluując go na kolejnych $n\in {\mathbb{\mathbb{Z}}}_{13}$:

• • $0^2+4\cdot 0+7=7$,

• • $1^2+4\cdot 1+7=12$,

• • $2^2+4\cdot 2+7=4$,

• • $3^2+4\cdot 3+7=2$,

• • $4^2+4\cdot 4+7=0$, czyli $x-4=x+9$ dzieli $x^2+4x+7$.

Pozostały czynnik rozkładu możemy znaleźć wydzielając $x^2+4x+7$ przez $x+9$ lub ewaluując ten wielomian na pozostałych elementach ciała.

• • $5^2+4\cdot 5+7=0$, zatem $x^2+4x+7=(x+8)(x+9)$

i jest to jedyny rozkład $x^2+4x+7$ na nierozkładalne, unormowane czynniki.

• $3x^2+12x+8=3(x+8)(x+9)$.

Obserwacja

Wielomian stopnia $n$ nad ciałem $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ ma co najwyżej $n$ pierwiastków.

Dowód

Załóżmy, że $c_0,c_1,\dots ,c_{m-1}\in F$ są wszystkimi pierwiastkami wielomianu $p(x)$ stopnia $n$. Wtedy z Obserwacji Uzupelnic obserwacja - wkw na pierwiastek| mamy $x-c_i|p(x)$ dla $i\in \left\{0,\dots ,m-1\right\}$. Ponieważ $x-c_i$ są nierozkładalne, z jednoznaczności rozkładu mamy

$p(x)=c\cdot (x-c_0)\cdot \dots \cdot (x-c_{m-1})q(x),$

dla pewnego $c\in F$ i unormowanego wielomianu $q(x)$. Ale wtedy Obserwacja Uzupelnic obserwacja - stopien iloczynu| daje Parser nie mógł rozpoznać (błąd składni): {\displaystyle n={\sf deg}(p(x))={\sf deg}((x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x))\geq m} .

Ciała skończone

Wracamy teraz do ciał skończonych. Jedyne ciała skończone jakie poznaliśmy do tej pory to $({\mathbb{\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{\mathbb{Z}}}_p$? Odpowiedzi na te pytania poznamy w pozostałej części wykładu.

Charakterystyka ciała $\mathbf{𝐅}=(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 $\mathbf{𝐅}$ dzieli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertF\right\vert} .

Przykład

• $(\mathbb{ℝ},+,\cdot ,0,1)$ i $(\mathbb{\mathbb{Q}},+,\cdot ,0,1)$

mają charakterystykę nieskończoną (czasami przyjmuje się $0$),

• charakterystyka ${\mathbb{\mathbb{Z}}}_p$ równa jest $p$,

gdyż tyle razy trzeba do siebie dodać $1$, aby otrzymać $0$ w ${\mathbb{\mathbb{Z}}}_p$.

Obserwacja

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=(\underset{nrazy}{\underbrace{1+\dots +1}})=(\underset{prazy}{\underbrace{1+\dots +1}})\cdot (\underset{qrazy}{\underbrace{1+\dots +1}}).$

Ponieważ $p,q<n$ oba czynniki prawej strony ostatniej równości są niezerowe, to są one dzielnikami zera. Sprzeczność z Obserwacją Uzupelnic obserwacja - brak dzielnikow zera|.

Obserwacja

Grupa addytywna dowolnego ciała skończonego $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ jest izomorficzna z $({\mathbb{\mathbb{Z}}}_p{)}^k$ dla pewnej liczby pierwszej $p$ i $k\ge 1$. Zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertF\right\vert=p^k} .

Dowód

Niech $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ będzie ciałem o charakterystyce $p$. Z Obserwacji Uzupelnic obserwacja - charakterystyka jest liczba pierwsza|, $p$ jest liczbą pierwszą. Niech $\mathbf{𝟐},\mathbf{𝟑},\dots ,\mathbf{𝐩}\mathbf{-}\mathbf{𝟏}\in F$ będą zadane przez

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned {\bf 2}&=&1+1,\\ {\bf 3}&=&1+1+1,\\ &\ldots&\\ {\bf p-1}&=&\underbrace{1+\ldots+1}_{p\ razy}. \endaligned}

Ponieważ $1$ ma rząd $p$ w grupie $(F,+,0)$, to $\mathbf{𝟐},\dots ,\mathbf{𝐩}\mathbf{-}\mathbf{𝟏}$ są parami różne. Ponadto zbiór $(\left\{0,1,\mathbf{𝟐},\dots ,\mathbf{𝐩}\mathbf{-}\mathbf{𝟏}\right\},+,\cdot ,0,1)$ jest zamknięty na dodawanie i mnożenie. A zatem jest podciałem ciała $\mathbf{𝐅}$, i to izomorficznym z ciałem ${\mathbb{\mathbb{Z}}}_p$.

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

Obserwacja

Grupa multyplikatywna ciała skończonego jest cykliczna.

Dowód

Niech $(F,+,\cdot ,0,1)$ będzie ciałem o $q$ elementach. Jednym z warunków równoważnych cykliczności grupy multyplikatywnej $(F^{*},\cdot ,1)$ jest to, że

(*)

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle f^{q-1}=1\qquad\textrm{dla dowolnego } f F^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle .} }

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)}+\dots +x^d+1).$

Z Obserwacji Uzupelnic obserwacja - liczba pierwiastkow a stopien| wielomian $x^d-1$ ma co najwyżej $d$ pierwiastków, a $x^{d(k-1)}+x^{d(k-2)}+\dots +x^d+1$ ma co najwyżej $d(k-1)$. Jednak ich iloczyn $x^{q-1}-1$ ma dokładnie $q-1$ pierwiastków, więc oba wielomiany mają odpowiednio $d$ i $d(k-1)$ pierwiastków.

Fakt, iż $x^d-1$ ma dokładnie $d$ pierwiastków to dokładnie warunek (*).

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

• dowolne ciało skończone ma $p^k$ elementów,

dla pewnej liczby pierwszej $p$ i $k⩾1$,

• grupa addytywna dowolnego ciała $p^k$-elementowego jest izomorficzna z

$({\mathbb{\mathbb{Z}}}_p{)}^n$,

• grupa multyplikatywna dowolnego ciała $p^k$-elementowego jest izomorficzna z

${\mathbb{\mathbb{Z}}}_{p^k-1}$.

W tym kontekście nie jest zbyt zaskakujące, iż dowolne dwa ciała $p^k$-elementowe okażą się być izomorficzne. W dowodzie Obserwacji Uzupelnic obserwacja - cialo skonczone ma p^n elementow| widzieliśmy, że ciało skończone charakterystyki $p$ zawiera ciało izomorficzne z ${\mathbb{\mathbb{Z}}}_p$. Odtąd będziemy więc zakładać, że ${\mathbb{\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(p,r)=1} . Ale również lista

$a,a^p,a^{p^2},a^{p^3},\dots$

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\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},\dots ,a^{p^{s-1}}.$

Stopień elementu $a\ne 0$ ciała charakterystyki $p$ to najmniejsza liczba $d$, dla której $a^{p^s}=a$.

Wniosek

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

Obserwacja

Dla dowolnego ciała $\mathbf{𝐅}$ charakterystyki $p$ oraz $n\in \mathbb{\mathbb{N}}$ mamy:

• jeśli $a,b\in F$, to $(a+b{)}^{p^n}=a^{p^n}+b^{p^n}$,

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

Dowód

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

$(a+b{)}^p=\sum _{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})a^i{b}^{p-i}.$

To, wraz z faktem, że $p$ jako liczba pierwsza dzieli wszystkie współczynniki dwumianowe poza $(\genfrac{}{}{0ex}{}{p}{0})$ i $(\genfrac{}{}{0ex}{}{p}{p})$ oraz, że $\mathbf{𝐅}$ 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}^{i{p}^n}=\sum _i{c}_i{x}^{i{p}^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{\mathbb{Z}}}_p$.

Obserwacja

Niech $\mathbf{𝐅}$ 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{\mathbb{Z}}}_p[x]$ taki, że w ciele $\mathbf{𝐅}$ 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 $\mathbf{𝐅}$, które nie muszą być w ciele ${\mathbb{\mathbb{Z}}}_p$. Aby zobaczyć, że w istocie po wymnożeniu dostajemy współczynniki z ${\mathbb{\mathbb{Z}}}_p$ niech $w_a(x)=\sum _{i=0}^{d-1}{c}_i{x}^i$. Zauważmy, że zgodnie z Obserwacją Uzupelnic pta potega|

$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,\dots ,c_{d-1}\in F$ są pierwiastkami wielomianu $x^p-x\in \mathbf{𝐅}[x]$. Ponieważ wszystkie elementy z ciała ${\mathbb{\mathbb{Z}}}_p\subseteq \mathbf{𝐅}$ są już pierwiastkami tego wielomianu stopnia $p$, to $c_0,\dots ,c_{d-1}$ muszą być wśród nich, a zatem $c_0,\dots ,c_{d-1}\in {\mathbb{\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{\mathbb{Z}}}_p$, to wobec Obserwacji Uzupelnic pta potega| mielibyśmy $p(a^{p^{d-1}})=p(a^{p^{d-2}})=\dots =p(a^{p^2})=p(a^p)=p(a)=0$, czyli

$a^{p^{d-1}},a^{p^{d-2}},\dots ,a^{p^2},a^p,a$

byłyby różnymi pierwiastkami wielomianu $p(x)$, skąd Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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{\mathbb{Z}}}_p$, to wraz z $a$ również potęgi $a^p,a^{p^2},\dots ,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{\mathbb{Z}}}_p$), to $v(x)=c\cdot w_a(x)$ dla pewnego $c\in {\mathbb{\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 $\mathbf{𝐅}=(F,+,\cdot ,0,1)$ rozważmy dwuargumentową relację ${\sim }_{q(x)}$ na zbiorze $F$ zadaną przez

$a(x){\sim }_{q(x)}b(x)\text{<mrow data-mjx-texclass="ORD">wtedyitylkowtedy<mo>,</mo>gdy</mrow>}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 $\mathbf{𝐅}[x]$ generowany wielomianem $q(x)$. Zbiór klas równoważności tworzy więc pierścień ilorazowy $\mathbf{𝐅}[x]/q(x)$.

Twierdzenie

Jeśli $q(x)$ jest nierozkładalnym wielomianem stopnia $k$ nad ciałem ${\mathbb{\mathbb{Z}}}_p$, to pierścień ilorazowy ${\mathbb{\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},\dots ,a_0)$, gdzie $a_i\in {\mathbb{\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{\mathbb{Z}}}_p[x]$ jest największym wspólnym dzielnikiem $a(x)$ i $q(x)$. Z Wniosku Uzupelnic wniosek - wskazniki przy nwd| istnieją $\lambda (x),\mu (x)\in \mathbf{𝐅}[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{\mathbb{Z}}}_p[x]$, to ciało ilorazowe ${\mathbb{\mathbb{Z}}}_p[x]/q(x)$ opisane w Twierdzeniu Uzupelnic obserwacja - konstrukcja cial|.

Twierdzenie

Jeśli dwa skończone ciała są równoliczne, to są izomorficzne.

Dowód

Niech ciała $\mathbf{𝐅}$ i $\mathbf{𝐆}$ mają $p^k$ elementów. Przez $a$ oznaczmy generator grupy multyplikatywnej ciała $\mathbf{𝐅}$. Wtedy stopień elementu $a$ wynosi $k$. Pokażemy, że $\left\{1,a,a^2,\dots ,a^{k-1}\right\}$ stanowi bazę dla przestrzeni wektorowej $\mathbf{𝐅}$ nad ${\mathbb{\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{\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^{\prime }(x)$ stopnia co najwyżej $k-1$ taki, że $w^{\prime }(a)=0$. To jednak na mocy Twierdzenia Uzupelnic wiel nierozkladalny| nie jest możliwe, bo jedyny taki wielomian w ${\mathbb{\mathbb{Z}}}_p[x]$ to $w_a(x)$ stopnia $k$. Ponieważ liniowo niezależny zbiór $\left\{1,a,a^2,\dots ,a^{k-1}\right\}$ ma liczność równa wymiarowi przestrzeni wektorowej $\mathbf{𝐅}$ nad ${\mathbb{\mathbb{Z}}}_p$, to jest jej bazą.

Podobnie, startując od generatora $b$ grupy multyplikatywnej ciała $\mathbf{𝐆}$, dostaniemy bazę $\left\{1,b,b^2,\dots ,b^{k-1}\right\}$ przestrzeni wektorowej $\mathbf{𝐆}$ nad ${\mathbb{\mathbb{Z}}}_p$. Teraz łatwo już sprawdzić, że jedyne odwzorowanie liniowe $F⟶G$ posyłające $a^i$ w $b^i$ jest izomorfizmem nie tylko przestrzeni wektorowych, ale i ciał $\mathbf{𝐅}$ i $\mathbf{𝐆}$.

Twierdzenie Uzupelnic obserwacja - konstrukcja cial| 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{\mathbb{Z}}}_p$. Fakt, iż taki wielomian istnieje dla dowolnej liczby pierwszej $p$ i dowolnego $k\ge 1$ jest nietrywialny i jego dowód przeprowadzimy w serii ćwiczeń do tego wykładu.

Twierdzenie

Dla dowolnej liczby pierwszej $p$ i $k⩾1$ istnieje nierozkładalny wielomian $k$-tego stopnia nad ciałem ${\mathbb{\mathbb{Z}}}_p$.

Wniosek

Dla dowolnej liczby pierwszej $p$ i $k\ge 1$ istnieje dokładnie jedno, z dokładnością do izomorfizmu, ciało $p^n$-elementowe.

Ciało Galois $\mathbf{𝐆}\mathbf{𝐅}(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 $\mathbf{𝐆}\mathbf{𝐅}(4)$ i $\mathbf{𝐆}\mathbf{𝐅}(9)$.

• $\mathbf{𝐆}\mathbf{𝐅}(4)$:

• • $4=2^2$ zatem potrzebujemy nierozkładalnego wielomianu stopnia $2$

nad ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$. W jednym z poprzednich przykładów widzieliśmy, iż jest tylko jeden taki wielomian:

$x^2+x+1.$

• • elementami konstruowanego ciała są $4$ klasy reszt

z dzielenia wielomianów nad ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟐}}$ przez $x^2+x+1$, o reprezentantach: $0,1,x,x+1$.

• • oto tabelki działań dla ciała $\mathbf{𝐆}\mathbf{𝐅}(4)$

$\begin{array}{ccccc}+& 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\end{array}$ $\begin{array}{ccccc}\cdot & 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\end{array}$

• $\mathbf{𝐆}\mathbf{𝐅}(9)$.

• • $9=3^2$, potrzebujemy zatem nierozkładalnego wielomianu stopnia $2$

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

• • • $0^2+2\cdot 0+2=2$,

• • • $1^2+2\cdot 1+2=2$,

• • • $2^2+2\cdot 2+2=1$,

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

• • elementy konstruowanego ciała to $9$ klas reszt z dzielenia wielomianów

nad ${\mathbb{\mathbb{Z}}}_{\mathbf{𝟑}}$ przez $x^2+2x+2$, o reprezentantach: $0,1,2,x,x+1,x+2,2x,2x+1,2x+2$