Algebros paskaitos informatikams. Rimantas Grigutis.

1 Paskaita.

Matematinės indukcijos metodas. Dalumo su liekana teorema. Didžiausias bendras daliklis.Euklido algoritmas. Tarpusavyje pirminiai skaičiai. Pirminiai skaičiai. Pagrindinė aritmetikos teorema.

Matematinės indukcijos metodas.

Tai vienas dažnai naudojamas būdas teiginiams i̧rodinėti. Nagrinėkime sveiku̧ju̧ skaičiu̧ aibȩ Z ir tvarkos sa̧ryši̧ ≤ šioje aibėje. . Sakysime, kad a ≤ b , jei b−a ≥ 0. Šis dvieju̧ sveiku̧ju̧ skaičiu̧ sa̧ryšis pasižymi

savybėmis:

i) a ≤ a (refleksyvumas ) ; ii) ( a ≤ b) ∧ (b ≤ a) ⟹ a = b (nesimetriškumas) ; iii) (a ≤ b) ∧ (b ≤ c) ⟹ (a ≤ c) (tranzytivumas ) . Tuo atveju, kai a ≤ b ir a ≠ b rašome a < b. Aišku, kad bet kuriai sveiku̧ju̧ skaičiu̧ porai a ir b teisinga arba (a ≤ b), arba

(b ≤ c). Todėl sveiku̧ju̧ skaičiu̧ aibȩ Z vadina tiesiškai sutvarkyta aibe. Su šia tvarka surišti tam tikri principai. Išvardinkime kai kuriuos iš ju̧.

Visiško sutvarkymo principas(well-ordering Principle) sveikiesiems skaičiams. Tegu a- sveikasis skaičius. Bet kuris netuščias sveiku̧ju̧ skaičiu̧ ≥ a (≤ a) poaibis turi mažiausia̧(didžiausia̧) elementa̧.

Visiško sutvarkymo principas(well-ordering Principle) natūraliesiems skaičiams. Bet kuris netuščias natūraliu̧ju̧ skaičiu̧ poaibis turi mažiausia̧ elementa̧.

Natūraliuosius skaičius apibrėžia G.Peano(1858-1932) aksiomu̧ sistema. Iš šios sistemos išplaukia taip pat ir

Matematinės indukcijos principas: tegu su kiekvienu n∈ N turime teigini̧ T (n). Sakykime, kad žinome būda̧ teiginio T (l) , ∀l, teisingumui nustatyti, jeigu teisingi teiginiai T (k) su visais k<l ( tame tarpe teisingas T(1) teiginys).Tada teisingas ir teiginys T (n)su visais n ∈ N.

I̧rodymas.I̧rodysime prieštaros metodu. Nagrinėkime aibȩ S = {s|s ∈ N, teiginys T (s) neteisingas} ⊆ N. Tegu S ≠ ∅. Tada egzituoja mažiausias aibės S elementas s_{0}., t.y. teiginys

T (s_{0}) neteisingas. Jeigu s_{0} = 1, tai prieštarauja indukcijos bazei, o jeigu s_{0} > 1, tai visi teiginiai T (s), s < s_{0} , yra teisingi ir todėl žinome būda̧ teiginio T (s_{0}) teisingumui nustatyti.

Prieštaravimas i̧rodo matematinės indukcijos metoda̧. I̧rodyta.

Dalumo su liekana teorema.

Apibrėžimas. Tegu a ir b yra sveikieji skaičiai. Sakysime, kad a dalijasi iš b (be liekanos), jeigu egzistiuoja toks sveikasis skaičius c, kad a = b · c. Sakome,

kad skaičius b yra a daliklis. Žymėsime a⋮b.

Išvados. 1. Tegu a, b, c ∈ Z ir a⋮c, b⋮c. Tada (a ± b) ⋮c.

2.Tegu a, b, c ∈ Z ir a⋮c. Tada ab⋮c. 3.Tegu a ∈ Z, a ≠ 0. Tada 0⋮a. 4.Tegu a ∈ Z. Tada a⋮1. 5.Tegu a ∈ Z, 1⋮a. Tada a = ±1.

