Algebros paskaitos informatikams. Rimantas Grigutis.

3 paskaita. Klasikinės skaičiu̧ teorijos teoremos.

Primityviu̧ju̧ klasiu̧ multiplikacinė grupė.

Tegu U_{m} yra primityviu̧ju̧ klasiu̧ moduliu m aibė, t.y.

U_{m} = {ā| (a, m) = 1, 0 ≤ a ≤ m − 1} .

Šios aibės elementu̧ skaičiu̧ vadiname Oilerio funkcijos φ m reikšme : φ (m) . Pavyzdžiui, kai p− pirminis skaičius, tai φ (p) = p − 1. Jeigu skaičiaus m kanoninis skaidinys yra m = p_{1}^{α_{1}} ⋯ p_{s}^{α_{s}}, tai φ (m) = m (1 − \frac{1}{p_{1}} ) ⋯ (1 − \frac{1}{p_{s}} ) . Čia mes remiamės svarbiausia Oilerio funkcijos savybe - multiplikatyvumo savybe: jei (m, n) = 1, tai φ (m · n) = φ (m) · φ (n) .

Teiginys. Aibė U_{m} sandaugos atžvilgiu sudaro multiplikacinȩ grupȩ.

I̧rodymas. 1) Tegu α, β ∈ U_{m} ir a ∈ α, b ∈ β, t.y. (a, m) = (b, m) = 1. Tada (ab, m) = 1 ir αβ = K_{ab} ∈ U_{m}.

2) Visoms likiniu̧ klasėms galioja sandaugos asociatyvumo savybė. Todėl α (βγ) = (αβ) γ su visais α, β, γ ∈ U_{m}.

3) Akivaizdu, kad K_{1} ∈ U_{m}.

4) Jei α ∈ U_{m}, tai α · α^{−1} = K_{1}. Tada α = (α^{−1})^{−1} it todėl α^{−1} ∈ U_{m}.

I̧rodyta.

Dabar pateiksime klasikines skaičiu̧ teoremas.

Apibrėžimai. Tegu m > 1− fiksuotas skaičius. Skaičiu̧ a_{0} ∈ K_{0}, a_{1} ∈ K_{1}, ..., a_{m−1} ∈ K_{m−1} aibė {a_{0}, a_{1}, ..., a_{m−1}} vadinama pilna̧ja likiniu̧ sistema mod m. Skaičiai r_{1}, r_{2}, ..., r_{s} , paimti po viena̧ iš kiekvienos primityviosios likiniu̧ klasės mod m sudaro redukuota̧ja̧ likiniu̧ sistema̧ mod m. Pastebėsime, kad s = φ (m) .

Lema. Tegu r_{1}, r_{2}, ..., r_{s}− redukuotoji likiniu̧ sistema mod m ir skaičius a yra tarpusavyje pirminis m : (a, m) = 1. Tada skaičiu̧ sistema ar_{1}, ar_{2}, ..., ar_{s} irgi yra redukuotoji likiniu̧ sistema mod m.

I̧rodymas. Skaičiai r_{1}, r_{2}, ..., r_{s} yra redukuotoji likiniu̧ sistema mod m, todėl (r_{i}, m) = 1 su visais i = 0, 1, 2, ..., s Tada ir (ar_{i}, m) = 1 su visais i = 0, 1, 2, ..., s ir todėl jie visi yra primityviose klasėse. Parodysime, kad skaičiai sekoje ar_{0}, ar_{1}, ..., ar_{s} yra tarpusavyje skirtingi mod m ir todėl jie visi yra skirtingose primityviose klasėse Sakykime, kad ar_{i} ≡ ar_{j} (mod m) . Tada ar_{i} − ar_{j} = a (r_{i} − r_{j}) dalijasi iš m. Bet (a, m) = 1, todėl r_{i} − r_{j} dalijasi iš m ir r_{i} ≡ r_{j} (mod m) , taigi i = j. Gavome, kad skaičiai sekoje ar_{0}, ar_{1}, ..., ar_{s} yra skirtingose primityviose klasėse. Ir skaičiu̧ sekoje ir primityviu̧ju̧ klasiu̧ yra po lygiai (po s = φ (m)). Taigi ar_{0}, ar_{1}, ..., ar_{s} yra redukuotoji likiniu̧ sistema mod m.

I̧rodyta.

Išvada. Tegu r_{1}, r_{2}, ..., r_{s}− redukuotoji likiniu̧ sistema mod m ir skaičius a yra tarpusavyje pirminis m : (a, m) = 1. Tada

ar_{0} · ar_{1} ⋯ ar_{s} ≡ r_{0} · r_{1} ⋯ r_{s} (mod m) .

I̧rodymas. Turime

