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 6.1

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 6.2

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$

$\begin{array}{rl}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\cdot 1=x.\end{array}$

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 6.3

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

$\begin{array}{rl}a(x)\cdot b(x)& =(a_m{b}_n)x^{m+n}+(a_{m-1}{b}_n+a_m{b}_{n-1})x^{m+n-1}+\dots \\ & +(\sum _{j=0}^i{a}_j{b}_{i-j})x^i+\dots +(a_1{b}_0+a_0{b}_1)x+(a_0+b_0).\end{array}$

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:

$\begin{array}{rl}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\cdot 0+2\cdot 2+3\cdot 3)x^2+(0\cdot 2+2\cdot 3)x+(0+3)\\ & =3x^3+x^2+2x+3.\end{array}$

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{𝐑}$ 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 $\mathsf{d}\mathsf{e}\mathsf{g}(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 6.5

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

$\mathsf{d}\mathsf{e}\mathsf{g}(a(x)+b(x))⩽\max (\mathsf{d}\mathsf{e}\mathsf{g}(a(x)),\mathsf{d}\mathsf{e}\mathsf{g}(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{\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 6.6

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

$\mathsf{d}\mathsf{e}\mathsf{g}(a(x)\cdot b(x))\le \mathsf{d}\mathsf{e}\mathsf{g}(a(x))+\mathsf{d}\mathsf{e}\mathsf{g}(b(x))$

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

$\mathsf{d}\mathsf{e}\mathsf{g}(a(x)\cdot b(x))=\mathsf{d}\mathsf{e}\mathsf{g}(a(x))+\mathsf{d}\mathsf{e}\mathsf{g}(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 6.2 mamy $a_m{b}_n\ne 0$, 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{ℝ}$.

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 6.7

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 $\mathsf{d}\mathsf{e}\mathsf{g}(r(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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 $\mathsf{d}\mathsf{e}\mathsf{g}(a(x))<\mathsf{d}\mathsf{e}\mathsf{g}(b(x))$ mamy

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

Gdy zaś $\mathsf{d}\mathsf{e}\mathsf{g}(a(x))⩾\mathsf{d}\mathsf{e}\mathsf{g}(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_m{x}^m+\dots +a_0,b(x)=b_n{x}^n+\dots +b_0$ dla $a_m\ne 0$, $b_n\ne 0$,

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 $\mathsf{d}\mathsf{e}\mathsf{g}(a^{\prime }(x))<\mathsf{d}\mathsf{e}\mathsf{g}(a(x))$ (lub $a^{\prime }(x)=0$) i z założenia indukcyjnego

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

gdzie $\mathsf{d}\mathsf{e}\mathsf{g}(r(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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 $\mathsf{d}\mathsf{e}\mathsf{g}(r_i(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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)\ne q_1(x)$, to $\mathsf{d}\mathsf{e}\mathsf{g}((q_0(x)-q_1(x))b(x))⩾\mathsf{d}\mathsf{e}\mathsf{g}(b(x))$. Natomiast dla $r_0(x)\ne r_1(x)$ mamy $\mathsf{d}\mathsf{e}\mathsf{g}(r_1(x)-r_0(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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 6.8

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 6.9

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 6.6 $\mathsf{d}\mathsf{e}\mathsf{g}(a(x))=\mathsf{d}\mathsf{e}\mathsf{g}(q(x))+\mathsf{d}\mathsf{e}\mathsf{g}(q^{\prime }(x))+\mathsf{d}\mathsf{e}\mathsf{g}(a(x))$, czyli $\mathsf{d}\mathsf{e}\mathsf{g}(q(x))=\mathsf{d}\mathsf{e}\mathsf{g}(q^{\prime }(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 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{𝐅}[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 $\mathsf{d}\mathsf{e}\mathsf{g}(r(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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 6.12

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 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^{\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 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 $\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 6.12 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 6.14

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ń:

$\begin{array}{rl}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),\\ & \dots & \\ r_{n-2}& =r_{n-1}(x)q_n(x)+r_n(x),\\ r_{n-1}& =r_n(x)q_{n+1}(x).\end{array}$

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 6.13 obliczamy następująco:

$\begin{array}{rl}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{array}$

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 6.6),
  • wszystkie wielomiany stopnia $1$ (tzw. wielomiany liniowe), gdyż dla dowolnego liniowego $p(x)$ jeśli $p(x)=a(x)b(x)$, to $1=\mathsf{d}\mathsf{e}\mathsf{g}(p(x))=\mathsf{d}\mathsf{e}\mathsf{g}(a(x))+\mathsf{d}\mathsf{e}\mathsf{g}(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 6.15 [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 6.13 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 6.16

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 $\mathsf{d}\mathsf{e}\mathsf{g}(u(x))⩽1$ 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}{rclr}\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 6.17 [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 $\mathsf{d}\mathsf{e}\mathsf{g}(r(x))<\mathsf{d}\mathsf{e}\mathsf{g}(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:

$\begin{array}{rl}3x^2+12x+8& =3\cdot (3^{-1}\cdot 3x^2+3^{-1}\cdot 12x+3^{-1}\cdot 8)\\ & =3(x^2+4x+7)\end{array}$

• z Obserwacji 6.16 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 6.17. 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 6.18

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 6.17 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 6.6 daje $n=\mathsf{d}\mathsf{e}\mathsf{g}(p(x))=\mathsf{d}\mathsf{e}\mathsf{g}((x-c_0)\cdot \dots \cdot (x-c_{m-1})q(x))\ge 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 $\left|F\right|$.

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 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=(\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ą 6.2.

Obserwacja 6.20

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 $\left|F\right|=p^k$.

Dowód

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

$\begin{array}{rl}\mathbf{𝟐}& =1+1,\\ \mathbf{𝟑}& =1+1+1,\\ & \dots & \\ \mathbf{𝐩}\mathbf{-}\mathbf{𝟏}& =\underset{prazy}{\underbrace{1+\dots +1}}.\end{array}$

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 6.21

Grupa multyplikatywna ciała skończonego jest cykliczna.

Dowód

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

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

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

$f^{q-1}=1$ 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)}+\dots +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)}+\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 6.20 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 $\mathsf{N}\mathsf{W}\mathsf{D}(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 $\mathsf{N}\mathsf{W}\mathsf{D}(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 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 $\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 6.24

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ą 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,\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 6.23 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 $\mathsf{d}\mathsf{e}\mathsf{g}(p(x))=d=\mathsf{d}\mathsf{e}\mathsf{g}(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{ 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 $\mathbf{𝐅}[x]$ generowany wielomianem $q(x)$. Zbiór klas równoważności tworzy więc pierścień ilorazowy $\mathbf{𝐅}[x]/q(x)$.

Twierdzenie 6.25

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 6.13 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 6.25.

Twierdzenie 6.26

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

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

Wniosek 6.28

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$