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}+\ldots +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}+\ldots +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}+\ldots +f_{n}x^{n}$ to wielomian $f'(x)=f_{1}+2f_{2}x+\ldots +nf_{n}x^{n-1}$.

Pokaż, że:

${\begin{aligned}(f+g)'(x)&=f'(x)+g'(x),\\(fg)'(x)&=f'(x)g(x)+f(x)g'(x)\end{aligned}}$

Wskazówka

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

Rozwiązanie

Niech

${\begin{aligned}f(x)&=f_{0}+f_{1}x+f_{2}x^{2}+\ldots +f_{n}x^{n},\\g(x)&=g_{0}+g_{1}x+g_{2}x^{2}+\ldots +g_{n}x^{n}\end{aligned}}$

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)'_{k}=(k+1)(f_{k+1}+g_{k+1})$,
• $f'_{k}=(k+1)f_{k+1}$,
• $g'_{k}=(k+1)g_{k+1}$,
• $f'_{k}+g'_{k}=(k+1)(f_{k+1}+g_{k+1})$

oraz dla iloczynu:

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

${\begin{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}if_{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{aligned}}$

Ćwiczenie 3

Pokaż, że rozkład wielomianu $x^{p^{n}}-x$ nad ciałem ${\bf {\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\geq 2$ jest stopniem nierozkładalnego i unormowanego wielomianu $f(x)\in \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 ${\bf {\mathbb {Z} }}_{p}[x]$,
• stopień nierozkładalnego wielomianu dzielącego wielomian $x^{p^{n}}-x$ w pierścieniu ${\bf {\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 ${\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 $d\geq 2$ jest stopniem nierozkładalnego wielomianu $f(x)\in \mathbb {Z} _{p}[x]$, to $f(x)$ dzieli $x^{p^{d}}-1$:

Niech $f(x)$ będzie nierozkładalnym wielomianem stopnia $d\geqslant 2$. Na podstawie twierdzenia opisującego konstrukcję ciał o $p^{k}$ elementach wiemy, że pierścień ilorazowy $\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 {Z} _{p}[x]/f(x)$ z dzielenia przez $f(x)$:

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

Ponieważ $\mathbb {Z} _{p}[x]/f(x)$ jest ciałem, to klasy $[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

$[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

$[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 $[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 ${\bf {\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\neq 0$. Z Małego Twierdzenia Fermata mamy $c^{p-1}=1$ dla ${\bf {\mathbb {Z} }}_{p}-\left\lbrace 0\right\rbrace$, 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 {Z} _{p}$.

Niech teraz $f(x)$ będzie nierozkładalnym wielomianem stopnia $d\geqslant 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 {Z} _{p}[x]$, sam jest dzielnikiem $n$:

Rozważmy dowolny unormowany, nierozkładalny dzielnik $f(x)$ wielomianu $x^{p^{n}}-x$ o stopniu $d\geqslant 2$. Niech $n=qd+r$, gdzie $0\leqslant r<d$. Udowodnimy, że $r=0$. Na podstawie punktu pierwszego wiemy, że $f(x)|x^{p^{d}}-x$ w pierścieniu $\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 {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)}\ldots \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 {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 {Z} _{p}$, to $h(x^{p^{r}})=h(x)^{p^{r}}$ w ${\bf {\mathbb {Z} _{p}}}[x]$. A zatem dla dowolnego $h(x)\in \mathbb {Z} _{p}[x]$

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle [h(x)]_{f(x)}=[h(x)]^{p^r}_{f(x)} }

co oznacza, że każdy spośród $p^{d}$ elementów ciała $\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 ${\bf {\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'(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 $p^{n}=0$ w ciele $\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 {Z} _{p}[x]$ istnieje unormowany, nierozkładalny (nad $\mathbb {Z} _{p}$) wielomian stopnia $n$.

Wskazówka

Niech $N_{n}(p)$ będzie liczba nieredukowalnych, unormowanych wielomianów stopnia $n$ w $\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 {Z} _{p}[x]$. Rozważmy rozkład wielomianu $x^{p^{n}}-x$ w pierścieniu $\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}dN_{d}(p)$

Wzór inwersyjny Mobiusa daje wtedy:

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

czyli

${\begin{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.\end{aligned}}$

Ponieważ $N_{n}(p)$ przyjmuje wartości całkowite

$N_{n}(p)\geqslant 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 {Z} _{n}^{*}=\left\lbrace m:1\leqslant m\leqslant n,\ m\perp n\right\rbrace$. Pokaż, że gdy $p$ jest liczbą pierwszą, to grupa $\mathbb {Z} _{p^{2}}^{*}$ jest cykliczna.

Wskazówka

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

Rozwiązanie

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

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

czyli $\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 {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 {Z} _{p^{2}}^{*}$ tzn. liczbę $\varphi (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}\not \equiv _{p^{2}}1$, to $g$ ma rząd $p(p-1)$ w $\mathbb {Z} _{p^{2}}^{*}$, czyli $\mathbb {Z} _{p^{2}}^{*}$ jest cykliczna.

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

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

${\begin{aligned}(g(p+1))^{p-1}&\equiv _{p}&g^{p-1}(p+1)^{p-1}\\&\equiv _{p}&1\cdot \left({p-1 \choose 0}+{p-1 \choose 1}p+{p-1 \choose 2}p^{2}+\ldots \right)\\&\equiv _{p}&1\end{aligned}}$

oraz

${\begin{aligned}(g(p+1))^{p-1}&\equiv _{p^{2}}&g^{p-1}(p+1)^{p-1}\\&\equiv _{p^{2}}&1\cdot \left({p-1 \choose 0}+{p-1 \choose 1}p+{p-1 \choose 2}p^{2}+\ldots \right)\\&\equiv _{p^{2}}&1+(p-1)p\\&\equiv _{p^{2}}&1-p.\end{aligned}}$

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 {Z} _{p^{2}}^{*}$. A zatem i w tym przypadku $\mathbb {Z} _{p^{2}}^{*}$ jest cykliczna.