ar_{0} · ar_{1} ⋯ ar_{s} ≡ r_{0} · r_{1} ⋯ r_{s} (mod m) ⇔
K_{ar_{0}} · K_{ar_{1}} ⋯ K_{ar_{s}} = K_{r_{0}} · K_{r_{1}} ⋯ K_{r_{s}}.

Paskutinioji lygybė teisinga, nes tiek kairėje, tiek dešinėje jos pusėje yra visu̧ skirtingu̧ primityviu̧ju̧ klasiu̧ sandaugos.

I̧rodyta.

Oilerio teorema. Jeigu (a, m) = 1, tai a^{φ(m)} ≡ 1 (mod m) .

I̧rodymas. Tegu r_{1}, r_{2}, ..., r_{s}− redukuotoji likiniu̧ sistema mod m. Tada (r_{i}, m) = 1 su visais i = 0, 1, 2, ..., s ir todėl skaičius r_{1} · r_{2} ⋯ r_{s} irgi yra tarpusavyje pirminis m : (r_{1} · r_{2} ⋯ r_{s}, m) = 1.

Turime

ar_{0} · ar_{1} ⋯ ar_{s} ≡ r_{0} · r_{1} ⋯ r_{s} (mod m) ⇔
a^{s}r_{0} · r_{1} ⋯ r_{s} ≡ r_{0} · r_{1} ⋯ r_{s} (mod m) , (a, m) = 1 ⇔
a^{s} ≡ 1 (mod m) ,

čia s = φ (m) .

I̧rodyta.

Išvada. Jeigu (a, m) = 1, tai ā^{−1} ≡ ā^{φ(m)−1} (mod m) .

Mažoji Ferma teorema. Jeigu p− pirminis skaičius, o a nesidalija iš p, tai a^{p−1} ≡ 1 (mod m) .

I̧rodymas. Tai atskiras Oilerio teoremos atvejis, kai m = p− pirminis, nes φ (p) = p − 1.

I̧rodyta.

Išvada. Jeigu a nesidalija iš pirminio skaičiaus p, tai ā^{−1} = ā^{p−2} (mod p) .

Teiginys. Tegu m = p_{1} · p_{2} ⋯ p_{r} yra natūralusis skaičius, čia p_{1}, p_{2}, ..., p_{r} - skirtingi pirminiai skaičiai. Tada visiems ā ∈ Z_{m} teisinga lygybė

ā^{φ(m)+1} = ā.

I̧rodymas. Mūsu̧ nagrinėjamu atveju

φ (m) = (p_{1} − 1) (p_{2} − 1) ⋯ (p_{r} − 1) .

Tegu ā ∈ Z_{m}. Pirminiam skaičiui p_{i}, 1≤ i ≤ r, galimi du variantai:

a) (a, p_{i}) = 1. Tada pagal Maža̧ja̧ Ferma teorema̧ turime a^{p_{i}−1} ≡ 1 (mod m) ir

a^{φ(m)} = (a^{p_{i}−1})^{\frac{φ(m)}{p_{i}−1}} ≡ 1 (mod p_{i}) ,
a^{φ(m)+1} ≡ a (mod p_{i}) .

b) (a, p_{i}) > 1. Tada a dalijasi iš p_{i}, t.y. a ≡ 0 (mod m) ir todėl

a^{φ(m)+1} ≡ 0 ≡ a (mod m) .

Taigi turime, kad skaičius a^{φ(m)+1} − a dalijasi iš visu̧ pirminiu̧ p_{i},kartu ir iš šiu̧ pirminiu̧ skaičiu̧ sandaugos m :

a^{φ(m)+1} ≡ a (mod m)
ā^{φ(m)+1} = ā.

I̧rodyta.

Pateiksime dabar klasikini̧ pirminio skaičiaus testa̧.

Vilsono teorema. Skaičius p yra pirminis tada ir tik tada, kada (p − 1)! ≡ −1 (mod p) .

I̧rodymas. Tegu p− pirminis skaičius. Nagrinėkime baigtini̧ kūna̧ Z_{p}. Šiame kūne visos nenulinės likiniu̧ klasės turi atvirkštines:

K_{1}^{−1} = K_{ψ(1)}, ..., K_{p−1}^{−1} = K_{ψ(p−1)},

čia ψ− bijekcija aibėje {1, 2, ..., p − 1} . Klasiu̧ aibėje K_{ψ(1)}, ..., K_{ψ(p−1)} yra visos nenulinės Z_{p} klasės. Turime, kad

skaičiu̧ aibė 1, 2, ..., p−1 susiskaido poromis {1, ψ (1)} , ..., {p − 1, ψ (p − 1)} . Raskime poras, kuriose i = ψ (i) , t.y. K_{i}^{−1} = K_{i} ir 1 ≤ i < p. Tada

