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

Ciała skończone

Ćwiczenie 1

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

Wskazówka

Wykorzystaj rozkład

$x^n-1=(x^d-1)(x^{(q-1)d}+x^{(q-2)d}+\dots +x^d+1)$

gdzie $n=qd$.

Rozwiązanie

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

$x^n-1=(x^d-1)(x^{(q-1)d}+x^{(q-2)d}+\dots +x^d+1)$

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

Ćwiczenie 2

Pochodna wielomianu $f(x)=f_0+f_{1}x+f_2{x}^2+\dots +f_n{x}^n$ to wielomian $f^{\prime }(x)=f_1+2f_{2}x+\dots +n{f}_n{x}^{n-1}$.

Pokaż, że:

$\begin{array}{rl}(f+g{)}^{\prime }(x)& =f^{\prime }(x)+g^{\prime }(x),\\ (fg{)}^{\prime }(x)& =f^{\prime }(x)g(x)+f(x)g^{\prime }(x)\end{array}$

Wskazówka

Policz i porównaj współczynniki wielomianów $(f+g{)}^{\prime }(x)$ z $f^{\prime }(x)+g^{\prime }(x)$ oraz $(fg{)}^{\prime }(x)$ z $f^{\prime }(x)g(x)+f(x)g^{\prime }(x)$.

Rozwiązanie

Niech

$\begin{array}{rl}f(x)& =f_0+f_{1}x+f_2{x}^2+\dots +f_n{x}^n,\\ g(x)& =g_0+g_{1}x+g_2{x}^2+\dots +g_n{x}^n\end{array}$

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

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

oraz dla iloczynu:

• $(fg{)}_k=\sum _{i=0}^k{f}_i{g}_{k-i}$,
• $(fg){\text{'}}_k=(k+1)\cdot \sum _{i=0}^{k+1}{f}_i{g}_{k+1-i}$,
• $(f^{\prime }g{)}_k=\sum _{i=0}^k(i+1)f_{i+1}{g}_{k-i}$,
• $(f{g}^{\prime }{)}_k=\sum _{i=0}^k(k+1-i)f_i{g}_{k+1-i}$,

$\begin{array}{rl}(f^{\prime }g+f{g}^{\prime }{)}_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}\end{array}$

Ćwiczenie 3

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

Wskazówka

Spróbuj pokazać kolejno:

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

Rozwiązanie

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

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

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

$[0{]}_{f(x)},[h_1(x){]}_{f(x)},\dots ,[h_{p^d-1}(x){]}_{f(x)}$

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

$[x{h}_1(x){]}_{f(x)}\cdot \dots \cdot [x{h}_{p^d-1}(x){]}_{f(x)}=[h_1(x){]}_{f(x)}\cdot \dots \cdot [h_{p^d-1}(x){]}_{f(x)}$

czyli

$[x^{p^d-1}{]}_{f(x)}[h_1(x){]}_{f(x)}\cdot \dots \cdot [h_{p^d-1}(x){]}_{f(x)}=[h_1(x){]}_{f(x)}\cdot \dots \cdot [h_{p^d-1}(x){]}_{f(x)}$

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

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

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

Niech teraz $f(x)$ będzie nierozkładalnym wielomianem stopnia $d⩾2$. Na podstawie punktu pierwszego wiemy, że $f(x)|x^{p^d}-1$. Łącząc to z podzielnością $x^{p^d}-1|x^{p^n}-1$, otrzymaną w ćwiczeniu 1, dostajemy $f(x)|x^{p^n}-1$.

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

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

$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)}\dots {\sim }_{f(x)}{x}^{p^d}{\sim }_{f(x)}x$

skąd

$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 $[x^{p^r}{]}_{f(x)}=[x{]}_{f(x)}$. W konsekwencji, dla dowolnego wielomianu $h(x)\in {\mathbb{\mathbb{Z}}}_p[x]$ mamy $[h(x){]}_{f(x)}=[h(x^{p^r}){]}_{f(x)}$. Z drugiej strony, ponieważ $h(x)$ ma współczynniki w ciele ${\mathbb{\mathbb{Z}}}_p$, to $h(x^{p^r})=h(x{)}^{p^r}$ w ${\mathbb{\mathbb{Z}}}_{\mathbf{𝐩}}[x]$. A zatem dla dowolnego $h(x)\in {\mathbb{\mathbb{Z}}}_p[x]$

$[h(x){]}_{f(x)}=[h(x){]}_{f(x)}^{p^r}$

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

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

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

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

Porównując pochodne obu wielomianów dostajemy

$p^n{x}^{p^n}-1=2f(x)f^{\prime }(x)q(x)+f^2(x)q^{\prime }(x)=f(x)\cdot (2f^{\prime }(x)q(x)+f(x)q^{\prime }(x)).$

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

Ćwiczenie 4

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

Wskazówka

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

Rozwiązanie

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

$p^n=\sum _{d|n}d{N}_d(p).$

Wzór inwersyjny Mobiusa daje wtedy:

$n{N}_n(p)=\sum _{d|n}\mu (d)p^{\frac{n}{d}},$

czyli

$\begin{array}{r}{N}_n(p)=\frac{1}{n}\sum _{d|n}\mu (d)p^{\frac{n}{d}}\\ ⩾& \frac{1}{n}(p^n-(p^{n-1}+p^{n-2}+\dots +1))\\ =\frac{1}{n}(p^n-\frac{p^{n-1}}{p-1})>0.\end{array}$

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

$N_n(p)⩾1,$

co było do pokazania.

Ćwiczenie 5

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

Wskazówka

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

Rozwiązanie

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

$g^{p-1}{\equiv }_{p}1,$

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

• $g^{p-1}{\equiv }_{p^2}p+1$.

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

• $g^{p-1}{\equiv }_{p^2}1$.

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

$\begin{array}{rlr}(g(p+1){)}^{p-1}& {\equiv }_p& g^{p-1}(p+1{)}^{p-1}\\ & {\equiv }_p& 1\cdot ((\genfrac{}{}{0ex}{}{p-1}{0})+(\genfrac{}{}{0ex}{}{p-1}{1})p+(\genfrac{}{}{0ex}{}{p-1}{2})p^2+\dots )\\ & {\equiv }_p& 1\end{array}$

oraz

$\begin{array}{rlr}(g(p+1){)}^{p-1}& {\equiv }_{p^2}& g^{p-1}(p+1{)}^{p-1}\\ & {\equiv }_{p^2}& 1\cdot ((\genfrac{}{}{0ex}{}{p-1}{0})+(\genfrac{}{}{0ex}{}{p-1}{1})p+(\genfrac{}{}{0ex}{}{p-1}{2})p^2+\dots )\\ & {\equiv }_{p^2}& 1+(p-1)p\\ & {\equiv }_{p^2}& 1-p.\end{array}$

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