7. ŽIEDO ℤ_{n} VIENETU_{‘} GRUPĖ

6.7 pastabos. Žinome (žr. 6.5 pavyzdi_{‘}, 1), kad U(ℤ) = ({−1, 1}, ·) yra 2-osios eilės ciklinė grupė.

Jeigu K – kūnas, tai grupė U(K) = K − {0} = K^{∗} yra vadinama multiplikacine kūno K grupe.

Atskirai panagrinėkime likiniu_{‘} klasiu_{‘} žieda_{‘} ℤ_{n} ir šio žiedo elementu_{‘}, turinčiu_{‘} atvirkštinius elementus, grupe_{‘} U(ℤ_{n}) = U_{n}.

Iš 6.3 pavyzdžiu_{‘} žinome, kad ne visiems n nenuliniai žiedo ℤ_{n} elementai turi atvirkštinius. Pavyzdžiui, žiede ℤ_{8} elementai \overline{2}, \overline{4}, \overline{6} neturi atvirkštiniu_{‘}, o elementai \overline{1}, \overline{3}, \overline{5}, \overline{7} turi atvirkštinius. Priežastis ta, kad skaičiai 1, 3, 5, 7 yra tarpusavyje pirminiai skaičiui 8, o skaičiai 2, 4, 6 – ne.

6.8 teiginys. 1. U_{n} = \{\overline{a} | DBD (a, n) = 1\}.
2. |U_{n}| = φ(n), kai φ – Oilerio funkcija.

I_{‘} rodymas. 1. Jeigu \overline{a} ∈ U_{n}, tai egzistuoja toks \overline{b} ∈ U_{n}, kad \overline{a}\overline{b} = \overline{1}, t.y. a · b ≡ 1 (mod n) ⟺ a · b = 1 + n · k, k ∈ ℤ, a · b + n(−k) = 1.

Jeigu būtu_{‘} DBD(a, n) = d > 1, tai egzistuotu_{‘} tokie c ir m, kad a = dc, n = dm ir d(cb + m(−k)) = 1, t.y. 1 turėtu_{‘} dalytis iš d > 1. Ši prieštara ir rodo, kad DBD (a, n) = 1.

Priešingai, jeigu DBD (a, n) = 1, tai atvirkštiniu Euklido^{1} algoritmu galima rasti tokius skaičius b ir k, kad

a · b + n · k = 1,
a · b = 1 − n · k,
a · b ≡ 1 (mod n),
\overline{a} · \overline{b} = \overline{1} ir \overline{a} ∈ U_{n}.

2. I_{‘}rodymas išplaukia iš Oilerio funkcijos apibrėžimo (žr. 2.17 pavyzdi_{‘}).

1 Eυκλειδης, III a. pr. Kr., – senovės graiku_{‘} matematikas.

△

Remiantis paskutiniu teiginiu i_{‘}rodomi žymiu_{‘}ju_{‘} teoremu_{‘} analogai grupei U_{n}.

6.9 Oilerio–Ferma teorema. Jeigu \overline{a} ∈ U_{n}, tai \overline{a}^{φ(n)} = \overline{1}.

Išvada. Jeigu \overline{a} ∈ U_{n}, tai \overline{a}^{−1} = (\overline{a})^{φ(n)−1}.

6.10 Mažoji Ferma teorema. Jeigu p yra pirminis skaičius, tai visiems \overline{a} ∈ U_{p}, \overline{a}^{p−1} = \overline{1}.

Išvada. Jeigu p yra pirminis skaičius, tai visiems \overline{a} ∈ ℤ_{p}, a ≠ 0, \overline{a}^{−1} = \overline{a}^{p−2}.

6.11 išvada. Tegu n = p_{1}p_{2} … p_{r} yra natūralusis skaičius, čia p_{1}, p_{2}, …, p_{r} – skirtingi pirminiai skaičiai. Tada visiems \overline{a} ∈ ℤ_{n} teisinga lygybė \overline{a}^{φ(n)+1} = \overline{a}, φ – Oilerio funkcija.

I_{‘} rodymas. Mūsu_{‘} nagrinėjamu atveju φ(n) = (p_{1}−1)(p_{2}−1) … (p_{r}−1). Tegu \overline{a} ∈ ℤ_{n}. Pirminiam skaičiui p_{i}, 1 ⩽ i ⩽ r, galimi du variantai:

a) DBD (a, p_{i}) = 1, tai a^{p_{i}−1} ≡ 1 (mod p_{i}),

\begin{matrix}a^{φ(n)} = (a^{p_{i}−1})^{\frac{φ(n)}{p_{i}−1}} ≡ 1 (mod p_{i}), \\ a^{φ(n)+1} ≡ a (mod p_{i}). \end{matrix}

b) DBD (a, p_{i}) > 1, t.y. a dalijasi iš p_{i} ir todėl a ≡ 0 (mod p_{i}),
a^{φ(n)+1} ≡ 0 ≡ a (mod p_{i}).

