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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $(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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $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}$,

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ż $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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $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.