K_{i}^{2} = K_{1}
⇔ i^{2} = 1 (mod p)
⇔ (i − 1) (i + 1) ≡ 0 (mod p)

⇔ (i − 1) (i + 1) dalijasi iš pirminio p ⇔ arba i − 1 dalijasi iš p, arba i + 1 dalijasi iš p.

Pirmuoju atveju i − 1 = 0 ir i = 1, antruoju atveju i + 1 = p ir i = p − 1. Tada turime

K_{1} · K_{2} ⋯ K_{p−1} = K_{1} · (K_{2} · K_{ψ(2)}) ⋯ K_{p−1} = K_{1} · K_{p−1} = K_{p−1} = K_{−1} (p − 1)! ≡ −1 (mod p) .

Tegu dabar p− sudėtinis skaičius: p = a·b, čia 1 < a, b < p ir todėl (p − 1)!⋮a, b. Taigi (p − 1)! ≡ 0 (mod p) .

I̧rodyta.

Naudodamiesi Vilsono teorema galima sukonstruoti funkcija̧

f (m) = sin (\frac{π · ((m − 1)! + 1)}{m}) = [ \begin{matrix}0, jeigu m − pirminis \\ ≠ 0, jeigu m − sudėtinis \end{matrix} .

Tai savotiškas pirminio skaičiaus testas, tiesa praktiškai netaikomas, nes tenka skaičiuoti (m − 1)!, o tai labai didelis skaičius net esant pakankamai mažiems m.

Baigsime ši̧ skyriu̧ lyginiu̧ sistemu̧ sprendimu.

Teorema( kinu̧ teorema liekanoms). Tegu m_{1}, m_{2}, ..., m_{k} yra poromis tarpusavyje pirminiai skaičiai > 1 , t.y. (m_{i}, m_{j}) = 1, kai i ≠ j, ir tegu M = m_{1} · m_{2} ⋯ m_{k}. Tada

(1) lyginiu̧ sistema \{ \begin{matrix}x ≡ a_{1} (mod m_{1}) \\ x ≡ a_{2} (mod m_{2}) \\ ⋯ \\ x ≡ a_{k} (mod m_{k}) \end{matrix} turi sprendini̧ x = x_{0};

(2) jeigu x = x_{2} yra kitas sistemos sprendinys, tai x_{2} ≡ x_{0} (mod M) .

Teoremos i̧rodymas remiasi tokiomis lemomis.

Lema 1. Tegu a ≡ b (mod m_{i}) , čia m_{1}, m_{2}, ..., m_{n}− poromis tarpusavyje pirminiai skaičiai. Tada a ≡ b (mod m_{1}m_{2} ⋯ m_{n}) .

I̧rodymas. Tegu a ≡ b (mod m_{1}) ir a ≡ b (mod m_{2}) ,čia (m_{1}, m_{2}) = 1, t.y. xm_{1} + ym_{2} = 1 ir

\underbrace{\underbrace{(a − b)}_{⋮ m_{2}} xm_{1}}_{⋮ m_{1}m_{2}} + \underbrace{\underbrace{(a − b)}_{⋮ m_{1}} ym_{2}}_{⋮ m_{1}m_{2}}= a − b

Taigi a − b dalijasi iš m_{1}m_{2}. Lemoje esantis teiginys i̧rodomas indukcija pagal n. I̧rodyta.

Lema 2. Jeigu a ≡ b (mod m) ir m dalijasi iš d, tai ir a ≡ b (mod d) .

I̧rodymas akivaizdus (aš tikuosi).

Teoremos i̧rodymas. Apibrėžkime skaičius M_{i} ir N_{i} iš šiu̧ sa̧lygu̧:

M_{i} = \frac{M}{m_{i}} ,

M_{i}N_{i} ≡ 1 (mod m_{i}) , i = 1, 2, ..., k.

Tai galima padaryti, nes (M_{i}, m_{i}) = 1. Tegu dabar

x_{0} = M_{1}N_{1}a_{1} + ⋯ + M_{k}N_{k}a_{k}.

Tada

x_{0} = M_{1}N_{1}a_{1} + ⋯ + M_{k}N_{k}a_{k} ≡ M_{i}N_{i}a_{i} ≡ a_{i} (mod m_{i}) ,

t.y. x_{0} yra sistemos sprendinys,ir todėl sistema

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

ekvivalenti sistemai

\{ \begin{matrix}x ≡ x_{0} (mod m_{1}) \\ x ≡ x_{0} (mod m_{2}) \\ ⋯ \\ x ≡ x_{0} (mod m_{k}) \end{matrix} .

Remiantis Lema 1 ir Lema 2 paskutinioji sistema yra ekvivalenti lyginiui

x = x_{0} (mod m_{1}m_{2} ⋯ m_{k}) .

I̧rodyta.