Taigi visiems p_{i}, 1 ⩽ i ⩽ r, a^{φ(n)+1} ≡ a (mod p_{i}), t.y. a^{φ(n)+1} − a dalijasi iš visu_{‘} pirminiu_{‘} p_{i}, 1 ⩽ i ⩽ r, kartu iš šiu_{‘} pirminiu_{‘} skaičiu_{‘} sandaugos p_{1}p_{2} … p_{r} = n:

\begin{matrix}a^{φ(n)+1} ≡ a (mod n), \\ \overline{a}^{φ(n)+1} = \overline{a}. \end{matrix}

△

Remdamiesi bendrais teiginiais apie komutatyvia_{‘}sias grupes, ištirsime, kokios gali būti grupės U_{n} elementu_{‘} eiliu_{‘} reikšmės.

6.12 teiginys. Tegu (A, ·) yra komutatyvioji grupė, kurios eilė |A| = n, o laisvai pasirinktu_{‘} grupės A elementu_{‘} a ir b eilės yra ord_{A}(a) = l ir ord_{A}(b) = m. Tada:

1) a^{k} = e_{A} tada ir tik tada, kai k dalijasi iš l;

2) jeigu DBD (l, m) = 1, tai ord_{A}(a · b) = l · m;

3) grupėje A visada galima rasti toki_{‘} elementa_{‘} c, kurio eilė yra lygi bendrajam mažiausiam skaičiu_{‘} l ir m kartotiniui: ord_{A}(c) = BMK (l, m).

I_{‘} rodymas. 1) Padalije_{‘} skaičiu_{‘} k iš l su liekana, gausime k = l · q + r, 0 ⩽ r < l. Tada

\begin{matrix}e_{A} = a^{k} ⟺ e_{A} = (a^{l})^{q} · a^{r} ⟺ e_{A} = (e_{A})^{q}a^{r} ⟺ e_{A} = a^{r}, \\ 0 ⩽ r < l ⟺ r = 0. \end{matrix}

2) Kai DBD (l, m) = 1, tai (a · b)^{l·m} = (a^{l})^{m} · (b^{m})^{l} = e_{A}^{m} · e_{A}^{l} = e_{A}, ir todėl remiantis 1) sandauga l · m dalijasi iš ord_{A}(a · b) = s.

Priešingai,

\begin{matrix}e_{A} = (a · b)^{s} = a^{s} · b^{s}, \\ a^{s} = (b^{s})^{−1} = (b^{−1})^{s}, \end{matrix}

e_{A} = (a^{l})^{s} = a^{l·s} = (b^{−1})^{l·s} = (b^{l·s})^{−1} ⟺ e_{A} = b^{l·s}

ir pagal 1) l · s dalijasi iš m. Bet DBD (l, m) = 1 ir todėl s turi dalytis iš m.

Panašiai galime i_{‘}sitikinti ir tuo, kad skaičius s dalijasi iš l. Taigi s = ord_{A}(a · b) dalijasi iš m · l (nes DBD (l, m) = 1). Apibendrine_{‘} gausime, kad ord_{A}(a · b) = m · l.

3) Užrašykime skaičius l ir m skirtingu_{‘} pirminiu_{‘} skaičiu_{‘} sandauga:

\begin{matrix}l = p_{1}^{α_{1}} … p_{t}^{α_{t}}, \\ m = p_{1}^{β_{1}} … p_{t}^{β_{t}}. \end{matrix}

Taip skaidant, gali atsitikti, kad kai kuriems i, 1 ⩽ i ⩽ t, α_{i} = 0, o kai kuriems j, 1 ⩽ j ⩽ t, β_{j} = 0.

Gerai žinome, kad:

a) BMK (l, m) = p_{1}^{max (α_{1},β_{1})} … p_{t}^{max (α_{t},β_{t})},

b) DBD (l, m) = p_{1}^{min (α_{1},β_{1})} … p_{t}^{min (α_{t},β_{t})},

c) BMK (l, m) · DBD (l, m) = l · m.

Nagrinėjamus skaičiu_{‘} l ir m skaidinius sutvarkykime taip:

\begin{matrix}l = p_{1}^{α_{1}} … p_{r}^{α_{r}}p_{r+1}^{α_{r+1}} … p_{t}^{α_{t}}, \\ m = p_{1}^{β_{1}} … p_{r}^{β_{r}}p_{r+1}^{β_{r+1}} … p_{t}^{β_{t}}; \end{matrix}

čia

\begin{matrix}α_{i} ⩽ β_{i}, kai 1 ⩽ i ⩽ r, \\ α_{i} > β_{i}, kai r + 1 ⩽ i ⩽ t. \end{matrix}

Pažymėje_{‘} k_{1} = p_{1}^{α_{1}} … p_{r}^{α_{r}}, k_{2} = p_{r+1}^{β_{r+1}} … p_{t}^{β_{t}}, gausime k_{1} · k_{2} = p_{1}^{α_{1}} … p_{r}^{α_{r}}p_{r+1}^{β_{r+1}} … p_{t}^{β_{t}} = p_{1}^{min (α_{1}β_{1})} … p_{t}^{min (α_{t}β_{t})} = DBD (l, m),

ord(a^{k_{1}}) = \frac{l}{DBD (l, k_{1})} = \frac{l}{k_{1}} ,

