16. VIENETO ŠAKNYS IR PRIMITYVIEJI KŪNO ELEMENTAI

Šiame skyrelyje mus domins polinomo x^{n} − 1 faktorizacija virš baigtinio kūno GF (q). Taip pat pateiksime vieneto šaknu_{‘}, nagrinėtu_{‘} kompleksiniu_{‘} skaičiu_{‘} teorijoje, apibendrinima_{‘} baigtiniuose kūnuose.

12.1 apibrėžimas. Tegu polinomo x^{n} − 1 ∈ GF (q) [x] skaidinio kūnas yra GF (q^{s}). Šis kūnas vadinamas n-ciklotominiu kūnu virš kūno GF (q). Polinomo x^{n} − 1 šaknys šiame n-ciklotominiame kūne GF (q^{s}) yra vadinamos n-ojo laipsnio vieneto šaknimis virš kūno GF (q). Šiu_{‘} vieneto šaknu_{‘} aibe_{‘} žymėsime E_{n}.

Prisiminkime, kad panašiai buvo apibrėžtos ir kompleksinės n-ojo laipsnio vieneto šaknys. Nagrinėdami polinoma_{‘} x^{n} − 1 virš racionaliu_{‘}ju_{‘} skaičiu_{‘} kūno ℚ, vieneto šaknimis vadinome polinomo x^{n}−1 šaknis, esančias šio polinomo skaidinio kūne virš ℚ. Šis skaidinio kūnas yra tam tikras kompleksiniu_{‘} skaičiu_{‘} kūno ℂ pokūnis. Vaizdi yra šiu_{‘} vieneto šaknu_{‘} geometrinė interpretacija: tai taisyklingojo n-kampio, i_{‘}brėžto i_{‘} vienetini_{‘} apskritima_{‘}, kurio centras yra kompleksinės plokštumos koordinačiu_{‘} pradžioje, viršūnės.

Baigtinio kūno atveju vieneto šaknu_{‘} aibės E_{n} struktūra_{‘} nusako toks teiginys:

12.2 teiginys. Tegu n ∈ ℕ ir kūno GF (q) charakteristika yra lygi p. Tada:

1. Jeigu DBD (n, p) = 1, tai vieneto šaknu_{‘} aibė E_{n} yra n-osios eilės ciklinis multiplikacinės kūno GF (q^{s}) grupės GF (q^{s})^{∗} pogrupis.

2. Jeigu DBD (n, p) > 1 (t.y. DBD (n, p) = p) ir n = mp^{r} (čia m, r ∈ ℕ ir DBD (m, p) = 1), tai vieneto šaknu_{‘} aibė E_{n} = E_{m} . Kiekvienos iš šiu_{‘} šaknu_{‘} kartotinumas yra lygus p^{r}.

I_{‘} rodymas. 1. Jeigu DBD (n, p) = 1, tai polinomas x^{n} − 1 neturi kartotiniu_{‘} šaknu_{‘} jokiame kūno GF (q) plėtinyje, nes šis polinomas ir jo išvestinė (x^{n} − 1)′ = nx^{n−1} yra tarpusavyje pirminiai polinomai. Taigi aibėje E_{n} yra n polinomo x^{n} − 1 šaknu_{‘}: |E_{n}| = n. Jeigu α, β ∈ E_{n}, tai

(α β^{−1})^{n} = α^{n}(β^{−1})^{n} = α^{n}(β^{n})^{−1} = 1

ir α β^{−1} ∈ E_{n}.

Taigi E_{n} yra ciklinės grupės GF (q^{s})^{∗} pogrupis ir todėl E_{n} pati yra ciklinė grupė.

2. Jeigu n = mp^{r} (čia DBD (m, p) = 1), tai

x^{n} − 1 = x^{mpr} − 1 = (x^{m} − 1)^{pr}.

I_{‘}rodymui baigti belieka pasinaudoti 1.

△

Toliau baigtinio kūno GF (q) charakteristika char GF (q) bus pirminis skaičius p, tarpusavyje pirminis skaičiui n.

12.3 apibrėžimas. n-ojo laipsnio vieneto šaknis virš kūno GF (q), generuojanti cikline_{‘} grupe_{‘} E_{n}, vadinama primityvia_{‘}ja n-ojo laipsnio vieneto šaknimi virš kūno GF (q).

