Matematyka dyskretna 2/Ćwiczenia 6: Ciała skończone

From Studia Informatyczne

Ciała skończone

Ćwiczenie 1

Udowodnij, że jeśli \displaystyle d|n, to dla dowolnego \displaystyle p mamy \displaystyle x^{p^d-1}|x^{p^n-1}.

Wskazówka

Wykorzystaj rozkład


\displaystyle x^n-1=(x^d-1)(x^{(q-1)d}+x^{(q-2)d}+\ldots+x^d+1),


gdzie \displaystyle n=qd.

Rozwiązanie

Łatwo pokazać, że jeśli \displaystyle d|n, czyli np. \displaystyle n=qd, to


\displaystyle x^n-1=(x^d-1)(x^{(q-1)d}+x^{(q-2)d}+\ldots+x^d+1),


skąd \displaystyle x^d-1|x^n-1. Ewaluując wskazane wielomiany dla \displaystyle x=p otrzymujemy, że \displaystyle p^{d-1}|p^{n-1}. Korzystając raz jeszcze z podanego rozkładu, ale dla \displaystyle d:=p^{d-1} oraz \displaystyle n:=p^{n-1}, dostajemy \displaystyle x^{p^d}-1|x^{p^n}-1.

Ćwiczenie 2

Pochodna wielomianu \displaystyle f(x)=f_0+f_1x+f_2x^2+\ldots+f_nx^n to wielomian \displaystyle f'(x)=f_1+2f_2x+\ldots+nf_nx^{n-1}.

Pokaż, że:


\displaystyle \aligned (f+g)'(x)&=f'(x)+g'(x),\\ (fg)'(x)&=f'(x)g(x)+f(x)g'(x). \endaligned


Wskazówka

Policz i porównaj współczynniki wielomianów \displaystyle (f+g)'(x) z \displaystyle f'(x)+g'(x) oraz \displaystyle (fg)'(x) z \displaystyle f'(x)g(x)+f(x)g'(x).

Rozwiązanie

Niech


\displaystyle \aligned f(x)&=f_0+f_1x+f_2x^2+\ldots+f_nx^n,\\ g(x)&=g_0+g_1x+g_2x^2+\ldots+g_nx^n. \endaligned


Wielomiany są równe gdy mają te same współczynniki. Liczymy więc \displaystyle k-te współczynniki kolejnych wielomianów dla sumy:

  • \displaystyle (f+g)_k=f_k +g_k,
  • \displaystyle (f+g)'_k=(k+1)(f_{k+1}+g_{k+1}),
  • \displaystyle f'_k=(k+1)f_{k+1},
  • \displaystyle g'_k=(k+1)g_{k+1},
  • \displaystyle f'_k+g'_k =(k+1)(f_{k+1}+g_{k+1})