Visiško sutvarkymo principas. Tegu k_{0}− sveikasis skaičius. Bet kuris netuščias sveiku̧ju̧ skaičiu̧ ne mažesniu̧ už k_{0} ( ≥ k_{0}) poaibis turi mažiausia̧ elementa̧. Bet kuris netuščias sveiku̧ju̧ skaičiu̧ ne didesniu̧ už k_{0} ( ≤ k_{0}) poaibis turi didžiausia̧ elementa̧.

Teorema(dalybos su liekana teorema). Tegu a ir b− sveikieji skaičiai ir b ≠ 0. Tada egzistuoja vienintėliai sveikieji skaičiai q ir r su kuriais teisinga lygybė a = bq + r, čia 0 ≤ r < |b| .

I̧rodymas. Nagrinėkime sveiku̧ju̧ skaičiu̧ seka̧{a − k · b|k ∈ Z} :

…, a − 2b, a − b, a, a + b, a + 2b, ... .

Šioje sekoje yra tiek teigiami ,tiek neigiami skaičiai. Pagal Visiško sutvarkymo principa̧ neneigiamu̧ ( kai k_{0} = 0) sekos nariu̧ posekyje galima rasti mažiausia̧ skaičiu̧ r = a − qb ≥ 0. Tada

a = bq + r ir 0 ≤ r < |b| .

Parodysime, kad taip parinktas r yra vienintėtis. Tegu turime

a = bq_{1} + r_{1} ir 0 ≤ r < |b|

ir tegu r ≠ r_{1}, beto r_{1} < r. Tada yra teisinga 0 < r − r_{1} < |b| ir galioja lygybė

r − r_{1} = (q_{1} − q) b ,

t.y. r − r_{1} dalijasi iš b, o tai prieštarauja tam, kad 0 < r − r_{1} < |b| . I̧rodyta.

Apibrėžimas.Tegu a, b ∈ Z. Sveikasis skaičius d > 0 vadinamas skaičiu̧ a ir b didžiausiu bendru dalikliu, jeigu

1. a⋮d, b⋮d.

2. Jeigu a⋮c.b⋮c, tai d⋮c.

Didžiausio bendro daliklio žymuo: d = BDD(a, b) = (a, b) .

Pastaba. (0, 0) = 0.

Teorema. Su visais a, b ∈ Z, a ≠ 0, b ≠ 0 egzistuoja tokie sveikieji skaičiai x_{0} ir y_{0}, kad (a, b) = ax_{0} + by_{0}.

I̧rodymas.Nagrinėkime sveiku̧ju̧ skaičiu̧ aibȩ M = {ax + by|x, y ∈ Z} . Ši aibė yra netuščia, nes a, b ∈ M. Aibėje M yra tiek teigiami, tiek neigiami skaičiai. Pagal Visiško sutvarkymo principa̧ teigiamu̧ ( kai k_{0} = 1) aibės M poaibyje galima rasti mažiausia̧ skaičiu̧ 0 ≠ d = ax_{0} + by_{0}. Parodysime, kad skaičius d ir yra didžiausias bendras a ir b daliklis: d = (a, b) . Parašykime skaičiu̧ porai a ir d dalybos su liekana lygybȩ:

a = dq + r, 0 ≤ r < d.

Tada

0 ≤ r = a − dq = a − (ax_{0} + by_{0}) q = (1 − x_{0}q) a + (−y_{0}q) b ∈ M.

Bet d yra mažiausias \underline{teigiamas} skaičius iš M, todėl r = 0, t.y. a⋮d. Panašiai

galima parodyti, kad ir b⋮d.

Tegu dabar yra toks sveikas c, kad a⋮c ir b⋮c. Tada

d =\underbrace{\underbrace{a · x_{0}}_{dalijasi iš c} + \underbrace{b · y_{0}}_{dalijasi iš c}}_{dalijasi iš c} .

Pagal apibrėžima̧ d = (a, b) . I̧rodyta.

Nevienintėlis reiškimas: 6 = (12, −30) = 12 · 3 + (−30) · 1 = 12 · (−2) + (−30) · (−1) .

Euklido algoritmas BDD skaičiavimui. Turime skaičius a ir b, b ≠ 0. Rašysime dalybos su liekana teorema̧:

Tegu a_{0} = a ir a_{1} = b. Tada

a_{0} = a_{1}q_{1} + a_{2}  0 < a_{2} < |a_{1}|
a_{1} = a_{2}q_{2} + a_{3}  0 < a_{3} < a_{2}
⋯  ⋯
a_{k−2} = a_{k−1}q_{k−1} + a_{k} 0 < a_{k} < a_{k−1}
a_{k−1} = a_{k}q_{k}