Vieneto šaknu_{‘} grupė E_{n} yra ciklinė, todėl, remiantis 5.43 teorema, egzistuoja φ (n) skirtingu_{‘} primityviu_{‘}ju_{‘} n-ojo laipsnio vieneto šaknu_{‘} virš kūno GF (q). Jeigu ω yra viena iš primityviu_{‘}ju_{‘} n-ojo laipsnio vieneto šaknu_{‘} virš GF (q), tai visos kitos primityviosios n-ojo laipsnio vieneto šaknys virš GF (q) yra ω^{s}; čia 1 ⩽ s ⩽ n, DBD (s, n) = 1. Pastebėsime, kad φ (n) > 0, ir todėl visiems teigiamiems sveikiems skaičiams n, tarpusavyje pirminiams skaičiui q, egzistuoja primityvioji n-ojo laipsnio vieneto šaknis virš kūno GF (q).

12.4 teiginys. Tegu GF (q^{s}) yra polinomo u_{n}(x) = x^{n} − 1 ∈ GF (q) skaidinio kūnas. Tada s yra toks mažiausias teigiamas sveikas skaičius, kad n yra q^{s} − 1 daliklis, t.y. q^{s} ≡ 1 (mod n). Šiuo atveju sakoma, kad skaičius s yra skaičiaus q eilė mod n ir rašoma s = ord_{n}(q).

I_{‘} rodymas. Tegu ω yra primityvioji n-ojo laipsnio vieneto šaknis virš GF (q). Tada

ω ∈ GF (q^{k}) ⟺ ω^{qk} = ω ⟺ ω^{qk−1} = 1 ⟺ q^{k} ≡ 1 (mod n),

o s yra toks mažiausias k, kuriam ω ∈ GF (q^{k}) ir todėl s – toks mažiausias teigiamas sveikas skaičius, kad q^{s} ≡ 1 (mod n).

△

Reikėtu_{‘} skirti primityviuosius polinomo u_{n}(x) = x^{n} − 1 skaidinio kūno GF (q^{s}) elementus, kaip cikline_{‘} grupe_{‘} GF (q^{s})^{∗} generuojančius, ir primityvia_{‘}sias n-ojo laipsnio vieneto šaknis virš kūno GF (q), kaip cikline_{‘} grupe_{‘} E_{n} generuojančius elementus.

12.5 teiginys. 1. Tegu a yra primityvusis polinomo u_{n}(x) = x^{n} − 1 skaidinio kūno GF (q^{s}) elementas. Tada primityviu_{‘}ju_{‘} kūno GF (q^{s}) elementu_{‘} aibė A yra

A = {a^{k} | DBD (k, q^{s} − 1) = 1}, |A| = φ (q^{s} − 1),

o n-ojo laipsnio primityviu_{‘}ju_{‘} vieneto šaknu_{‘} virš GF (q) aibė B yra

B = \{a^{k} | k = \frac{q^{s} − 1}{n} · m, m < n, DBD (m, n) = 1\}, |B| = φ (n).

2. Aibės A ir B sutampa tada ir tik tada, kai n = q^{s} − 1.

Visais kitais atvejais A ∩ B = O /.

I_{‘}rodysime teiginio 1 dali_{‘}, o 2 dali_{‘} paliksime i_{‘}rodyti skaitytojui.

I_{‘} rodymas. 1. Primityviojo kūno GF (q^{s}) elemento a eilė yra lygi q^{s}−1, todėl n yra q^{s} − 1 daliklis: q^{s} − 1 = nr. Tada

ord (a^{k}) = \frac{q^{s} − 1}{DBD (k, q^{s} − 1)} = \frac{nr}{DBD (k, nr)}.

Elementas a^{k} yra primityvioji n-ojo laipsnio vieneto šaknis tada ir tik tada, kai

\frac{nr}{DBD (k, nr)} = n ⟺ DBD (k, nr) = r ⟺ k = rm, DBD (m, n) = 1.

Tai i_{‘}rodo pirma_{‘}ja_{‘} teiginio dali_{‘}.

△

Žinodami primityvu_{‘}ji_{‘} kūno GF (q^{s}) elementa_{‘}, remdamiesi ka_{‘} tik i_{‘}rodytu teiginiu galime faktorizuoti polinoma_{‘} u_{n}(x) = x^{n}−1 virš kūno GF (q).

Tegu a yra primityvusis kūno GF (q^{s}) elementas ir s = ord_{n}(q). Iš 12.5 teiginio žinome, kad

ω = a^{\frac{q^{s}−1}{n}}

yra primityvioji n-ojo laipsnio vieneto šaknis ir todėl visos polinomo u_{n}(x) šaknys yra ω laipsniai

