Mam drobny problem z udowodnieniem następującego faktu:
Udowodnij, że trójmian \(\displaystyle{ x^{2n} + x^{n} + 1}\) jest nierozkładalny nad ciałem \(\displaystyle{ GF(2)}\) wtw, gdy \(\displaystyle{ n = 3^{k}}\) (dla pewnej nieujemnej liczby całkowitej k).
Może ktoś pomóc w rozwikłaniu tego stwierdzenia?
Nierozkładalność wielomianu
: 14 lut 2009, o 17:07
autor: max
Na razie umiem \(\displaystyle{ (\Leftarrow)}\)
Najpierw uświadomimy sobie kilka prawd z których będziemy chcieli wywnioskować nierozkładalność wielomianu \(\displaystyle{ x^{2\cdot 3^{k}} + x^{3^{k}} + 1\in \mathbb{F}_{2}[x].}\)
Lemat 1.
Niech \(\displaystyle{ n}\) będzie dowolną liczbą całkowitą dodatnią, \(\displaystyle{ \Phi_{n}(x)}\) n-tym wielomianem cyklotomicznym, \(\displaystyle{ p}\) dowolną liczbą pierwszą. Wtedy:
(i) \(\displaystyle{ \Phi_{p^{k}}(x) = \Phi_{p}(x^{p^{k-1}})}\)
(ii) Jeśli \(\displaystyle{ p \nmid n,}\) to każdy czynnik nierozkładalny \(\displaystyle{ \Phi_{n}(x)}\) w \(\displaystyle{ \mathbb{F}_{p}[x]}\) ma stopień równy rzędowi \(\displaystyle{ p}\) modulo \(\displaystyle{ n.}\)
dowód:
(i) Ponieważ \(\displaystyle{ x^{p^{k}} - 1 = \prod_{i = 0}^{k}\Phi_{p^{i}}(x)}\) to możemy zweryfikować tę równość indukcyjnie korzystając ze wzoru: \(\displaystyle{ x^{p^{k+1}} - 1 = (x^{p^{k}})^{p} - 1^{p} = (x^{p^{k}} - 1)\sum_{i = 1}^{p}x^{(p-i)p^{k}}.}\)
(ii) Mamy \(\displaystyle{ x^{n} - 1 = \Phi_{n}(x)\prod_{\substack{d|n \\ 0 < d < n}} \Phi_{d}(x)}\)
więc na podstawie \(\displaystyle{ \Phi_{d}(x) | x^{d} - 1}\) i \(\displaystyle{ (x^{n} - 1)' = nx^{n-1}\neq 0}\) (bo \(\displaystyle{ p\nmid n}\)) wnosimy, że pierwiastki \(\displaystyle{ \Phi_{n}(x)}\) to elementy rzędu \(\displaystyle{ n}\) w grupie multiplikatywnej \(\displaystyle{ \mathbb{F}_{p^{l}}^{*},}\) gdzie \(\displaystyle{ l}\) jest rzędem \(\displaystyle{ p}\) modulo \(\displaystyle{ n.}\)
Ustalmy dowolny taki pierwiastek \(\displaystyle{ \alpha.}\)
Weźmy grupę \(\displaystyle{ G:=\mbox{Aut} \, (\mathbb{F}_{p^{l}}) = \mbox{Gal} \, (\mathbb{F}_{p^{l}}/\mathbb{F}_{p}).}\)
Jest to grupa cykliczna rzędu \(\displaystyle{ l}\) generowana przez automorfizm Frobeniusa: \(\displaystyle{ \mathbb{F}_{p^{l}}\ni a \mapsto a^{p}\in \mathbb{F}_{p^{l}}}\)
Rozszerzenie \(\displaystyle{ \mathbb{F}_{p^{l}}/\mathbb{F}_{p}}\) jest Galois, więc \(\displaystyle{ \mathbb{F}_{p^{l}}^{G} = \mathbb{F}_{p}.}\)
Orbita \(\displaystyle{ \alpha}\) przy działaniu \(\displaystyle{ G}\) na \(\displaystyle{ \mathbb{F}_{p^{l}}}\) to \(\displaystyle{ \{\alpha, \alpha^{p},\ldots, \alpha^{p^{l - 1}}\}.}\)
Stąd wielomian minimalny \(\displaystyle{ \alpha}\) nad \(\displaystyle{ \mathbb{F}_{p}}\) to: \(\displaystyle{ \prod_{i = 0}^{l-1}(x - \alpha^{p^{i}}),}\)
musi on dzielić \(\displaystyle{ \Phi_{n}(x)}\) a jego stopień jest równy rzędowi \(\displaystyle{ p}\) modulo \(\displaystyle{ n,}\) co kończy dowód.
Lemat 2.
Niech \(\displaystyle{ k}\) będzie dowolną liczbą całkowitą dodatnią. Wtedy rząd \(\displaystyle{ 2}\) modulo \(\displaystyle{ 3^{k}}\) wynosi \(\displaystyle{ 2\cdot 3^{k-1}}\)
dowód:
Indukcyjnie pokazujemy, że \(\displaystyle{ l_{k}:= 2\cdot 3^{k-1}}\) spełnia \(\displaystyle{ 3^{k}|2^{l_{k}} - 1, \ 3^{k+1}\nmid 2^{l_{k}} - 1}\) i że \(\displaystyle{ l_{k}}\) jest rzędem \(\displaystyle{ 2}\) modulo \(\displaystyle{ 3^{k}.}\)
Przypadek \(\displaystyle{ k = 1}\) liczymy w pamięci.
Jeśli mamy tezę dla \(\displaystyle{ k,}\) to korzystamy z równości: \(\displaystyle{ 2^{l_{k+1}} - 1 = (2^{l_{k}} - 1)(2^{2l_{k}} + 2^{l_{k}} + 1)}\)
Z założenia indukcyjnego \(\displaystyle{ 3^{k}}\) dzieli pierwszy nawias, \(\displaystyle{ 3^{k+1}}\) nie dzieli pierwszego nawiasu, \(\displaystyle{ 3}\) dzieli drugi nawias ale \(\displaystyle{ 3^{2}}\) nie dzieli drugiego nawiasu, więc \(\displaystyle{ 3^{k+1}| 2^{l_{k+1}} - 1,\ 3^{k+2}\nmid 2^{l_{k+1}} - 1.}\)
Stąd wiemy, że jeśli \(\displaystyle{ l,}\) jest rzędem \(\displaystyle{ 2}\) modulo \(\displaystyle{ 3^{k+1}}\) to \(\displaystyle{ l | l_{k+1},}\) a z założenia indukcyjnego \(\displaystyle{ l_{k}|l}\) oraz \(\displaystyle{ l_{k}\neq l,}\) stąd \(\displaystyle{ l = l_{k + 1}.}\)
Wracając do zadania, z pierwszej części pierwszego lematu: \(\displaystyle{ x^{2\cdot 3^{k}} + x^{3^{k}} + 1 = \Phi_{3}(x^{3^{k}}) = \Phi_{3^{k+1}}(x)}\)
z drugiej części pierwszego lematu i z drugiego lematu otrzymujemy, że każdy czynnik nierozkładalny \(\displaystyle{ \Phi_{3^{k+1}}(x)}\) jest stopnia \(\displaystyle{ 2\cdot 3^{k}=\varphi(3^{k+1}) = \deg \Phi_{3^{k+1}}(x)}\) czyli jest równy \(\displaystyle{ \Phi_{3^{k+1}}(x)}\) co dowodzi nierozkładalności tego wielomianu.
Nierozkładalność wielomianu
: 14 lut 2009, o 17:28
autor: Arczi1984
Dzięki. Zaraz to przeanalizuję.
Nierozkładalność wielomianu
: 15 lut 2009, o 01:12
autor: max
A w drugą stronę jest dużo łatwiej, bo mamy takie coś:
Lemat
Niech \(\displaystyle{ n}\) będzie dowolną liczbą całkowitą dodatnią, \(\displaystyle{ p}\) dowolną liczbą pierwszą, \(\displaystyle{ \Phi_{n}(x)}\) n-tym wielomianem cyklotomicznym. Wtedy jeśli \(\displaystyle{ p\nmid n}\) to \(\displaystyle{ \Phi_{n}(x^{p}) = \Phi_{np}(x)\Phi_{n}(x)}\)
dowód:
Znów indukcja, dla \(\displaystyle{ n=1}\) jest to prawdziwa równość: \(\displaystyle{ x^{p} - 1 = \Phi_{p}(x)\Phi_{1}(x)}\)
A jeśli teza zachodzi dla wszystkich \(\displaystyle{ k < n,}\) to rozpisujemy z założenia indukcyjnego: \(\displaystyle{ x^{np} - 1 = (x^{p})^{n} - 1 = \Phi_{n}(x^{p})\prod_{\substack{d|n \\ 0<d <n}}\Phi_{d}(x^{p}) =\\
= \Phi_{n}(x^{p})\prod_{\substack{d|n \\ 0<d <n}}\Phi_{dp}(x)\Phi_{d}(x) = \Phi_{n}(x^{p})\prod_{\substack{d|np \\ 0<d\\ n\neq d\neq np}}\Phi_{d}(x)}\)
a z drugiej strony: \(\displaystyle{ x^{np} - 1 = \prod_{\substack{d|np \\ 0<d \le n}}\Phi_{d}(x)}\)
i przyrównując stronami te dwie równości dostajemy tezę dla \(\displaystyle{ n.}\)
Zatem jeśli mamy \(\displaystyle{ n= pm, \ p\neq 3,}\) to dostajemy rozkład: \(\displaystyle{ x^{2n} + x^{n} + 1 = \Phi_{3}(x^{n}) =\Phi_{3}((x^{m})^{p}) = \Phi_{3p}(x^{m})\cdot \Phi_{3}(x^{m})}\) (i to nawet w \(\displaystyle{ \mathbb{Z}[x]}\))