Informatyka MIMUW

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

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

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

$\begin{align*} x\cdot(y\cdot z) & =(x\cdot y)\cdot z \\ (x+y)\cdot z & =x\cdot z+y\cdot z, \\ x\cdot(y+z) & =x\cdot y+x\cdot z, \\ 1\cdot x & =x\cdot1=x. \end{align*}$
Pierścień ${\mathbf R}=(R,+,\cdot,0,1)$ jest przemienny jeśli $xy=yx$ dla dowolnych $x,y\in R$.

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

Obserwacja 6.3

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

$x\cdot0=0\cdot x=0.$

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

Przykład

• $(\mathbb{Z},+,\cdot,0,1)$ jest pierścieniem przemiennym bez dzielników zera, gdyż:
  • $(\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\neq0$, o ile tylko $a,b\in\mathbb{Z}-{\{ {0} \} }$.

• $(\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 ${\mathbf {Z}_{15}}=(\mathbb{Z}_{15},+,\cdot,0,1)$ mamy $3\cdot5=0$, czyli $3$ i $5$ są dzielnikami zera.

• Niech $M$ będzie zbiorem macierzy liczb całkowitych wymiaru $2\times2$, $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),\qquad \left(\begin{array} {cc}4 & 2 \\ 5 & 5\end{array} \right)\cdot\left(\begin{array} {cc}3 & 1 \\ 0 & 4\end{array}\right )=\left(\begin{array} {cc}12 & 12 \\ 15 & 25\end{array} \right).$

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

$f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0,$

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

Wielomian $a(x)$ nad pierścieniem ${\mathbf R}=(R,+,\cdot,0,1)$ to formalne wyrażenie postaci

$a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0,$

gdzie $n\in\mathbb{N}$, $a_i\in R$ i $a_n\neq0$. Elementy $a_i$ to współczynniki wielomianu. Współczynnik $a_n$ to współczynnik wiodący. Wielomian postaci $a_0$ nazywamy stałą i często utożsamiamy go z odpowiednim elementem pierścienia ${\mathbf R}$. Dopuszczamy również wielomian stały $a_0=0$ (mimo że współczynnik wiodący równy jest $0$) - jest to wielomian zerowy. Symbole $x^i$ należy traktować jedynie jako etykiety pozycji dla współczynników. Wielomiany równie dobrze można zapisywać w tradycyjnej notacji dla ciągów, czyli $(a_n,\ldots,a_0)$.

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

Zbiór wszystkich wielomianów nad pierścieniem ${\mathbf R}$ oznaczamy przez $R[x]$.

Suma wielomianów $a(x),b(x)\in {R}[x]$, dla $a(x)=a_mx^m+\ldots+a_0$, $b(x)=b_nx^n+\ldots+b_0$ to wielomian $a(x)+b(x)\in{R}[x]$ zadany przez

$a(x)+b(x)=(a_k+b_k)x^k+(a_{k-1}+b_{k-1})x^{k-1}+\ldots+(a_0+b_0),$

gdzie $k=\max(m,n)$ oraz niezdefiniowane wartości $a_i$ bądź $b_i$ traktujemy jako $0$.

Iloczyn wielomianów $a(x),b(x)\in {R}[x]$, dla $a(x)=a_mx^m+\ldots+a_0$, $b(x)=b_nx^n+\ldots+b_0$ to wielomian $a(x)\cdot b(x)\in {R}[x]$ zadany przez

$\begin{align*} a(x)\cdot b(x) & =(a_mb_n)x^{m+n}+(a_{m-1}b_n+a_mb_{n-1})x^{m+n-1}+\ldots \\ & +(\sum_{j=0}^ia_jb_{i-j})x^i+\ldots+(a_1b_0+a_0b_1)x+(a_0+b_0). \end{align*}$

Przykład

Suma i iloczyn wielomianów

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

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

$\begin{align*} a(x)+b(x) & =(3+0)x^2+(2+2)x+(0+3)=3x^2+3, \\ a(x)\cdot b(x) & =(3+0)x^3+(0\cdot0+2\cdot2+3\cdot3)x^2+(0\cdot2+2\cdot3)x+(0+3) \\ & =3x^3+x^2+2x+3. \end{align*}$

Zauważmy, że zgodnie z nawykami pomijamy symbole $x^i$, dla $a_i=0$, np.: $3x^2+3$ formalnie oznacza $3x^2+0x+3$.

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

Obserwacja 6.4

Jeśli ${\mathbf R}$ jest pierścieniem (przemiennym), to ${\mathbf R}[x]=(R[x],+,\cdot,0,1)$ jest pierścieniem (przemiennym), gdzie $+$ i $\cdot$ to operacje sumy i iloczynu wielomianów.

Pierścień wielomianów nad pierścieniem ${\mathbf R}$ to pierscień ${\mathbf R[x]}=({R}[x],+,\cdot,0,1)$.

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

Stopień wielomianu $a(x)$ to liczba ${\sf deg}(a(x))$ równa indeksowi jego współczynnika wiodącego. Uwaga: wielomian zerowy ma stopień niezdefiniowany (lub czasem przyjmowany jako $-\infty$).

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

Obserwacja 6.5

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

${\sf deg}(a(x)+b(x))\leq\max({\sf deg}(a(x)),{\sf deg}(b(x)) ).$

Przykład

Suma wielomianów nad skończonym ciałem może mieć stopień silnie mniejszy, niż stopień każdego składnika sumy. Na przykład dla wielomianów pierwszego stopnia $2x+1$ i $3x+1$ nad ciałem $\mathbb{Z}_5$ ich suma $(2x+1)+(3x+1)= 2$ jest wielomianem stałym. Podobnie iloczyn wielomianów nad skończonym pierścieniem może mieć stopień silnie mniejszy od sumy stopni mnożonych wielomianów. Na przykład, nad pierścieniem $\mathbb{Z}_6$ wielomiany $3x^3+2x^2-1$ i $2x^2+1$ są stopnia $2$, podczas gdy ich iloczyn $6x^5+3x^3+4x^4+2x^2-2x^2-1=4x^4+3x^3-1$ jest stopnia $4$.

Obserwacja 6.6

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

${\sf deg}(a(x)\cdot b(x))\leq {\sf deg}(a(x))+{\sf deg}(b(x)).$

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

${\sf deg}(a(x)\cdot b(x))= {\sf deg}(a(x))+{\sf deg}(b(x)).$

Dowód

Pierwsza część wynika wprost z definicji iloczynu wielomianów. Niech teraz współczynnikami wiodącymi wielomianów $a(x),b(x)$ będą odpowiednio $a_m$ i $b_n$ Wtedy najwyższym zdefiniowanym, $(m+n)$-tym, współczynnikiem iloczynu jest $a_mb_n$. Z Obserwacji 6.2 mamy $a_mb_n\neq0$, zatem jest to współczynnik wiodący.

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

Przykład

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

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

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

Obserwacja 6.7

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

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

gdzie $r(x)=0$ lub ${\sf deg}(r(x)) < {\sf deg}(b(x))$.

Dowód

Najpierw wykażemy istnienie takich wielomianów. Dla ustalonego wielomianu $b(x)$ poprowadzimy indukcję względem stopnia wielomianu $a(x)$. Jeśli $a(x)=0$, to $q(x)=r(x)=0$ są szukanymi wielomoanami. Dla ${\sf deg}(a(x)) < {\sf deg}(b(x))$ mamy

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

Gdy zaś ${\sf deg}(a(x))\geq{\sf deg}(b(x))$, zakładamy indukcyjnie, iż dla wszystkich wielomianów stopnia mniejszego niż stopień $a(x)$ istnieją postulowane w tezie wielomiany. Niech

$a(x)=a_mx^m +\ldots+a_0,\qquad b(x)=b_nx^n+\ldots+b_0\qquad$ dla $a_m\neq 0$, $b_n\neq 0$,

oraz

$a'(x)=a(x)-a_mb_n^{-1}x^{m-n}b(x).$

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

$a'_m=a_m-a_mb_n^{-1}b_n=0.$

Zatem ${\sf deg}(a'(x)) < {\sf deg}(a(x))$ (lub $a'(x)=0$) i z założenia indukcyjnego

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

gdzie ${\sf deg}(r(x)) < {\sf deg}(b(x))$ lub $r(x)=0$. Zauważmy, że

$a(x)=(q'(x)+a_mb_n^{-1}x^m)b(x)+r(x),$

czyli szukane wielomany to $q(x)=q'(x)+a_mb_n^{-1}x^m$ i $r(x)$.

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

$a(x)=q_0(x)b(x)+r_0(x)=q_1(x)b(x)+r_1(x),$

gdzie $r_i(x)=0$ lub ${\sf deg}(r_i(x)) < {\sf deg}(b(x))$ dla $i=0,1$. Przekształcając ostatnią równość otrzymujemy

$(q_0(x)-q_1(x))b(x)=r_1(x)-r_0(x).$

Z Obserwacji 6.5 i 6.6, jeśli $q_0(x)\neq q_1(x)$, to ${\sf deg}((q_0(x)-q_1(x))b(x))\geq{\sf deg}(b(x))$. Natomiast dla $r_0(x)\neq r_1(x)$ mamy ${\sf deg}(r_1(x)-r_0(x)) < {\sf deg}(b(x))$. Zatem jedyna możliwość aby równość zaszła to $q_0(x)=q_1(x)$ i $r_0(x)=r_1(x)$.

Wielomiany nad ciałem

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

Wielomian $b(x)$ dzieli (jest dzielnikiem) wielomian $a(x)$ (co zapisujemy $b(x)|a(x)$), jeśli $a(x)=q(x)b(x)$ dla pewnego $q(x)\in{\bf F}[x]$. Mówimy też wtedy, że $q(x)$ jest wielokrotnością $b(x)$.

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

Obserwacja 6.8

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

Dowód

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

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

Obserwacja 6.9

Dla dowolnego ciała ${\bf F}$ i $a(x),b(x)\in{\mathbf F}[x]$ jeśli $a(x)|b(x)$ i $b(x)|a(x)$ to $a(x)=c\cdot b(x)$ dla pewnego $c\in F^*$.

Dowód

Załóżmy, że $a(x)=q(x)b(x)$ i $b(x)=q'(x)a(x)$. Mamy wtedy

$a(x)=q(x)b(x)=q(x)q'(x)a(x).$

Z Obserwacji 6.6 ${\sf deg}(a(x)) ={\sf deg}(q(x))+{\sf deg}(q'(x))+{\sf deg}(a(x))$, czyli ${\sf deg}(q(x))={\sf deg}(q'(x))=0$. Zatem $a(x)=c\cdot b(x)$ dla pewnego $c\in F^*$.

Największy wspólny dzielnik wielomianów $a(x),b(x)\in{\bf F}[x]$ to taki wielomian $g(x)$, że

• $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 F}[x]$ nad ciałem ${\bf F}$ każdy ideał jest główny.

Dowód

Niech $I$ będzie ideałem pierścienia ${\bf F}[x]$. Jeśli $I$ składa się tylko z wielomianu zerowego, to $I$, jako generowany przez ${\{ {0} \} }$, jest główny. Niech teraz $g(x)$ będzie niezerowym wielomianem z $I$ o minimalnym stopniu. Pokażemy, że ${\{ {g(x)} \} }$ generuje ideał $I$. Istotnie, niech $p(x)\in I$. Wydzielając $p(x)$ przez $g(x)$ otrzymujemy

$p(x)=q(x)g(x)+r(x),$

gdzie $r(x)=0$ lub ${\sf deg}(r(x)) < {\sf deg}(g(x))$. Zatem $r(x)\in I$ bo $r(x)=p(x)-q(x)g(x)$ i $p(x),q(x)g(x)\in I$. Ale $g(x)$ ma minimalny stopień wśród wielomianów w $I$. Zatem $r(x)=0$. To oznacza, iż $p(x)=q(x)g(x)$, czyli ${\{ {g(x)} \} }$ generuje $I$.

Obserwacja 6.12

Dowolne dwa wielomiany $a(x),b(x)$ nad ciałem ${\bf F}=(F,+,\cdot,0,1)$ mają największy wspólny dzielnik. Ponadto dla dowolnych $g(x),h(x)$ największych wspólnych dzielników $a(x)$ i $b(x)$ zachodzi $g(x)=c\cdot h(x)$ dla pewnego $c\in F$.

Dowód

Niech $I$ będzie ideałem pierścienia ${\mathbf F[x]}$ generowanym przez ${\{ {a(x),b(x)} \} }$. Wtedy $I={\{ {a'(x)a(x)+b'(x)b(x): a'(x),b'(x)\in{\mathbf F}[x]} \} }$. Z drugiej strony, na podstawie Obserwacji 6.11, ideał $I$ jest główny. Niech więc $g(x)$ generuje $I$ Postulujemy, iż $g(x)$ jest największym wspólnym dzielnikiem $a(x)$ i $b(x)$. Ponieważ $a(x),b(x)\in I$ a $I$ jest zbiorem wielokrotności $g(x)$, to $g(x)|a(x)$ i $g(x)|b(x)$. Ponadto, dla dowolnego $d(x)$ wspólnego dzielnika $a(x)$ i $b(x)$ mamy $d(x)|g(x)$, gdyż $g(x)=a'(x)a(x)+b'(x)b(x)$ dla pewnych $a'(x),b'(x)\in{\mathbf F}[x]$.

Dla dowodu drugiej części załóżmy, że $g(x),h(x)\in{\mathbf F}[x]$ są największymi wspólnymi dzielnikami $a(x)$ i $b(x)$. Wtedy mamy $g(x)|h(x)$ i $h(x)|g(x)$ i z Obserwacji 6.9 $g(x)=c\cdot h(x)$ dla pewnego $c\in F$.

Wniosek 6.13

Dla dowolnych wielomianów $a(x),b(x)$ nad ciałem ${\bf F}$ jeśli $g(x)$ jest największym wspólnym dzielnikiem $a(x),b(x)$, to $g(x)=\lambda(x)a(x)+\mu(x)b(x)$ dla pewnych $\lambda(x),\mu(x)\in{\mathbf F}[x]$.

Dowód

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

Wielomian unormowany nad ciałem ${\bf F}$ to wielomian, którego współczynnik wiodący równy jest $1$. Oczywiście dowolny, niezerowy wielomian $p(x)$ może być przedstawiony w postaci $p(x)=c\cdot u(x)$, gdzie $c\in F$, a $u(x)$ jest wielomianem unormowanym tego samego stopnia co $p(x)$.

Wniosek 6.14

Dla dowolnych wielomianów $a(x),b(x)$ nad ciałem ${\bf F}$ istnieje dokładnie jeden unormowany największy wspólny dzielnik $a(x),b(x)$.

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

Algorytm Euklidesa dla wielomianów.

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

$\begin{align*} a(x) & =b(x)q_0(x)+r_0(x), \\ b(x) & =r_0(x)q_1(x)+r_1(x), \\ r_0(x) & =r_1(x)q_2(x)+r_2(x), \\ & \ldots & \\ r_{n-2} & =r_{n-1}(x)q_n(x)+r_n(x), \\ r_{n-1} & =r_n(x)q_{n+1}(x). \end{align*}$

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

Z ostatniej równości wynika, iż $r_n(x)$ dzieli $r_{n-1}(x)$. Przedostatnia równość implikuje, że $r_n(x)$ dzieli także $r_{n-2}(x)$, itd., zatem $r_n(x)|a(x)$ i $r_n(x)|b(x)$. Ponadto dowolny $d(x)$ dzielnik $a(x)$ i $b(x)$ dzieli $r_0(x)$, bo $r_0(x)=a(x)-q_0(x)b(x)$. Ponieważ $d(x)$ dzieli $b(x)$ i $r_0(x)$, to ma podstawie drugiej równości $d(x)$ dzieli też $r_1(x)$. Idąc wzdłuż kolejnych równości dostajemy $d(x)|r_n(x)$.

Analogicznie jak w przypadku pierścienia liczb całkowitych, algorytm Euklidesa może posłużyć do wskazania wielomianów $\lambda(x),\mu(x)$ takich, że $\lambda(x)a(x)+\mu(x)b(x)=r_n(x)$.

Przykład

Znajdźmy największy wspólny dzielnik wielomianów $5x^3+3x^2+5x+5$ i $3x^2+1$ nad ciałem $\mathbb{Z}_7$ używając algorytmu Euklidesa dla wielomianów:

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

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

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

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

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

$\begin{array} {crrr} & 3x & +2 \\ \hline x+4| & 3x^2 & & +1 \\ & 3x^2 & +5x \\ \hline & & 2x & +1 \\ & & 2x & +1 \\ \hline & & & 0 \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{Z}_7[x]$ z Wniosku 6.13 obliczamy następująco:

$\begin{align*} x+4 & =(5x^3+3x^2+5x+5)-(4x+1)(3x^2+1) \\ & =(5x^3+3x^2+5x+5)+(3x+6)(3x^2+1). \end{align*}$

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

Wielomian nierozkładalny nad ciałem ${\bf F}$ to taki niezerowy wielomian $p(x)$, dla którego $p(x)=a(x)b(x)$ implikuje, że $a(x)$ jest stały lub $b(x)$ jest stały.

Przykład

• dla dowolnego ciała ${\bf F}$ następujące wielomiany nad ${\bf F}$ 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={\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 ${\bf \mathbb{Z}_2}$.
  • 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 ${\bf \mathbb{Z}_2}$:

$x,\qquad x+1.$

• • lista wszystkich iloczynów wielomianów stopnia pierwszego nad ${\bf \mathbb{Z}_2}$, czyli lista wszystkich wielomianów rozkładalnych stopnia $2$:

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

• • tylko jeden wielomian stopnia $2$ nad ${\bf Z_2}$ 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 ${\bf F}$, jeśli $p(x)$ jest nierozkładalny i $p(x)|a(x)b(x)$, to $p(x)|a(x)$ lub $p(x)|b(x)$.

Dowód

Załóżmy, że $p(x)$ nie dzieli $a(x)$. Z nierozkładalności $p(x)$ wiemy, że największym wspólnym dzielnikiem $p(x)$ i $a(x)$ jest dowolna stała, w szczególności $1\in{\bf F}[x]$. Z Wniosku 6.13 mamy $\lambda(x)p(x)+\mu(x)a(x)=1$ dla pewnych $\lambda(x),\mu(x)\in{\bf F}[x]$. Mnożąc obie strony równości przez $b(x)$ otrzymujemy

$\lambda(x)p(x)b(x)+\mu(x)a(x)b(x)=b(x).$

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

Rozkład wielomianu unormowanego $u(x)$ nad ${\bf F}$ na nierozkładalne, unormowane czynniki to przedstawienie go w postaci $u(x)=u_0(x)\cdot\ldots\cdot u_{n-1}(x)$, gdzie wszystkie $u_i\in{\bf F}[x]$ są nierozkładalne i unormowane. Każdy, niezerowy, unormowany wielomian ma taki rozkład - wystarczy rozbijać kolejne rozkładalne czynniki na iloczyn wielomianów o mniejszym stopniu (wszystkie będą unormowane).

Rozkład dowolnego wielomianu $p(x)$ nad ciałem ${\bf F}=(F,+,\cdot,0,1)$ to przedstawienie go w postaci $p(x)=c\cdot u(x)$, gdzie $c\in F$ a $u(x)$ jest wielomianem unormowanym, i później rozłożenie $u(x)$ na nierozkładalne, unormowane czynniki.

Obserwacja 6.16

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

Dowód

Indukcja po stopniu wielomianu $u(x)$. Dla ${\sf deg}(u(x))\leq1$ wielomian $u(x)$ jest nierozkładalny i sam stanowi swój jedyny rozkład. Rozważmy zatem dowolny $u(x)$ stopnia $n+1$ i rozważmy jego dwa rozkłady na nierozkładalne czynniki

$a_0(x)\cdot\ldots\cdot a_{m-1}(x)=u(x)=b_0(x)\cdot\ldots\cdot b_{n-1}(x).$

Widzimy, iż $a_0(x)|b_0(x)\cdot\ldots\cdot b_{n-1}(x)$. Z nierozkładalności $a_0(x)$ i lematu Euklidesa mamy, iż $a_0(x)|b_i(x)$ dla pewnego $i$. Z nierozkładalności $b_i(x)$ i faktu, iż $a_0(x)$ i $b_i(x)$ są unormowane otrzymujemy $a_0(x)=b_i(x)$. Dzieląc obie strony równości przez ten wielomian $a_0(x)$ otrzymujemy wielomian istotnie mniejszego stopnia. Zatem z założenia indukcyjnego ma on jednoznaczny rozkład, co kończy dowód.

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

Ewaluacja wielomianu $p(x)=p_nx^n+\ldots+p_0$ nad ciałem ${\bf F}=(F,+,\cdot,0,1)$ to funkcja $\overline{p}:F\longrightarrow F$ zadana przez

$\overline{p}(x)=p_nx^n+\ldots+p_1x+p_0.$

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

Przykład

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

$a(x)=x^2,\qquad b(x)=x^4+x^3+x^2,$

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

Zatem $a(x)\neq b(x)$ ale $\overline{a}(x)=\overline{b}(x)$.

Obserwacja 6.17 [Bezout]

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

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

• $\overline{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{\bf F}[x]$. Ewaluacja wielomianu $p(x)$ na elemencie $c$ daje $\overline{p}(c)=\overline{q}(c)\cdot(c-c)=0$.

Dla dowodu implikacji odwrotnej załóżmy, że $\overline{p}(c)=0$. Dzieląc $p(x)$ przez $x-c$ otrzymujemy

$p(x)=q(x)(x-c)+r(x),$

dla pewnych $q(x),r(x)$ gdzie $r(x)=0$ lub ${\sf deg}(r(x)) < {\sf deg}(x-c)=1$. Zatem $r(x)$ jest wielomianem stałym i jego ewaluacja $\overline{r}$ to funkcja stała, przyjmująca zawsze tę samą wartość $r \in F$. Wtedy

$0=\overline{p}(c)=\overline{q}(c)\cdot(c-c)+r =r,$

czyli $r(x)$ jest wielomianem zerowym i $x-c|p(x)$.

Pierwiastek wielomianu $p(x)$ nad ciałem ${\bf F}$ to taki element $c\in F$, że $\overline{p}(c)=0$.

Przykład

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

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

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

• najpierw sprowadzamy nasz wielomian do postaci unormowanej:

$\begin{align*} 3x^2+12x+8 & =3\cdot(3^{-1}\cdot3x^2+3^{-1}\cdot12x+3^{-1}\cdot8) \\ & =3(x^2+4x+7) \end{align*}$

• 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{Z}_{13}$:
  • $0^2+4\cdot0+7=7$,
  • $1^2+4\cdot1+7=12$,
  • $2^2+4\cdot2+7=4$,
  • $3^2+4\cdot3+7=2$,
  • $4^2+4\cdot4+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\cdot5+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 ${\bf F}=(F,+,\cdot,0,1)$ ma co najwyżej $n$ pierwiastków.

Dowód

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

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

dla pewnego $c\in F$ i unormowanego wielomianu $q(x)$. Ale wtedy Obserwacja 6.6 daje $n={\sf deg}(p(x))={\sf deg}((x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x))\geq m$.