Nierozkładalność wielomianu

[Arczi1984]

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?

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

[Arczi1984]

Dzięki. Zaraz to przeanalizuję.

[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]}\))