Sveikieji skaičiai sudaro mažėjančia̧ seka̧ |a_{1}| > a_{2} > a_{3} > ⋯ > a_{k−1} > a_{k} > 0. Tada (a, b) = a_{k}.

Apibrėžimas. Du skaičiai a, b ∈ Z vadinami tarpusavyje pirminiais, jeigu (a, b) = 1.

Teorema. Skaičiai a, b ∈ Z yra tarpusavyje pirminiai tada ir tik tada, kada egzistuoja tokie x, y ∈ Z, kad ax + by = 1.

I̧rodymas. Teiginys iš kairės i̧ dešinȩ yra teisingas pagal apibrėžima̧. Tegu dabar ax + by = 1 ir (a, b) = d. Tada

1 =\underbrace{\underbrace{a · x}_{dalijasi iš d} + \underbrace{b · y}_{dalijasi iš d}}_{dalijasi iš d},

t,y. 1 dalijasi iš d ir todėl d = 1. I̧rodyta.

Teiginys(tarpusavyje pirminiu̧ skaičiu̧ savybė). Tegu a_{1}, ..., a_{m} ir b_{1}, ..., b_{n} yra dvi tokios sveiku̧ju̧ skaičiu̧ sekos, kad (a_{i}, b_{j}) = 1 su visais 1 ≤ i ≤ m, 1 ≤ j ≤ n. Tada (a_{1} ⋯ a_{m}, b_{1} ⋯ b_{n}) = 1.

Be i̧rodymo.

Išvados. 1.Jeigu \frac{a}{b} yra nesuprastinama trupmena , tai ir trupmena \frac{a^{n}}{b^{n}} yra nesuprastinama su visais natūraliaisiais n.

2. Tegu c ∈ Z ir n > 1. Tada ^{n} \sqrt{c} yra arba sveikasis skaičius, arba iracionalusis skaičius.

Apibrėžimas. Skaičius n ∈ N, n > 1 vadinamas pirminiu skaičiumi, jeigu jis turi tik šiuos daliklius: ±1, ±n .

Teiginys. Bet kuris sveikasis skaičius, nelygus ±1, dalijasi iš kurio nors pirminio skaičiaus.

Teorema( Euklidas). Yra be galo daug pirminiu̧ skaičiu̧.

I̧rodymas. I̧rodysime prieštaros būdu. Sakykime, egzistuoja baigtinis pirminiu̧ skaičiu̧ kiekis: p_{1}, p_{2}, ..., p_{m}. Skaičius n = p_{1}p_{2} ⋯ p_{m} + 1 dalijasi iš pirminio, taigi egzistuoja toks i, 1 ≤ i ≤ m, kad n⋮p_{i}. Tada

1 =\underbrace{\underbrace{n}_{dalijasi iš p_{i}} − \underbrace{p_{1}p_{2} ⋯ p_{m}}_{dalijasi iš p_{i}}}_{dalijasi iš p_{i}} ,

t.y. 1⋮p_{i}, o tai prieštarauja pirminio skaičiaus apibrėžimui( p_{i} > 1). I̧rodyta.

Pastaba. Pastebėsime, kad pirmieji pavidalo p_{1}p_{2} ⋯ p_{m} + 1 skaičiai yra pirminiai: 2+1 = 3, 2·3 +1 = 7, 2·3·5+1 = 31, 2·3·5·7+1 = 211, 2·3·5·7·11+1 = 2311. Tačiau skaiċius 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509 yra sudėtinis.

Teiginys( pirminiu̧ skaičiu̧ savybė). Tegu a_{1}, ..., a_{m} yra tokia sveiku̧ju̧ skaičiu̧ seka, kad skaičius a_{1} ⋯ a_{m} dalijasi iš pirminio p. Tada egzistuoja toks j, 1 ≤ j ≤ m, kad a_{j} dalijasi iš p.

Be i̧rodymo.

Pagrindinė aritmetikos teorema. Su kiekvienu natūraliuoju n > 1 egzistuoja tokie pirminiai p_{1}, p_{2}, ..., p_{s} (tarp ju̧ gali būti sutampančiu̧), kad n = p_{1} · p_{2} · ⋯ p_{s}.

Be i̧rodymo.