ord(a^{k_{2}}) = \frac{m}{DBD (m, k_{2})} = \frac{m}{k_{2}} ,

ord(a^{k_{1}} · a^{k_{2}}) = \frac{l}{k_{1}} · \frac{m}{k_{2}} = \frac{l · m}{DBD (l, m)} = BMK (l, m), nes

DBD (\frac{l}{k_{1}} , \frac{m}{k_{2}} ) = DBD(p_{r+1}^{α_{r+1}} … p_{t}^{α_{t}}, p_{1}^{β_{1}} … p_{r}^{β_{r}}) = 1.

△

6.13 pastaba. I_{‘}rodyto teiginio 3) dali_{‘} indukcija pagal n galima apibendrinti:

3′) jeigu a_{1}, a_{2}, …, a_{r} ∈ A, tai grupėje A visada galima rasti toki_{‘} elementa_{‘} c, kurio eilė

ord_{A}(c) = BMK (ord_{A}(a_{1}), ord_{A}(a_{2}), …, ord_{A}(a_{r})). Pirmiesiems natūraliesiems n grupės U_{n} yra ciklinės:

n = 1, φ(1) = 1, U_{1} = {1} = ⟨1⟩,

n = 2, φ(2) = 1, U_{2} = {1} = ⟨1⟩,
n = 3, φ(3) = 2, U_{3} = {1, 2} = ⟨2⟩.

Generuojančio grupe_{‘} U_{3} elemento laipsniai mod 3:

\begin{aligned}n & = & 1 & 2 \\ 2^{n} & = & 2 & 1 \end{aligned}

n = 4, φ(4) = 2, U_{4} = {1, 3} = ⟨3⟩.

Generuojančio grupe_{‘} U_{4} elemento laipsniai mod 4:

\begin{aligned}n & = & 1 & 2 \\ 3^{n} & = & 3 & 1 \end{aligned}

n = 5, φ(5) = 4, U_{5} = {1, 2, 3, 4} = ⟨2⟩.

Generuojančio grupe_{‘} U_{5} elemento laipsniai mod 5:

\begin{aligned}n & = & 1 & 2 & 3 & 4 \\ 2^{n} & = & 2 & 4 & 3 & 1 \end{aligned}

n = 6, φ(6) = 2, U_{6} = {1, 5} = ⟨5⟩.

Generuojančio grupe_{‘} U_{6} elemento laipsniai mod 6:

\begin{aligned}n & = & 1 & 2 \\ 5^{n} & = & 5 & 1 \end{aligned}

n = 7, φ(7) = 6, U_{7} = {1, 2, 3, 4, 5, 6} = ⟨3⟩.

Generuojančio grupe_{‘} U_{7} elemento laipsniai mod 7:

\begin{aligned}n & = & 1 & 2 & 3 & 4 & 5 & 6 \\ 3^{n} & = & 3 & 2 & 6 & 4 & 5 & 1 \end{aligned}

n = 8, φ(8) = 4, U_{8} = {1, 3, 5, 7}.

Grupės U_{8} elementu_{‘} laipsniai mod 8:

\begin{aligned}n & = & 1 & 2 & 3 & 4 \\ 3^{n} & = & 3 & 1 & 3 & 1 \\ 5^{n} & = & 5 & 1 & 5 & 1 \\ 7^{n} & = & 7 & 1 & 7 & 1. \end{aligned}

Taigi U_{8} yra pirmoji neciklinė grupė. Žemiau suformuluotas teiginys atsakys mums kodėl.

6.14 teiginys. Grupė U_{n} yra ciklinė tik tada, kai n = 1, 2, 4, p^{α}, 2p^{α}; čia p – nelyginis pirminis skaičius, o α – bet kuris natūralusis skaičius.

Cikline_{‘} grupe_{‘} U_{n} generuojantis elementas vadinamas primityvia_{‘}ja šaknimi moduliu n.

Žinome, jeigu a yra ciklinės grupės U_{n} primityvioji šaknis mod n, tai \overline{a}^{φ(n)} = \overline{1} (Oilerio–Ferma teorema). Priešingai, jeigu U_{n} nėra ciklinė, t.y. n ≠ 1, 2, 4, p^{α}, 2p^{α}, p > 2 – pirminis skaičius, o α ∈ ℕ, tai su visais a ∈ U_{n}

a^{\frac{φ(n)}{2}} = 1.

6.15 pavyzdys. U_{18} yra ciklinė grupė, nes 18 = 2 · 3^{2}, |U_{18}| = φ(18) = 6 ir U_{18} = {1, 5, 7, 11, 13, 17} = ⟨5⟩.

Generuojančio grupe_{‘} U_{18} elemento laipsniai mod 18:

\begin{aligned}n & = & 1 & 2 & 3 & 4 & 5 & 6 \\ 5^{n} & = & 5 & 7 & 17 & 13 & 11 & 1. \end{aligned}

Kiek iš viso yra primityviu_{‘}ju_{‘} šaknu_{‘} moduliu n? I_{‘} ši_{‘} klausima_{‘} atsakys toks teiginys:

6.16 teiginys. Grupėje U_{n} yra φ ( φ(n)) primityviu_{‘}ju_{‘} šaknu_{‘} moduliu n.

I_{‘} rodymas. Jeigu grupėje U_{n} yra nors viena primityvioji šaknis, pavyzdžiui a, tai U_{n} – ciklinė grupė: U_{n} = {a, a^{2}, …, a^{φ(n)}}, a^{φ(n)} = 1. Pagal 5.43 teiginio 4b dali_{‘} šioje ciklinėje grupėje yra φ ( φ(n)) generuojančiu_{‘} šia_{‘} cikline_{‘} grupe_{‘} elementu_{‘}, o tai ir yra primityviosios šaknys mod n.

△

6.17 pastaba. Jeigu a yra primityvioji šaknis modn ir DBD(k, φ(n)) = 1, tai ir a^{k}, yra primityvioji šaknis mod n (žr. 5.42 teiginio 4b) dali_{‘}).

6.18 pavyzdys. Iš 6.15 pavyzdžio matėme, kad 5 yra primityvioji šaknis mod 18. Elemento \overline{5}^{k} eilė grupėje U_{18} lygi

\frac{φ(18)}{DBD (k, φ(18))} = \frac{6}{DBD(k, 6)}.

Šis elementas bus primityvioji šaknis mod 18 tik tada, kai DBD(k, 6) = 1, 1 ⩽ k ⩽ 5.

Vienas iš tokiu_{‘} skaičiu_{‘} k yra 5, todėl 5^{5} ≡ 11 (mod 18) – kita primityvioji šaknis (mod 18).

Dabar pateiksime algoritma_{‘}, pagal kuri_{‘} galima rasti primityvia_{‘}ja_{‘} šakni_{‘} mod p, kai p > 2 yra pirminis skaičius.

6.19 algoritmas. Žinoma: p – nelyginis pirminis skaičius. Rezultatas: a – primityvioji šaknis mod p.

1. Randame skaičiaus p − 1 kanonini_{‘} skaidini_{‘}:

p − 1 = p_{1}^{m_{1}}p_{2}^{m_{2}} … p_{k}^{m_{k}}; priskiriame a := 1, i := 1.

2. Priskiriame a := a + 1.

3. Skaičiuojame b := a^{\frac{p−1}{p_{i}}} (žr. 5.11 algoritma_{‘}).

Jeigu b = 1, pereiname prie 2.

Jeigu b ≠ 1, tai i := i + 1.

4. Jeigu i > k, išvedame a.

Jeigu i ⩽ k, pereiname prie 2.

△

6.20 pavyzdys. U_{11} yra ciklinė grupė, U_{11} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. 11 − 1 = 10 = 2 · 5.

Jeigu a = 2, tai

2^{\frac{10}{2}} = 2^{5} = 32 ≡ 10 mod 11 ≡ / 1 (mod 11),
2^{\frac{10}{5}} = 2^{2} = 4 ≡ /1 (mod 11).

Taigi 2 yra primityvioji šaknis mod 11. Jeigu a = 3, tai 3^{\frac{10}{2}} = 3^{5} = 243 ≡ 1 (mod 11) ir todėl 3 nėra primityvioji šaknis mod 11.

Apibendrinkime mūsu_{‘} samprotavimus apie primityviu_{‘}ju_{‘} šaknu_{‘} mod n paieška_{‘}:

Kai n = 2 arba n = 4, tai a = n − 1 yra primityvioji šaknis mod n. Kai n = p, p – pirminis skaičius, tai primityvia_{‘}sias šaknis galima rasti

pagal 6.19 algoritma_{‘}.

Kai n = p^{α} arba n = 2p^{α}, p – pirminis nelyginis skaičius, o α ∈ ℕ, α ⩾ 2, primityvia_{‘}sias šaknis mod n galima rasti remiantis tokiu teiginiu:

6.21 teiginys. 1. Tegu a yra primityvioji šaknis mod p, p – pirminis nelyginis skaičius. Tada:

a) jeigu a^{p−1} ≡ /1(modp^{2}), tai a – primityvioji šaknis modp^{α}, α ⩾ 2;

b) jeigu (a + p)^{p−1} ≡/1 (mod p^{2}), tai a + p – primityvioji šaknis mod p^{α}, α ⩾ 2.

2. Tegu b yra primityvioji šaknis modp^{α}, p – pirminis skaičius, α ⩾ 2. Tada:

a) jeigu b nelyginis, tai b – primityvioji šaknis mod 2p^{α};

b) jeigu b + p nelyginis, tai b + p^{α} – primityvioji šaknis mod 2p^{α}.

6.22 pastabos. 1. Pastebėkime, kad tik vienas iš skaičiu_{‘} b arba b + p yra nelyginis. Paaiškinsime 6.21 teiginio 1 dalies sa_{‘}lyga_{‘}:

(a + p)^{p−1} = a^{p−1} + (p − 1)pa^{p−2} + C_{p−1}^{2}p^{2}a^{p−3} + …

≡ a^{p−1} + (p − 1)pa^{p−2} (mod p^{2}) ≡ a^{p−1} + p^{2}a^{p−2} − pa^{p−2}

≡ a^{p−1} − pa^{p−2} (mod p^{2}).

Jeigu a^{p−1} ≡ 1(modp^{2}), tai (a+p)^{p−1} ≡ 1−pa^{p−2}(modp^{2}) ≡ /1(modp^{2}), nes DBD (a, p) = 1 ir pa^{p−2} ≡ / 0 (mod p^{2}).

Jeigu (a+p)^{p−1} ≡ 1(modp^{2}), tai 1 ≡ a^{p−1} −pa^{p−2}(modp^{2}) ir a^{p−1} ≡ / 1 (mod p^{2}) (priešingu atveju būtu_{‘} pa^{p−2} ≡ 0 (mod p^{2}) ir DBD (a, p) ≠ 1).

2. Norint rasti primityvia_{‘}ja_{‘} šakni_{‘} mod p^{α}, p > 2 – pirminis skaičius, α ⩾ 2, reikia:

a) pagal 6.19 algoritma_{‘} rasti a – primityvia_{‘}ja_{‘} šakni_{‘} mod p;

b) skaičiuoti a_{1} ≡ a^{p−1}(mod p^{2});

c) jeigu a_{1} ≠ 1, tai a – primityvioji šaknis mod p^{α}, α ⩾ 2;

jeigu a_{1} = 1, tai a + p – primityvioji šaknis mod p^{α}, α ⩾ 2.

3. Norint rasti primityvia_{‘}ja_{‘} šakni_{‘} mod 2p^{α}, p > 2 – pirminis skaičius, α ⩾ 2, reikia:

a) pagal 6.19 algoritma_{‘} rasti b – primityvia_{‘}ja_{‘} šakni_{‘} mod p;

b) jeigu b nelyginis, tai b – primityvioji šaknis mod 2p^{α};

jeigu b lyginis, tai b + p^{α} – primityvioji šaknis mod 2p^{α}. Dabar panagrinėkime neciklines U_{n} grupes. Natūralu pradėti nuo

atvejo, kai n = 2^{α}, α ⩾ 3, α ∈ ℕ.

6.23 teiginys. U_{2^{α}} ≈ ℤ_{2} × ℤ_{2^{α−2}}, kur ℤ_{2}, ℤ_{2^{α−2}} yra adicinės ciklinės grupės.

Grupėje U_{2^{α}} nesunkiai galime rasti elementa_{‘}, kurio eilė šioje grupėje yra maksimali. Tai elementas 5 ∈ U_{2^{α}}, nes iš ord_{U_{2^{α}}} (5) = 2^{α−2} gauname, kad 2^{α} dalijasi iš ord_{U_{2^{α}}} (5) ir ord_{U_{2^{α}}} (5) ⩽ 2^{α−1} (i_{‘}rodykite!). Tada

5^{2^{k}} ≡ 1 (mod 2^{α}) ⟺ (5^{2^{k}} − 1) ≡ 0 (mod 2^{α})
⟺ (5 − 1)(5^{2^{0}} + 1)(5^{2^{1}} + 1) … (5^{2^{k−1}} + 1) ≡ 0 (mod 2^{α})
⟺ (5 + 1)(5^{2} + 1)(5^{2^{2}} + 1) … (5^{2^{k−1}} + 1) ≡ 0 (mod 2^{α−2})

ir, kai k = α − 1,

(5 + 1)(5^{2} + 1)(5^{2^{2}} + 1) … (5^{2^{α−2}} + 1) ≡ 0 (mod 2^{α−2}).

6.24 pastaba. Remiantis pastaruoju teiginiu, bet kuri_{‘} grupės U_{2^{α}} elementa_{‘} galima užrašyti taip:

(−1)^{i}5^{j}, 0 ⩽ i ⩽ 1, 1 ⩽ j ⩽ 2^{α−1}.

Neciklinėse grupėse U_{n} yra svarbūs tie elementai, kuriu_{‘} eilė šioje grupėje yra maksimali. Tai maksimalios eilės grupės elementai.

6.25 teiginys. Jeigu a yra maksimalios eilės grupės U_{n} elementas, tai bet kuriam b ∈ U_{n} teisinga

ord_{U_{n}}(a) dalijasi iš ord_{U_{n}}(b).

I_{‘} rodymas. Iš 6.12 teiginio 3) dalies žinome, kad egzistuoja toks c ∈ U_{n}, kad ord_{U_{n}}(c) = BMK(ord_{U_{n}}(a), ord_{U_{n}}(b)). Bet ord_{U_{n}}a yra maksimalus grupėje, todėl

ord_{U_{n}}(c) =BMK (ord_{U_{n}}(a), ord_{U_{n}}(b)) ⩽ ord_{U_{n}}(a),
BMK (ord_{U_{n}}(a), ord_{U_{n}}(b)) = ord_{U_{n}}(a)

ir todėl ord_{U_{n}}(a) dalijasi iš ord_{U_{n}}(b).

△

6.26 apibrėžimas. Funkcija λ : ℕ → ℕ,

λ(n) = max{ord_{U_{n}}(a) | a ∈ U_{n}},

vadinama maksimalios eilės funkcija.

6.27 pavyzdžiai.

λ(1) = φ(1) = 1, λ(2) = φ(2) = 1, λ(4) = φ(4) = 2,

λ(p^{α}) = φ (p^{α}) = p^{α} − p^{α−1} = p^{α−1}(p − 1), p > 2 − pirminis skaičius,

λ(2p^{α}) = φ (2p^{α}) = (p − 1)p^{α−1}, p > 2 − pirminis skaičius,

λ(2^{α}) = 2^{α−2}, α ⩾ 3.

Maksimalios eilės funkcijos λ reikšmėms λ(n) skaičiuoti mes pasitelksime skaičiaus n kanonini_{‘} skaidini_{‘} n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{r}^{α_{r}}, p_{1}, p_{2}, …, p_{r} – skirtingi pirminiai skaičiai, ir funkcijos λ reikšmes λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), λ(p_{r}^{α_{r}}). Tam talkins

6.28 kinu_{‘} teorema liekanoms. Tegu m_{1}, m_{2}, …, m_{k} yra poromis tarpusavyje pirminiai skaičiai, t.y. DBD (m_{i}, m_{j}) = 1, kai i ≠ j, M = m_{1}m_{2} … m_{k}; a_{1}, a_{2}, …, a_{k} – bet kurie sveikieji skaičiai. Lyginiu_{‘} sistema

x ≡ a_{1} (mod m_{1}),
x ≡ a_{2} (mod m_{2}),
. . . . . . . . . . . . . . . . .
x ≡ a_{k} (mod m_{k})

(∗)

turi vieninteli_{‘} sprendini_{‘} x moduliu M.

Kitais žodžiais sakant, turime bijekcija_{‘} f : ℤ_{M} → ℤ_{m_{1}} × ℤ_{m_{2}} × … × ℤ_{m_{k}}, kuri bet kuriam x, 0 ⩽ x < M − 1, priskiria f(x) = (a_{1}, a_{2}, …, a_{k}); čia a_{i} ≡ x mod m_{i}, i = 1, 2, …, k.

I_{‘} rodyma_{‘} pateiksime algoritmais. Iš pradžiu_{‘} nurodysime būda_{‘}, kaip išspre_{‘}sti (∗) sistema_{‘}, kai k = 2.

6.29 algoritmas. Žinoma: m_{1}, m_{2} > 1 – tarpusavyje pirminiai skaičiai; a_{1}, a_{2} – sveikieji skaičiai.

Rezultatas: toks x, kad x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}).

1. Jeigu a_{1} ⩾ 0, tai x := LIEKANA (a_{1}, m_{1}) [skaičiaus a_{1} dalybos su liekana iš m_{1} liekanos priskyrimas].

2. m_{1}^{−1} := m_{1}^{−1} (mod m_{2}) [žr. 6.8 ir 6.9 algoritmus].

3. q := LIEKANA (m_{1}^{−1} (a_{2} − x), m_{2}).

4. x := x + m_{1}q.

△

Remdamiesi šiuo algoritmu, i_{‘}rodysime kinu_{‘} teorema_{‘}, kai n = 2. Lyginys x ≡ a_{1} (mod m_{1}) yra visada išsprendžiamas, todėl x = a_{1} + m_{1}q; čia q – sveikasis skaičius. Ši_{‘} skaičiu_{‘} rasime, naudodamiesi tuo, kad x ≡ a_{2} (modm_{2}) ir todėl a_{1} +m_{1}q ≡ a_{2} (modm_{2}), q = (a_{2} −a_{1})m_{1}^{−1} (modm_{2}). Taigi q = m_{1}^{−1}(a_{2} − a_{1}) + rm_{2}, r ∈ ℤ ir

x = a_{1} + m_{1}(m_{1}^{−1}(a_{2} − a_{1}) + rm_{2})
= a_{1} + m_{1}m_{1}^{−1}(a_{2} − a_{1}) + rm_{1}m_{2}
≡ a_{1} + m_{1}m_{1}^{−1}(a_{2} − a_{1})(mod m_{1}m_{2})

(išraiškose m_{1}^{−1} yra mod m_{2}).

Sprendinio vienatinumas. Tegu x ir y yra du nagrinėjamos lyginiu_{‘} sistemos sprendiniai. Tada

\begin{matrix}x − y ≡ 0 (mod m_{1}), \\ x − y ≡ 0 (mod m_{2}) \end{matrix}

ir x − y ≡ 0 (mod m_{1}m_{2}), nes DBD (m_{1}, m_{2}) = 1.

△

6.30 pavyzdys.

\begin{matrix}x ≡ 15 (mod 6), \\ x ≡ 4 (mod 11). \end{matrix}

1. 15 = 6 · 2 + 3, todėl pirmasis mūsu_{‘} sistemos lyginys keičiamas lyginiu x ≡ 3 (mod 6).

2. x = 3 + 6q.

3. DBD (6, 11) = 1 – pirminis skaičius, todėl 6^{−1} = 6^{φ(11)−1} = 6^{9} ≡ 2 (mod 11).

4. q ≡ 2 (4 − 3) (mod 11) = 2 (mod 11) ir x = 3 + 6 · 2 = 15 (mod 6 · 11) = 15 (mod 66).

Patikrinimas.

\begin{aligned}15 & = 2 · 6 + 3 ≡ 3 (mod 6), \\ 15 & = 1 · 11 + 4 ≡ 4 (mod 11). \end{aligned}

Apibendrinsime 6.29 algoritma_{‘}.

6.31 algoritmas. Žinoma: a_{1}, a_{2}, …, a_{k} – sveikieji skaičiai; m_{1}, m_{2}, …, m_{k} – poromis tarpusavyje pirminiai skaičiai, t.y. DBD (m_{i}, m_{j}) = 1, i ≠ j.

Rezultatas: vienintelis x (mod m_{1}m_{2} … m_{k}), tenkinantis lyginius x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}), …, x ≡ a_{k} (mod m_{k}).

1. m := 1, x := LIEKANA (a_{1}, m_{1}), i := 1.

2. m := m · m_{1}; m^{−1} := m^{−1} (mod m_{i+1}).

3. q_{i+1} := LIEKANA (m^{−1}(a_{i+1} − x), m_{i+1}).

4. x := x + mq_{i+1}.

5. i := i + 1; jeigu i ⩽ k − 1, tai gri_{‘}žtame prie 2;

jeigu i > k − 1, tai rezultatas yra x.

△

6.32 pastaba. Pastarasis algoritmas grindžiamas 6.29 algoritmo taikymu lyginiu_{‘} poroms: rade_{‘} lyginiu_{‘} sistemos x ≡ a_{1} (mod m_{1}), x ≡ a_{2}(mod m_{2}) vieninteli_{‘} sprendini_{‘} x_{1} (mod m_{1}m_{2}), sprendžiame sistema_{‘} x ≡ x_{1}(modm_{1}m_{2}), x ≡ a_{3}(modm_{3}). Išsprende_{‘} ja_{‘} ir surade_{‘} vieninteli_{‘} sprendini_{‘} x_{2} (mod m_{1}m_{2}m_{3}), sprendžiame kita_{‘} sistema_{‘} x ≡ x_{2} (mod m_{1}m_{2}m_{3}), x ≡ a_{4} (mod m_{4}) ir t.t.

6.33 pavyzdys.

x ≡ −5 (mod 7),
x ≡ 6 (mod 9),
x ≡ 4 (mod 8).

Sprendžiame lyginiu_{‘} sistema_{‘}

\begin{matrix}x ≡ −5 (mod 7), \\ x ≡ 6 (mod 9). \end{matrix}

1.1. −5 = 7 · (−1) + 2, todėl pirma_{‘}ji_{‘} sistemos lygini_{‘} keičiame lyginiu x ≡ 2 (mod 7).

1.2. x = 2 + 7q_{1}, q_{1} ∈ ℤ. 1.3. DBD (7, 9) = 1, todėl 7^{−1} ≡ 7^{φ(9)−1}(mod 9) = 7^{5} ≡ 4 (mod 9). 1.4. q_{1} = 4(6 − 2) = 16 ≡ 7 (mod 9);

x = 2 + 7 · 7 = 51 (mod 7 · 9). Sprendžiame lyginiu_{‘} sistema_{‘} x ≡ 51 (mod 63), x ≡ 4 (mod 8). 2.1. x = 51 + 63q_{2}, q_{2} ∈ ℤ. 2.2. DBD (63, 8) = 1, todėl 63^{−1} ≡ 63^{φ(8)−1}(mod 8) = 63^{3}(mod 8) ≡

7 (mod 8).

2.3. q_{2} = 7(4 − 51) = 7 · (−47) = −329 ≡ −9 (mod 8) ≡ 7 (mod 8), x = 51 + 63 · 7 = 492 (mod 7 · 9 · 8).

Patikrinimas:

492 = 70 · 7 + 2 ≡ 2 (mod 7),
492 = 54 · 9 + 6 ≡ 6 (mod 9),
492 = 61 · 8 + 4 ≡ 4 (mod 8).

Sistemos sprendini_{‘} 492 (mod 7 · 9 · 8) galima užrašyti ir taip: 492 = 2 + 7 · 7 + 7 · (7 · 9).

Bendruoju atveju lyginiu_{‘} sistemos (∗) sprendini_{‘} galima užrašyti ir taip:

x = q_{1} + q_{2} · m_{1} + q_{3}(m_{1} · m_{2}) + … + q_{k}(m_{1} · m_{2} · . . . · m_{k−1}); čia q_{1} = LIEKANA (a_{1}, m_{1}), o q_{i}, i > 1 iš 6.31 algoritmo.

Baigdami mūsu_{‘} kinu_{‘} teoremos liekanoms nagrinėjima_{‘}, pastebėsime, kad funkcija f : ℤ_{M} → ℤ_{m_{1}} × ℤ_{m_{2}} × … ℤ_{m_{k}}, M = m_{1}m_{2} … m_{k}, DBD (m_{i}, m_{j}) = 1, i ≠ j, yra ne tik bijekcija, bet ir žiedu_{‘} izomorfizmas: ℤ_{M} ≈ ℤ_{m_{1}} × ℤ_{m_{2}} × … × ℤ_{m_{k}}:

jeigu x ≡ a_{i} (mod m_{i}),

y ≡ b_{i} (mod m_{i}), 1 ⩽ i ⩽ k,
tai x + y ≡ a_{i} + b_{i} (mod m_{i}),
x · y ≡ a_{i} · b_{i} (mod m_{i}), 1 ⩽ i ⩽ k,

ir todėl

f(x + y) = (a_{1} + b_{1}, a_{2} + b_{2}, …, a_{k} + b_{k}) = (a_{1}, a_{2}, …, a_{k})
+ (b_{1}, b_{2}, …, b_{k}),
f(x · y) = (a_{1} · b_{1}, a_{2} · b_{2}, …, a_{k} · b_{k}) = (a_{1}, a_{2}, …, a_{k}) · (b_{1}, b_{2}, …, b_{k}).

Panašiai galėtume parodyti, kad

U_{M} ≈ U_{m_{1}} × U_{m_{2}} × … × U_{m_{k}};

čia U_{i} yra žiedo ℤ_{i} elementu_{‘}, turinčiu_{‘} atvirkštinius, grupė.

Gri_{‘}žkime prie maksimalios eilės funkcijos λ. Tegu n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{k}^{α_{k}} yra kanoninis skaičiaus n skaidinys, o a_{i} – maksimalios eilės λ(p_{i}^{α_{i}}) = φ (p_{i}^{α_{i}}) = p_{i}^{α_{i}} − p_{i}^{α_{i−1}} elementas grupėje U_{p_{i}^{α_{i}}}, 1 ⩽ i ⩽ k (ši_{‘} elementa_{‘} a_{i} jau mokame rasti).

Lyginiu_{‘} sistemos

x ≡ 1 (mod p_{1}^{α_{1}}),
. . . . . . . . . . . . . . . . .
x ≡ 1 (mod p_{i−1}^{α_{i−1}}),
x ≡ a_{i} (mod p_{i}^{α_{i}}),
x ≡ 1 (mod p_{i+1}^{α_{i+1}}),
. . . . . . . . . . . . . . . . .
x ≡ 1 (mod p_{k}^{α_{k}})

vienintelio sprendinio x_{i} (mod n) eilė grupėje U_{n} yra

ord_{U_{n}}x_{i} = ord_{U_{p_{i}}^{α_{i}}} (a_{i}) = λ(p_{i}^{α_{i}}).
Atsižvelge_{‘} i_{‘} 6.13 pastaba_{‘}, galime rasti toki_{‘} b ∈ U_{n}, kad
ord_{U_{n}}(b) = BMK(λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})).

Taigi λ(n) ⩾ BMK(λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})). Priešingai, jeigu a ∈ U_{n}, tai žinome, kad

ord_{U_{p_{i}}^{α_{i}}} (a) dalo λ(p_{i}^{α_{i}}), 1 ⩽ i ⩽ k,

ir todėl ord_{U_{p_{i}}^{α_{i}}} (a) dalo BMK(λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})) = s.

Tada

a^{s} ≡ 1 (mod p_{i}^{α_{i}}), 1 ⩽ i ⩽ k

ir

a^{s} ≡ 1 (mod n),
ord_{U_{n}}(a) ⩽ s,
λ(n) ⩽ s = BMK(λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})).

Taigi λ(n) = BMK(λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})).

6.34 pavyzdys. λ(120) = BMK(λ(2^{3}), λ(3), λ(5)) = BMK (2, 2, 4)= 4.

Apibendrinsime mūsu_{‘} žinias apie grupiu_{‘} U_{n} maksimalios eilės funkcija_{‘} λ.

6.35 teiginys. 1. Funkcijos λ reikšmės:

λ(n) = \{ \begin{matrix}1, & kai n = 1, 2, \\ 2, & kai n = 4, \\ p^{α−1}(p − 1), & kai n = p^{α}, p − nelyginis \\ & pirminis skaičius, \\ 2^{α−2}, & kai n = 2^{α}, α ⩾ 3, \\ BMK (λ(p_{1}^{α_{1}}), λ(p_{2}^{α_{2}}), …, λ(p_{k}^{α_{k}})), & kai n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{k}^{α_{k}}− \\ & kanoninis skaičiaus n \\ & skaidinys. \end{matrix}

2. Oilerio–Ferma teoremos analogas funkcijai λ:

Kai DBD (a, n) = 1, tai a^{λ(n)} ≡ 1 (mod n).

3. Kai n = p_{1}p_{2} … p_{k} yra bekvadratis skaičius (p_{1}, p_{2}, …, p_{k} – skirtingi pirminiai skaičiai), tai su visais a ∈ ℤ_{n} teisinga lygybė a^{λ(n)+1} ≡ a (mod n).

I_{‘} rodymas. 2. Kai a ∈ U_{n}, tai ord_{U_{n}}(a) dalo λ(n), t.y. λ(n) = ord_{U_{n}}(a) · l ir

a^{λ(n)} = (a^{ord_{Un} (a)})^{l} ≡ 1 (mod n).