oraz dla iloczynu:

  • \displaystyle (fg)_k = \sum_{i=0}^k f_i g_{k-i},
  • \displaystyle (fg)'_k= (k+1)\cdot\sum_{i=0}^{k+1}f_ig_{k+1-i},
  • \displaystyle (f'g)_k= \sum_{i=0}^k (i+1)f_{i+1} g_{k-i},
  • \displaystyle (fg')_k= \sum_{i=0}^k (k+1-i)f_i g_{k+1-i},
\displaystyle \aligned (f'g+fg')_k &=\sum_{i=0}^k (i+1)f_{i+1} g_{k-i} + \sum_{i=0}^k (k+1-i)f_i g_{k+1-i}\\ &=\sum_{i=1}^{k+1} i f_i g_{k+1-i}+\sum_{i=0}^k (k+1-i)f_i g_{k+1-i}\\ &=(k+1)\sum_{i=0}^{k+1} f_i g_{k+1-i}. \endaligned


Ćwiczenie 3

Pokaż, że rozkład wielomianu \displaystyle x^{p^n}-x nad ciałem \displaystyle {\bf \mathbb{Z}}_p składa się ze wszystkich nierozkładalnych, unormowanych wielomianów stopnia \displaystyle d, gdzie \displaystyle d|n. Każdy z takich wielomianów pojawia się dokładnie raz i wielomiany te stanowią wszystkie czynniki rozkładu \displaystyle x^{p^n}-x.

Wskazówka

Spróbuj pokazać kolejno:

  • jeśli \displaystyle d \geq 2 jest stopniem nierozkładalnego i unormowanego wielomianu \displaystyle f(x)\in \mathbb{Z}_p[x], to \displaystyle f(x) dzieli \displaystyle x^{p^d}-1,
  • jeśli \displaystyle d jest dzielnikiem \displaystyle n, to dowolny nierozkładalny wielomian stopnia \displaystyle d jest dzielnikiem wielomianu \displaystyle x^{p^n}-x w pierścieniu \displaystyle {\bf \mathbb{Z}}_p[x],
  • stopień nierozkładalnego wielomianu dzielącego wielomian \displaystyle x^{p^n}-x w pierścieniu \displaystyle {\bf \mathbb{Z}}_p[x], sam jest dzielnikiem \displaystyle n,
  • w rozkładzie wielomianu \displaystyle x^{p^n}-x na iloczyn wielomianów nierozkładalnych z pierścienia \displaystyle {\bf \mathbb{Z}}_p[x] wszystkie czynniki sa różne.

Rozwiązanie

Dowód podzielimy na cztery części zgodnie ze Wskazówką:

  • jeśli \displaystyle d\geq 2 jest stopniem nierozkładalnego wielomianu \displaystyle f(x)\in \mathbb{Z}_p[x], to \displaystyle f(x) dzieli \displaystyle x^{p^d}-1:

Niech \displaystyle f(x) będzie nierozkładalnym wielomianem stopnia \displaystyle d\geqslant 2. Na podstawie twierdzenia opisującego konstrukcję ciał o \displaystyle p^k elementach wiemy, że pierścień ilorazowy \displaystyle \mathbb{Z}_p[x]/f(x) jest \displaystyle p^d-elementowym ciałem. Jego elementy to klasy równoważności reszt wielomianów w \displaystyle \mathbb{Z}_p[x]/f(x) z dzielenia przez \displaystyle f(x):


\displaystyle [0]_{f(x)},[h_1(x)]_{f(x)},\ldots,[h_{p^d-1}(x)]_{f(x)}.


Ponieważ \displaystyle \mathbb{Z}_p[x]/f(x) jest ciałem, to klasy \displaystyle [xh_1(x)]_{f(x)},\ldots,[xh_{p^d-1}(x)]_{f(x)} są różne i niezerowe. Zatem, podobnie jak w dowodzie Małego Twierdzenia Fermata, mamy


\displaystyle [xh_1(x)]_{f(x)}\cdot\ldots\cdot[xh_{p^d-1}(x)]_{f(x)}=[h_1(x)]_{f(x)}\cdot\ldots\cdot[h_{p^d-1}(x)]_{f(x)}


czyli


\displaystyle [x^{p^d-1}]_{f(x)}[h_1(x)]_{f(x)}\cdot\ldots\cdot[h_{p^d-1}(x)]_{f(x)}=[h_1(x)]_{f(x)}\cdot\ldots\cdot[h_{p^d-1}(x)]_{f(x)},


co oznacza, że \displaystyle [x^{p^d}-1]_{f(x)}=[0]_{f(x)} lub równoważnie \displaystyle f(x)|x^{p^d}-1.

  • jeśli \displaystyle d jest dzielnikiem \displaystyle n, to dowolny nierozkładalny wielomian stopnia \displaystyle d jest dzielnikiem wielomianu \displaystyle x^{p^n}-x w pierścieniu \displaystyle {\bf \mathbb{Z}}_p[x]:

Oczywiście \displaystyle x|x^{p^n}-x bo \displaystyle x^{p^n}-x=x(x^{p^n-1}-1). Rozważmy dowolny, inny, unormowany, nierozkładalny wielomian stopnia \displaystyle 1, czyli \displaystyle x-c dla \displaystyle c\neq0. Z Małego Twierdzenia Fermata mamy \displaystyle c^{p-1}=1 dla \displaystyle {\bf \mathbb{Z}}_p-\left\lbrace 0 \right\rbrace, tzn. \displaystyle c jest pierwiastkiem \displaystyle x^{p-1}-1. Twierdzenie Bezout daje więc \displaystyle x-c|x^{p-1}-1. Z ćwiczenia 1 wiemy, że \displaystyle x^{p-1}-1|x^{p^n}-1 więc \displaystyle x-c|x^{p^n}-1, dla dowolnego \displaystyle c\in\mathbb{Z}_p.

Niech teraz \displaystyle f(x) będzie nierozkładalnym wielomianem stopnia \displaystyle d\geqslant 2.

Na podstawie punktu pierwszego wiemy, że \displaystyle f(x)|x^{p^d}-1. Łącząc to z podzielnością \displaystyle x^{p^d}-1|x^{p^n}-1, otrzymaną w ćwiczeniu 1, dostajemy \displaystyle f(x)|x^{p^n}-1.

  • stopień nierozkładalnego wielomianu dzielącego wielomian \displaystyle x^{p^n}-x w pierścieniu \displaystyle \mathbb{Z}_p[x], sam jest dzielnikiem \displaystyle n:

Rozważmy dowolny unormowany, nierozkładalny dzielnik \displaystyle f(x) wielomianu \displaystyle x^{p^n}-x o stopniu \displaystyle d\geqslant2. Niech \displaystyle n=qd+r, gdzie \displaystyle 0\leqslant r<d. Udowodnimy, że \displaystyle r=0. Na podstawie punktu pierwszego wiemy, że \displaystyle f(x)|x^{p^d}-x w pierścieniu \displaystyle \mathbb{Z}_p[x], czyli wielomiany \displaystyle x^{p^d} i \displaystyle x dają te same reszty modulo \displaystyle \sim_{f(x)}, czyli są równe w ciele \displaystyle \mathbb{Z}_p[x]/f(x). Mamy więc


\displaystyle x^{p^{qd}} = \left( x^{p^d} \right)^{p^{(q-1)d}} \sim_{f(x)}  x^{p^{(q-1)d}} = \left( x^{p^d} \right)^{p^{(q-2)d}} \sim_{f(x)} \ldots \sim_{f(x)} x^{p^d} \sim_{f(x)}x


skąd


\displaystyle x \sim_{f(x)} x^{p^n} = x^{p^{qd+r}} = \left( x^{p^{qd}} \right)^{p^r} \sim_{f(x)} x^{p^r},


czyli \displaystyle [x^{p^r}]_{f(x)}=[x]_{f(x)}. W konsekwencji, dla dowolnego wielomianu \displaystyle h(x)\in \mathbb{Z}_p[x] mamy \displaystyle [h(x)]_{f(x)}=[h(x^{p^r})]_{f(x)}. Z drugiej strony, ponieważ \displaystyle h(x) ma współczynniki w ciele \displaystyle \mathbb{Z}_p, to \displaystyle h(x^{p^r})=h(x)^{p^r} w \displaystyle {\bf \mathbb{Z}_p}[x]. A zatem dla dowolnego \displaystyle h(x)\in \mathbb{Z}_p[x]


\displaystyle [h(x)]_{f(x)}=[h(x)]^{p^r}_{f(x)},


co oznacza, że każdy spośród \displaystyle p^d elementów ciała \displaystyle \mathbb{Z}_p[x]/f(x) jest pierwiastkiem wielomianu \displaystyle X^{p^r}-X=0. Gdyby więc \displaystyle r>0, to wielomian \displaystyle X^{p^r}-X=0 jest niezerowy i mógłby mieć co najwyżej \displaystyle p^r<p^d pierwiastków. Ta sprzeczność pokazuje, że \displaystyle r=0 i w konsekwencji, że stopień \displaystyle d dowolnego nierozkładalnego dzielnika \displaystyle f(x)|x^{p^n}-x spełnia \displaystyle d|n.

  • w rozkładzie wielomianu \displaystyle x^{p^n}-x na iloczyn wielomianów nierozkładalnych z pierścienia \displaystyle {\bf \mathbb{Z}}_p[x] wszystkie czynniki sa różne.

Dla dowodu niewprost załóżmy, że \displaystyle f(x) jest nierozkładalnym wielomianem o niezerowym stopniu oraz


\displaystyle x^{p^n}-x=f(x)^2q(x).


Porównując pochodne obu wielomianów dostajemy


\displaystyle p^nx^{p^n}-1=2f(x)f'(x)q(x)+f^2(x)q'(x)= f(x)\cdot\left( 2f'(x)q(x)+f(x)q'(x) \right).


Pamiętając, że \displaystyle p^n=0 w ciele \displaystyle  \mathbb{Z}_p otrzymujemy, że \displaystyle f(x)|-1. To zaś może być prawdą tylko wtedy, gdy \displaystyle f(x) jest wielomianem stałym.

Ćwiczenie 4

Pokaż, że dla dowolnej liczby pierwszej \displaystyle p i dowolnego \displaystyle n>1 w pierscieniu \displaystyle \mathbb{Z}_p[x] istnieje unormowany, nierozkładalny (nad \displaystyle \mathbb{Z}_p) wielomian stopnia \displaystyle n.

Wskazówka

Niech \displaystyle N_n(p) będzie liczba nieredukowalnych, unormowanych wielomianów stopnia \displaystyle n w \displaystyle \mathbb{Z}_p[x]. Wykorzystując ćwiczenie 3 skonstruuj zależność z uwikłanymi wartościami \displaystyle N_d(p), gdzie \displaystyle d przebiega wszystkie dzielniki liczby \displaystyle n. Później użyj wzoru inwersyjnego Mobiusa do rozwikłania wartości \displaystyle N_n(p)

Rozwiązanie

Przez \displaystyle N_n(p) oznaczmy liczbę nieredukowalnych, unormowanych wielomianów stopnia \displaystyle n w pierścieniu \displaystyle \mathbb{Z}_p[x]. Rozważmy rozkład wielomianu \displaystyle x^{p^n}-x w pierścieniu \displaystyle \mathbb{Z}_p[x] na wielomiany nierozkładalne. Z ćwiczenia 3 wiemy, że w rozkładzie tym pojawia się dokładnie \displaystyle N_d(p) czynników stopnia \displaystyle d, gdy \displaystyle d|n, oraz że nie ma czynników innych stopni. Ponieważ stopnie wszystkich czynników rozkładu muszą się sumować do \displaystyle p^n, mamy


\displaystyle p^n=\sum_{d|n}dN_d(p).


Wzór inwersyjny Mobiusa daje wtedy:


\displaystyle nN_n(p)=\sum_{d|n}\mu(d)p^{\frac{n}{d}},


czyli


\displaystyle \aligned N_n(p) =\frac{1}{n}\sum_{d|n}\mu(d)p^{\frac{n}{d}}\\ \geqslant&\frac{1}{n}(p^n-(p^{n-1}+p^{n-2}+\ldots+1))\\ =\frac{1}{n}(p^n-\frac{p^{n-1}}{p-1})>0. \endaligned


Ponieważ \displaystyle N_n(p) przyjmuje wartości całkowite


\displaystyle N_n(p)\geqslant1,


co było do pokazania.

Ćwiczenie 5

Niech \displaystyle (Z_n^*,\cdot,1) będzie grupą elementów odwracalnych względem mnożenia modulo \displaystyle n, czyli \displaystyle \mathbb{Z}_n^*=\left\lbrace m:1\leqslant m\leqslant n,\ m\perp n \right\rbrace. Pokaż, że gdy \displaystyle p jest liczbą pierwszą, to grupa \displaystyle \mathbb{Z}_{p^2}^* jest cykliczna.

Wskazówka

Gdy \displaystyle g\in \left\lbrace 1,2,\ldots, p-1 \right\rbrace jest generatorem grupy multyplikatywnej ciała \displaystyle \mathbb{Z}_p, to \displaystyle g lub \displaystyle (p+1)g generuje grupę \displaystyle \mathbb{Z}_{p^2}^*.

Rozwiązanie

Niech \displaystyle g będzie generatorem grupy multyplikatywnej ciała \displaystyle \mathbb{Z}_p. Mamy zatem


\displaystyle g^{p-1}\equiv_p 1,


czyli \displaystyle \mathbb{Z}_p^2 element \displaystyle g^{p-1} ma jedną z dwu wartości: \displaystyle 1 lub \displaystyle p+1. Przeanalizujemy najpierw ten drugi przypadek:

  • \displaystyle g^{p-1}\equiv_{p^2}p+1.

Zbadajmy rząd elementu \displaystyle g w \displaystyle \mathbb{Z}_{p^2}^*. Załóżmy, że \displaystyle g^j\equiv_{p^2}1. Oczywiście wtedy \displaystyle g^j\equiv_p1, czyli \displaystyle p-1|j. A więc rząd \displaystyle g jest wielokrotnością \displaystyle p-1. Z drugiej strony rząd elementu \displaystyle g musi dzielić rząd grupy \displaystyle \mathbb{Z}_{p^2}^* tzn. liczbę \displaystyle \varphi(p^2)=p(p-1). Jako wielokrotność liczby \displaystyle p, rząd elementu \displaystyle g może więc wynosić albo \displaystyle p-1 albo \displaystyle p(p-1). Ale skoro, zgodnie z założeniem tego przypadku, \displaystyle g^{p-1}\not\equiv_{p^2}1, to \displaystyle g ma rząd \displaystyle p(p-1) w \displaystyle \mathbb{Z}_{p^2}^*, czyli \displaystyle \mathbb{Z}_{p^2}^* jest cykliczna.

  • \displaystyle g^{p-1}\equiv_{p^2}1.

W tym przypadku rozważmy element \displaystyle (p+1)g. Mamy


\displaystyle \aligned (g(p+1))^{p-1} &\equiv_p& g^{p-1}(p+1)^{p-1}\\ &\equiv_p&  1\cdot\left( {p-1\choose0}+{p-1\choose1}p+{p-1\choose2}p^2+\ldots \right)\\ &\equiv_p&  1 \endaligned


oraz


\displaystyle \aligned(g(p+1))^{p-1} &\equiv_{p^2}& g^{p-1}(p+1)^{p-1}\\ &\equiv_{p^2}& 1\cdot\left( {p-1\choose0}+{p-1\choose1}p+{p-1\choose2}p^2+\ldots \right)\\ &\equiv_{p^2}& 1+(p-1)p\\ &\equiv_{p^2}& 1-p. \endaligned


Korzystając z wyliczonych właśnie reszt \displaystyle p-1 potęgi liczby \displaystyle g_1 =g(p+1) modulo \displaystyle p i \displaystyle p^2 można argumentować jak w pierwszym przypadku i dostać, że \displaystyle g_1 ma rząd \displaystyle p(p-1) w \displaystyle \mathbb{Z}_{p^2}^*. A zatem i w tym przypadku \displaystyle \mathbb{Z}_{p^2}^* jest cykliczna.