1, ω, ω^{2}, …, ω^{n−1}.

Surade_{‘} šiu_{‘} elementu_{‘} minimaliuosius polinomus ir sudaugine_{‘} skirtingus neredukuojamus virš GF (q) polinomus, gausime polinomo u_{n}(x) = x^{n} − 1 kanonini_{‘} skaidini_{‘} virš GF (q).

Visiems i, 0 ⩽ i ⩽ n − 1, elemento ω^{i} jungtiniai elementai yra

ω^{i}, ω^{iq}, ω^{iq^{2}}, …, ω^{iqm−1};

čia m yra toks mažiausias sveikas teigiamas skaičius, kad ω^{iqm} = ω^{i}, t.y. iq^{m} ≡ i (mod n). Paskutinė sa_{‘}lyga apibrėžia elemento ω^{i} jungtiniu_{‘} elementu_{‘} skaičiu_{‘} m.

Šiu_{‘} elemento ω^{i} jungtiniu_{‘} elementu_{‘} minimalus polinomas yra

m_{i}(x) = (x − ω^{i})(x − ω^{iq})(x − ω^{iq^{2}}) … (x − ω^{iqm−1});

čia m yra mažiausias sveikas teigiamas skaičius, kuriam iq^{m} ≡ i (mod n).

12.6 apibrėžimas. Elemento ω^{i} jungtiniu_{‘} elementu_{‘} skirtingu_{‘} laipsnio rodikliu_{‘} aibė

C_{i} = {i, iq, iq^{2}, …, iq^{m−1}};

čia m yra mažiausias sveikas teigiamas skaičius, kuriam iq^{m} ≡ i (mod n), vadinama i-a_{‘}ja skaičiaus q ciklotomine aibe moduliu n.

Skaičiaus q ciklotominės aibės mod n nepriklauso nuo konkretaus primityvaus kūno GF (q^{s}) elemento parinkimo. Be to, žinodami šios aibės elementus, galime iš anksto pasakyti, kiek neredukuojamu_{‘} polinomu_{‘} bus polinomo u_{n}(x) kanoniniame skaidinyje ir kokie šiu_{‘} polinomu_{‘} laipsniai.

12.7 pavyzdys. Faktorizuosime polinoma_{‘} u_{15}(x) = x^{15} −1 virš kūno GF (2).

Žinome, kad n = 15, q = 2. Todėl s = ord_{15}(2) = 4 ir kūnas GF (2^{4}) = GF (16) yra polinomo u_{15}(x) skaidinio kūnas. Iš 11.14 pavyzdžio matėme, kad polinomas x^{4} + x^{3} + 1 yra primityvusis polinomas, todėl jo šaknis a yra primityvusis kūno GF (16) elementas. Bet

ω = a^{\frac{(q^{s}−1)}{n}} = a^{\frac{16−1}{15}} = a

taip pat yra ir primityvioji n-ojo laipsnio vieneto šaknis. Rasime skirtingas skaičiaus 2 ciklotomines aibes moduliu 15 (žr. 11.14 pavyzdi_{‘}):

C_{0} = {0},
C_{1} = {1, 2, 4, 8},
C_{3} = {3, 6, 9, 12}, 3 · 2^{3} = 24 ≡ 9 (mod 15),
C_{5} = {5, 10},
C_{7} = {7, 11, 13, 14}, 7 · 2^{2} = 28 ≡ 13 (mod 15),
7 · 2^{3} = 56 ≡ 11 (mod 15).

Taigi polinomo u_{15}(x) kanoniniame skaidinyje yra vienas pirmojo laipsnio polinomas, vienas antrojo laipsnio polinomas ir trys ketvirtojo laipsnio polinomai:

m_{0}(x) = x + 1,
m_{1}(x) = x^{4} + x^{3} + 1,
m_{3}(x) = x^{4} + x^{3} + x^{2} + x + 1,
m_{5}(x) = x^{2} + x + 1,
m_{7}(x) = x^{4} + x + 1.

Polinomo u_{15}(x) kanoninis skaidinys yra

x^{15} −1 = (x+1) (x^{4} +x^{3} +1) (x^{4} +x^{3} +x^{2} +x+1) (x^{2} +x+1) (x^{4} +x+1).

Ieškodami polinomo u_{n}(x) = x^{n} − 1 ∈ GF (q)[x] kanoninio skaidinio, naudojomės šio polinomo skaidinio kūnu GF (q^{s}).