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 = q d$ .

Rozwiązanie

Łatwo pokazać, że jeśli $d | n$ , czyli np. $n = q d$ , 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^{'} (x) = f_{1} + 2 f_{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)^{'} (x)$ z $f^{'} (x) + g^{'} (x)$ oraz $(f g)^{'} (x)$ z $f^{'} (x) g (x) + f (x) g^{'} (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)'_{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:

$(f g)_{k} = \sum_{i = 0}^{k} f_{i} g_{k - i}$ ,
$(f g)'_{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}$ ,
$(f g^{'})_{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 $ℤ_{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 ℤ_{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 $ℤ_{p} [x]$ ,
stopień nierozkładalnego wielomianu dzielącego wielomian $x^{p^{n}} - x$ w pierścieniu $ℤ_{p} [x]$ , sam jest dzielnikiem $n$ ,
w rozkładzie wielomianu $x^{p^{n}} - x$ na iloczyn wielomianów nierozkładalnych z pierścienia $ℤ_{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 ℤ_{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 $ℤ_{p} [x] / f (x)$ jest $p^{d}$ -elementowym ciałem. Jego elementy to klasy równoważności reszt wielomianów w $ℤ_{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ż $ℤ_{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 $ℤ_{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 $ℤ_{p} - {0}$ , tzn. $c$ jest pierwiastkiem $x^{p - 1} - 1$ . Twierdzenie Bezout daje więc $x - c | x^{p - 1} - 1$ . Z Zadania Uzupelnic ex ciala prosty fakt| wiemy, że $x^{p - 1} - 1 | x^{p^{n}} - 1$ więc $x - c | x^{p^{n}} - 1$ , dla dowolnego $c \in ℤ_{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 Zadaniu Uzupelnic ex ciala prosty fakt|, dostajemy $f (x) | x^{p^{n}} - 1$ .

stopień nierozkładalnego wielomianu dzielącego wielomian $x^{p^{n}} - x$ w pierścieniu $ℤ_{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 = q d + r$ , gdzie $0 ⩽ r < d$ . Udowodnimy, że $r = 0$ . Na podstawie punktu pierwszego wiemy, że $f (x) | x^{p^{d}} - x$ w pierścieniu $ℤ_{p} [x]$ , czyli wielomiany $x^{p^{d}}$ i $x$ dają te same reszty modulo $\sim_{f (x)}$ , czyli są równe w ciele $ℤ_{p} [x] / f (x)$ . Mamy więc

x^{p^{q d}} = {(x^{p^{d}})}^{p^{(q - 1) d}} \sim_{f (x)} x^{p^{(q - 1) d}} = {(x^{p^{d}})}^{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^{q d + r}} = {(x^{p^{q d}})}^{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 ℤ_{p} [x]$ mamy $[h (x)]_{f (x)} = [h (x^{p^{r}})]_{f (x)}$ . Z drugiej strony, ponieważ $h (x)$ ma współczynniki w ciele $ℤ_{p}$ , to $h (x^{p^{r}}) = h (x)^{p^{r}}$ w $ℤ_{𝐩} [x]$ . A zatem dla dowolnego $h (x) \in ℤ_{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 $ℤ_{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 $ℤ_{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 = 2 f (x) f^{'} (x) q (x) + f^{2} (x) q^{'} (x) = f (x) \cdot (2 f^{'} (x) q (x) + f (x) q^{'} (x)) .

Pamiętając, że $p^{n} = 0$ w ciele $ℤ_{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 $ℤ_{p} [x]$ istnieje unormowany, nierozkładalny (nad $ℤ_{p}$ ) wielomian stopnia $n$ .

Wskazówka

Niech $N_{n} (p)$ będzie liczba nieredukowalnych, unormowanych wielomianów stopnia $n$ w $ℤ_{p} [x]$ . Wykorzystując Zadanie Uzupelnic ex ciala rozklad xpn-x| 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 $ℤ_{p} [x]$ . Rozważmy rozkład wielomianu $x^{p^{n}} - x$ w pierścieniu $ℤ_{p} [x]$ na wielomiany nierozkładalne. Z Zadania Uzupelnic ex ciala rozklad xpn-x| 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} μ (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 $ℤ_{n}^{*} = {m : 1 ⩽ m ⩽ n, m ⊥ n}$ . Pokaż, że gdy $p$ jest liczbą pierwszą, to grupa $ℤ_{p^{2}}^{*}$ jest cykliczna.

Wskazówka

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

Rozwiązanie

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

g^{p - 1} \equiv_{p} 1,

czyli $ℤ_{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 $ℤ_{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 $ℤ_{p^{2}}^{*}$ tzn. liczbę $φ (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 $ℤ_{p^{2}}^{*}$ , czyli $ℤ_{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 $ℤ_{p^{2}}^{*}$ . A zatem i w tym przypadku $ℤ_{p^{2}}^{*}$ jest cykliczna.

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

Ciała skończone

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia