Algebros paskaitos informatikams. Rimantas Grigutis.

2 paskaita. Lyginiai.Likiniu̧ klasiu̧ žiedas. Baigtiniai kūnai. Pirmojo laipsnio lyginiu̧ sprendimas.

Apibrėžimas. Tegu m ≥ 1 yra sveikasis skaičius. Sakysime, kad du sveikieji skaičiai a ir b lygsta moduliu m, jeigu skaičius a − b dalijasi iš m. Rašysime: a ≡ b (mod m) . Ši̧ užraša̧ vadinsime lyginiu.

Pastaba. Su visais a, b ∈ Z yra teisinga a ≡ b (mod 1) . Pavyzdys. a ≡ b (mod 2) tada ir tik tada, kada arba a ir b yra abu lyginiai,

arba abu yra nelyginiai skaičiai.

Pagringinės lyginiu̧ savybės yra šios:

1. Refleksyvumas: su visais a ∈ Z , a ≡ a (mod m) .

2. Simetriškumas: \begin{matrix}a, b ∈ Z \\ a ≡ b (mod m) \end{matrix} \} ⟺ b ≡ a (mod m) .

3. Tranzityvumas: \begin{matrix}a, b, c ∈ Z \\ a ≡ b (mod m) \\ b ≡ c (mod m) \end{matrix} \} ⟹ a ≡ c (mod m) .

4. \begin{matrix}a, b, c, d ∈ Z \\ a ≡ c (mod m) \\ b ≡ d (mod m) \end{matrix} \} ⟹ a ± b ≡ c ± d (mod m) .

5. \begin{matrix}a, b, c, d ∈ Z \\ a ≡ c (mod m) \\ b ≡ d (mod m) \end{matrix} \} ⟺ a · b ≡ c · d (mod m) .

6. \begin{matrix}a, b ∈ Z \\ m, c > 1 \\ ac ≡ bc (mod mc) \end{matrix} \} ⟹ a ≡ b (mod m) .

7. \begin{matrix}a, b ∈ Z \\ (m, c) = 1 \\ ac ≡ bc (mod m) \end{matrix} \} ⟹ a ≡ b (mod m) .

Pastaba. 3 ≡ 15 (mod 6) ≠⇒ 1 ≡ 5 (mod 6) , nes 1 ≢ 5 (mod 6) .

8. Kiekvienas sveikasis skaičius a lygsta mod m > 1 su vienu ir tik vienu skaičiumi iš aibės {0, 1, 2, ..., m − 1} .

Likiniu̧ klasės.

Apibrėžimas. Tegu a, m ∈ Z, ir m > 1. Sveiku̧ju̧ skaičiu̧ aibės Z poaibi̧

{b ∈ Z|b ≡ a (mod m)}

vadinsime likiniu̧ klase moduliu m, kuriai atstovauja a, arba tiesiog likiniu̧ klase, ir žymėsime _{m}K_{a}, arba K_{a}, arba ā.

Pavyzdžiai. 1. m = 2, a = 0 : K_{0} = ¯0 = {b ∈ Z|b ≡ 0 (mod 2)} = 2Z yra visu̧ lyginiu̧ skaičiu̧ poaibis.

2. m = 2, a = 1 : K_{1} = ¯1 = {b ∈ Z|b ≡ 1 (mod 2)} yra visu̧ nelyginiu̧ skaičiu̧ poaibis.

3. m = 2, a = 2 : K_{2} = ¯2 = {b ∈ Z|b ≡ 2 (mod 2)} = 2Z yra visu̧ lyginiu̧ skaičiu̧ poaibis.

Svarbiausios likiniu̧ klasiu̧ savybės yra šios:

1. Refleksyvumas: a ∈ Z ⟹ a ∈ K_{a}.

2. Simetriškumas: a ∈ K_{b} ⟹ b ∈ K_{a}.

3. Tranzityvumas: \begin{matrix}a ∈ K_{b} \\ b ∈ K_{c} \end{matrix} \} ⟹ a ∈ K_{c}.

4. Tegu m > 1. Tada likiniu̧ klasės K_{0}, K_{1}, K_{2}, ..., K_{m−1} yra sveiku̧ju̧ skaičiu̧ aibės Z skaidinys, t.y.

(a) Z = K_{0} ∪ K_{1} ∪ K_{2} ∪ ... ∪ K_{m−1};

(b) jeigu K_{a} ∩ K_{b} ≠ ∅, tai K_{a} = K_{b} , 0 ≤ a, b ≤ m − 1.

Apibrėžimas. Tegu m > 1. Aibȩ {K_{0}, K_{1}, K_{2}, ..., K_{m−1}} vadinsime likiniu̧ klasiu̧ aibe moduliu m ir žymėsime Z_{m}.

Aibėje Z_{m} galima apibrėžti šiuos veiksmus.

Apibrėžimas. \begin{matrix}K′, K′′ ∈ Z_{m} \\ a ∈ K′, b ∈ K′′ \end{matrix} \} , tada \begin{matrix}K′ + K′′ =^{def} K_{a+b} \\ K′ · K′′ =^{def} K_{a·b} \end{matrix} .

Teiginys. Sudėties ir sandaugos veiksmai likiniu̧ klasėms apibrėžti korektiškai, t.y. jie nepriklauso nuo klasiu̧ atstovu̧ a ir b parinkimo.

I̧rodymas.Tegu a, a′ ∈ K′ ir b, b′ ∈ K′′, t.y. a ≡ a′ (mod m) ir b ≡ b′ (mod m) . Tada tiek a+b = a′ +b′ (mod m) , tiek a·b ≡ a′ ·b′ (mod m) ir todėl K_{a+b} = K_{a′+b′} ir K_{a·b} = K_{a′·b′} .

I̧rodyta.

Pavyzdžiai.Pateiksime veiksmu̧ lenteles Z_{3} ir daugybos lentelȩ Z_{6}.

+ ¯0 ¯1 ¯2 ¯0 ¯0 ¯1 ¯2 ¯1 ¯1 ¯2 ¯0 ¯2 ¯2 ¯0 ¯1 \begin{matrix}· & ¯0 & ¯1 & ¯2 \\ ¯0 & ¯0 & ¯0 & ¯0 \\ ¯1 & ¯0 & ¯1 & ¯2 \\ ¯2 & ¯0 & ¯2 & ¯1 \end{matrix}

\begin{matrix}· & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{matrix}

Veiksmu̧ su likiniu̧ klasėmis savybės.

Tegu ā, b̄, c̄ ∈ Z_{m}.

1. Sudėties asociatyvumas: (ā + b̄) + c̄ = ā + (b̄ + c̄) .

2. Neutralaus elemento sudėties atžvilgiu egzistavimas: egzistuoja tokia klasė ¯0, kad ā + ¯0 = ā. Ši klasė vadinama nuline klase.

3. Atvirkštinės klasės sudėties atžvilgiu egzistavimas: su visais ā egzistuoja toks b̄, kad ā + b̄ = ¯0. Elementas b̄ vadinamas atvirkštiniu elementui ā sudėties atžvilgiu ir žymimas: −ā.

4. Sudėties komutatyvumas: ā + b̄ = b̄ + ā.

5. Sandaugos asociatyvumas: (ā · b̄) · c̄ = ā · (b̄ · c̄) .

6. Sandaugos komutatyvumas: ā · b̄ = b̄ · ā.

7. Neutralaus elemento sandaugos atžvilgiu egzistavimas: egzistuoja tokia klasė ¯1, kad ā · ¯1 = ā. Ši klasė vadinama nuline klase.

8. Distributyvumas: \begin{matrix}ā · (b̄ + c̄) = ā · b̄ + ā · c̄ \\ (ā + b̄) · c̄ = ā · c̄ + b̄ · c̄ \end{matrix} .

Algebrinės struktūros.

Apibrėžimai. 1.Aibė, kurioje apibrėžtas sudėties veiksmas ir teisingos 1-3 savybės, vadinama adicine grupe ( arba tiesiog, grupe); jeigu teisinga ir 4 savybė, tai vadiname komutatyvia̧ja grupe( analogiškai yra apibrėžiama grupė sandaugos veiksmo atžvilgiu arba multiplikacinė grupė).

2. Aibė, kurioje apibrėžti ir sudėties, ir sandaugos veiksmai ir

- teisingos 1-5 ir 8 savybės, vadinama žiedu;

- teisingos 1-6 ir 8 savybės, vadinama komutatyviu žiedu;

- teisingos 1-5 ir7,8 savybės, vadinama žiedu su vienetu.

3. Tegu A− komutatyvus žiedas su vienetu ( teisingos 1-8 savybės). Jeigu elementui α ∈ A egzistuoja toks elementas β ∈ A, kad α · β = ¯1 ( ¯1− neutralusis A elementas sandaugos atžvilgiu), tai sakome, kad elementas α turi atvirkštini̧ sandaugos atžvilgiu ir žymime β = α^{−1}. Jeigu visi \underline{nenuliniai} komutatyvaus su vienetu žiedo elementai turi atvirkštinius sandaugos atžvilgiu, tai toks žiedas vadinamas kūnu.

Pavyzdžiai. 1. Realiu̧ju̧ skaičiu̧ aibė R, racionaliu̧ju̧ skaičiu̧ aibė Q yra kūnai.

2. Sveiku̧ju̧ skaičiu̧ aibė Z yra komutatyvus žiedas su vienetu, bet ne kūnas, nes visi sveikieji skaičiai ≠ ±1 neturi atvirkštiniu̧ sandaugos atžvilgiu.

3. Lyginiu̧ sveiku̧ju̧ skaičiu̧ aibė 2Z yra komutatyvus žiedas be vieneto, nes 1 yra nelyginis skaičius.

4. Likiniu̧ moduliu m klasiu̧ aibė Z_{m} yra komutatyvus žiedas su vienetu, bet ne visada kūnas, pavyzdžiui Z_{2}, Z_{3} yra kūnai, bet Z_{4} nėra kūnas, nes ¯2·¯1 = ¯2 ≠ ¯1; ¯2 · ¯2 = ¯0 ≠ ¯1; ¯2 · ¯3 = ¯2 ≠ ¯1.

Nustatysime sa̧lygas, kurioms esant Z_{m} yra kūnas. Pradėsime apibrėžimu.

Apibrėžimas. Likiniu̧ moduliu m klasė K vadinama primityvia̧ja klase, jeigu egzistuoja toks a ∈ K, kad (a, m) = 1.

Lema. Primityvioje klasėse moduliu m visi skaičiai yra tarpusavyje pirminiai su m.

I̧rodymas. Tegu K− primityvioji klasė moduliu m ir a- toks šios klasės skaičius, kad (a, m) = 1, t.y. ax + my = 1, čia x, y ∈ Z. Jei b ∈ K, tai a ≡ b (mod m) ir a−b = mt su t ∈ Z, ir a = b+mt. Tada ax+my = (b + mt) x+my = bx + m (tx + y) = 1 ir todėl (b, m) = 1.

I̧rodyta.

Teorema. Likiniu̧ moduliu m klasė K yra primityvioji tada ir tik tada, kada K turi atvirkštinȩ sandaugos atžvilgiu klasȩ žiede Z_{m}.

I̧rodymas. Tegu K− primityvioji klasė moduliu m ir a ∈ K. Tada K = K_{a} ir (a, m) = 1, t.y. ax + my = 1. Turime

K_{ax+my} = K_{1}
K_{a}K_{x} + K_{m}K_{y} = K_{1}
K_{a}K_{x} = K_{1} , nes K_{m} = K_{0}.

Priešingai, jei klasė K_{a} turi atvirkštinȩ klasȩ K_{b}, t.y. K_{a} · K_{b} = K_{1}, tai

K_{ab} = K_{1}

ab − 1 = mt , čia t - sveikas skaičius ab − mt = 1

(a, m) = 1.

I̧rodyta.

Teorema. Žiedas Z_{m} yra kūnas tada ir tik tada, kada m yra pirminis skaičius.

I̧rodymas. Tegu skaičius m− pirminis. Tada (1, m) = (2, m) = ⋯ = (m − 1, m) = 1 ir todėl visos nenulinės klasės moduliu m yra primityviosios ir turi atvirkštines klases.

Tegu m− sudėtinis skaičius, t.y. m = a · b , čia a > 1 ir b > 1. Tada \underline{nenulinė} klasė K_{a} nėra primityvi, nes (a, m) = a > 1.

I̧rodyta.

Lyginio ax ≡ b (mod m) sprendimas.

Nagrinėkime du atvejus: (a, m) = 1 ir (a, m) = d > 1.

1. (a, m) = 1.

Šiuo atveju, naudodamiesi Euklido algoritmu, galime rasti tokius c, q ∈ Z, kad ac + mq = 1. Tada

abc + mbq = b ⇒ abc = b − mbq ⇒ a (bc) ≡ b (mod m) .

Gavome, kad x_{0} = bc yra lyginio sprendinys. Tegu dabar x = x_{1} yra kitas šio lyginio sprendinys, t.y. ax_{1} ≡ b (mod m) .

Tada \begin{matrix}ax_{0} ≡ ax_{1} (mod m) \\ (a, m) = 1 \end{matrix} \} ⇒ x_{0} ≡ x_{1} (mod m) .

Iš kitos pusės, jeigu y ≡ x_{0} (mod m) , tai ay ≡ ax_{0} ≡ b (mod m) ir todėl y yra lyginio sprendinys.

Taigi, jeigu x_{0} yra lyginio sprendinys, tai kitais lyginio sprendiniais yra skaičiai iš _{m}K_{x_{0}} ir tik jie.

2. (a, m) = d > 1. Tam, kad lyginys ax ≡ b (mod m) turėtu̧ sprendini̧ būtina, kad b dalytu̧si iš d. Tikrai, jeigu x = x_{1} yra lyginio sprendinys, tai

\begin{matrix}ax_{1} ≡ b (mod m) \\ (a, m) = d \end{matrix} \} ⇒ \begin{matrix}ax_{1} − b = mq, q ∈ Z \\ a⋮d, m⋮d \end{matrix} \} ⇒ \begin{matrix}ax_{1} − mq = b \\ a = a_{1}d; m = m_{1}d \end{matrix} \}

⇒ a_{1}dx_{1} − m_{1}dq = b ⇒ d (a_{1}x_{1} − m_{1}q) = b ⇒ b⋮d.

Taigi, turime \begin{matrix}b = b_{1}d \\ m = m_{1}d \\ a_{1} = a_{1}d \end{matrix} \} ⇒ a_{1}dx ≡ b_{1}d (mod m_{1}d) ⟺ a_{1}x ≡ b_{1} (mod m_{1})

ir (a_{1}, m_{1}) = 1.

Tegu dabar x = x_{1} yra lyginio a_{1}x ≡ b_{1} (mod m_{1}) sprendinys. Tada lyginio ax ≡ b (mod m) skirtingais sprendiniais mod m yra x_{1}, x_{1} + \frac{m}{d}, x_{1} + 2 · \frac{m}{d}, ..., x_{1} + (d − 1) \frac{m}{d}, visi sprendiniai yra klasėse _{m}K_{x_{1}},_{m} K_{x_{1}+ \frac{m}{d}} , ...,_{m} K_{x_{1}+(d−1) \frac{m}{d}} .

Pavyzdys.

6x ≡ 3 (mod 15) , (6, 15) = 3 = d;
2x ≡ 1 (mod 5) , (2, 5) = 1;
2 · 3 ≡ 1 (mod 5) , nes 2 · 3 + 5 · (−1) = 1.

Gavome, kad lyginio sprendiniai yra x_{1} = 3, x_{1} + \frac{m}{d} = 3 + 5 = 8, x_{1} + 2 · \frac{m}{d} = 3 + 10 = 3 + 10 = 13. Visi sprendiniai yra klasėse _{15}K_{3},_{15} K_{8},_{15} K_{13}.