51

New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

ARVUTEOORIA

Kevad 2002

Loengukonspekt

Lektor: Valdis Laan

1

Page 2: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Sisukord

1. Jaguvus. Aritmeetika p~ohiteoreem 3

2. Algarvud 8

3. Kongruentsi m~oiste ja lihtsamad omadused 12

4. J�a�agiklassiringid 14

5. Arvuteoreetilisi funktsioone 16

6. Tundmatut sisaldavad kongruentsid. Hiina j�a�agiteoreem. 20

6.1. �Ulesande p�ustitusest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6.2. Lineaarkongruentsid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6.3. Hiina j�a�agiteoreem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6.4. Kongruentsid algarvu astme j�argi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.5. Kongruentsid suvalise mooduli j�argi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

7. Algjuured 26

8. L~oplikud korpused 30

8.1. L~oplike korpuste ehitus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

8.2. Aritmeetika l~oplikes korpustes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

8.3. Juurimine l~oplikes korpustes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

9. Ruutj�a�agid 37

10. Arvuvallad 43

10.1. Naturaalarvudelt t�aisarvudele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

10.2. T�aisarvudelt ratsionaalarvudele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

10.3. Ratsionaalarvudelt reaalarvudele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.3.1. Weierstrassi meetod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.3.2. Dedekindi meetod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.3.3. Cantori meetod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

10.3.4. p-aadilised arvud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

10.4. Reaalarvude valla laiendamine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2

Page 3: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

1. Jaguvus. Aritmeetika p~ohiteoreem

V�aga oluline koht arvuteoorias on jaguvuse m~oistel. Sellega olete te t~oen�aoliselt juba kokku puutunud kursuses

Algebra I v~oi Algebra II. Meenutame siiski olulisemaid de�nitsioone (vt. ka [1], lk. 191{198).

Olgu (R;+; �) nullitegureita kommutatiivne ring. (K�aesolevas kursuses peame ringi all silmas �uhikelemendiga

assotsiatiivset ringi.) Sellisel juhul v~oib k~onelda selle ringi elementide jaguvusest. Nimelt, �oeldakse, et element

a 2 R jagab elementi b 2 R (ja t�ahistatakse a j b), kui leidub selline element c 2 R, et ac = b. Fakti, et a j b, v~oibt�ahistada ja v�aljendada v�aga mitmel erineval moel. K~oik j�argnevad kirjutised ja v�aited t�ahendavad tegelikult �uhte

ja sedasama:

a j b � element a jagab elemeti b � b...a � element b jagub elemendiga a

� a on b jagaja � a on b tegur � b on a kordne � (9c)(ac = b):

Jaguvuse de�nitsioonist j�areldub vahetult, et element on p�o�oratav ringis R parajasti siis, kui ta jagab selle ringi

�uhikelementi. Ringi R p�o�oratavad elemendid moodustavad korrutamise suhtes r�uhma, mida t�ahistatakse U (R)

ja mille elemente nimetatakse vahel ka �uhikuiks (ingl. k. unit). Seega U (R) = fa 2 R j (9c 2 R)(ac = 1)g.Mittep�o�oratavat elementi p 2 R nimetatakse taandumatuks, kui iga a; b 2 R korral v~ordusest p = ab j�areldub, et

kas a on p�o�oratav v~oi b on p�o�oratav. �Oeldakse, et elemendid a; b 2 R on assotsieeritud (t�ahistatakse a � b), kui

a = bu; kus u 2 R on p�o�oratav. Saab t~oestada, et a ja b on assotsieeritud parajasti siis, kui a j b ja b j a (vt. [1],

Lemma 6.12.2.).

N�aide 1.1. T�aisarvude ringis Zon p�o�oratavad elemendid vaid 1 ja �1, s.t. U (Z) = f1;�1g. Igal arvul a 62 U (Z)

on v�ahemalt 4 jagajat: 1;�1; a;�a. N�aiteks arvu 6 jagajad on �1;�2;�3 ja �6. Arvud a ja b on assotsieeritud,

kui a = �b ning ringi Ztaandumatud elemendid on algarvud ja nende vastandarvud.

Meenutame m~oningaid jaguvusseose omadusi.

Lause 1.2. Jaguvusseosel nullitegureita kommutatiivses ringis R on j�argmised omadused: iga a; b; c 2 R korral

1. kui a j b ja b j c, siis a j c (transitiivsus);

2. kui a j b ja a j c, siis a j (b� c);

3. kui a j b, siis ac j bc (j�arelikult ka a j bc).

Nullitegureita kommutatiivses ringis R v~oib k~onelda elementide suurimast �uhistegurist ja v�ahimast �uhiskordsest.

De�nitsioon 1.3. Elementi d 2 R nimetatakse elementide a; b 2 R suurimaks �uhisteguriks (t�ahistatakse d =

S�UT(a; b) ehk l�uhidalt d = (a; b)), kui

(i) d j a ja d j b;

(ii) iga c 2 R korral, kui c j a ja c j b, siis c j d.

De�nitsioon 1.4. Elementi m 2 R nimetatakse elementide a; b 2 R v�ahimaks �uhiskordseks (t�ahistatakse m =

V�UK(a; b) ehk m = [a; b]), kui

(i) a j m ja b j m;

(ii) iga c 2 R korral, kui a j c ja b j c, siis m j c.

Lihtne on veenduda, et kui d on a ja b suurim �uhistegur (v�ahim �uhiskordne) ja u 2 U (R), siis ka du on a

ja b suurim �uhistegur (v�ahim �uhiskordne). Teiste s~onadega, suurim �uhistegur ja v�ahim �uhiskordne on m�a�aratud

�uheselt assotsieerituse t�apsusega (t�aisarvude korral t�ahendab see siis m�argi t�apsust). Muuhulgas t�ahendab see

seda, et mistahes suurimat �uhistegurit v~oi v�ahimat �uhiskordset sisaldavate avaldiste v~ordust tuleb t~olgendada

assotsieerituse t�apsusega.

Suurimal �uhisteguril on j�argmised omadused.

Lause 1.5. Iga a; b; c 2 R korral

1. (a; b) = a parajasti siis, kui a j b;

2. (a; 0) = a;

3. (a; b) = 0 parajasti siis, kui a = 0 ja b = 0;

3

Page 4: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

4. (ca; cb) = c(a; b);

5. ((a; b); c) = (a; (b; c)).

On ringe, mille kahe elemendi S�UT ja V�UK ei eksisteeri. T�aisarvude korral on siiski igal kahel arvul olemas

t�apselt kaks suurimat �uhistegurit ja v�ahimat �uhiskordset (v.a. juhul, kui m~olemad arvud on v~ordsed nulliga).

J�argmine lause on lugejale kindlasti tuttav. L�uhidalt �oeldes v�aidab ta seda, et iga t�aisarvu v~oib j�a�agiga jagada

iga naturaalarvuga. M�argime, et selle kursuse jooksul me loeme naturaalarvudeks arve 1; 2; 3; : : : (kuid mitte 0).

Lause 1.6. Olgu a t�aisarv ja b naturaalarv. Siis leiduvad �uheselt m�a�aratud t�aisarvud q (jagatis) ja r (j�a�ak), nii et

a = bq + r ja 0 � r < b:

T~oestus. Selliste q ja r leidumine on t~oestatud raamatus [1], lauses 6.1.21. N�aitame, et nad on �uheselt m�a�aratud.

Selleks oletame, et leiduvad t�aisarvud q1; q2; r1; r2 nii, et

a = bq1 + r1 = bq2 + r2 ja 0 � r1; r2 < b:

Siis b(q1 � q2) = r2 � r1. Kuna b 6= 0; jr2 � r1j < b ja q1 � q2 2Z; siis v~ordusest jr2 � r1j = jbjjq1� q2j j�areldub, etq1 � q2 = 0 ja seega ka r2 � r1 = 0. See t�ahendab, et q1 = q2 ja r1 = r2. 2

Seega naturaalarv b jagab t�aisarvu a (ehk a jagub arvuga b) parajasti siis, kui arvu a jagamisel arvuga b tekkiv

j�a�ak on 0.

Lausest 1.6 j�areldub muuhulgas, et ring Zon nn. Eukleidese ring ja seega (nagu teada kursusest Algebra I v~oi

Algebra II), v~oib selles ringis kahe elemendi suurima �uhisteguri leida Eukleidese algoritmi abil.Algoritm ise t�o�otab j�argmiselt. Olgu eesm�argiks leida t�aisarvude a ja b suurim �uhistegur. �Uldsust kitsendamata

v~oime eeldada, et a � b > 0 (sest (a; b) = (jaj; jbj)). K~oigep�a�alt jagame arvu a j�a�agiga arvuga b:

a = bq1 + r1; 0 � r1 < b:

Kui r1 = 0, siis b j a ja seega (a; b) = b. Kui r1 6= 0, siis jagame arvu b arvuga r1:

b = r1q2 + r2; 0 � r2 < r1:

Kui r2 = 0, siis l~opetame; vastasel juhul jagame arvu r1 arvuga r2:

r1 = r2q3 + r3; 0 � r3 < r2:

Niimoodi j�atkame senikaua kui saame mingil sammul j�a�agiks rn+1 = 0. Varem v~oi hiljem peab see juhtuma, sest

b > r1 > r2 > : : : � 0 ja ei leidu l~opmatuid kahanevaid naturaalarvujadasid. Osutub, et suurimaks �uhisteguriks on

viimane nullist erinev j�a�ak rn (t~oestuse v~oib leida raamatust [1], lk. 196{197). Algoritmi v~oib kokku v~otta j�argmise

tabelina.

Eukleidese algoritm.

a = bq1 + r1; 0 < r1 < b;

b = r1q2 + r2; 0 < r2 < r1;

r1 = r2q3 + r3; 0 < r3 < r2;

� � �rn�3 = rn�2qn�1 + rn�1 0 < rn�1 < rn�2;

rn�2 = rn�1qn + rn 0 < rn < rn�1;

rn�1 = rnqn+1 + 0:

(1)

Paljudel arvuteooria probleemidel on j�argmine kuju: kui f on t�aisarvuliste kordajatega (�uhe- v~oi mitmemuu-

tuja) pol�unoom, siis kas v~orrandil f = 0 on t�aisarvulisi lahendeid? Selliseid v~orrandeid on hakatud Diophantose

auks nimetama diofantilisteks v~orranditeks. Diophantos elas 3. sajandil ja t�o�otas Aleksandrias. Tema p~ohiteos oli

\Aritmeetika" , milles ta muuhulgas k�asitles tehteid ratsionaalarvudega, kasutas algelist algebralist s�umboolikat ja

lahendas mitme tundmatuga v~orrandeid.

Teoreem 1.7. Antud t�aisarvude a; b; c korral on diofantilisel v~orrandil

ax+ by = c (2)

olemas t�aisarvuline lahend parajasti siis, kui (a; b) j c. Kui v�ahemalt �uks arvudest a ja b ei ole 0 ning x0; y0 on sellev~orrandi mingi (eri)lahend, siis k~oik �ulej�a�anud selle v~orrandi lahendid x; y saadakse valemite

x = x0 +b

(a; b)t; y = y0 �

a

(a; b)t

abil, andes muutujale t k~oik t�aisarvulised v�a�artused.

4

Page 5: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. T~oestame esimese v�aite.

Tarvilikkus. Oletame, et leiduvad sellised t�aisarvud x0 ja y0, et ax0 + by0 = c. Kuna (a; b) j a ja (a; b) j b, siislause 1.2(2) p~ohjal ka (a; b) j ax+ by = c.

Piisavus. See, et (a; b) j c, t�ahendab, et leidub selline s 2Z, et rns = c. Olgu (a; b) = rn leitud Eukleidese algoritmi

abil. Liikudes tabelis (1) alt �ules, saame rn avaldada a ja b kaudu:

rn = rn�2 � rn�1qn = rn�2 � (rn�3 � rn�2qn�1)qn = (1 + qnqn�1)rn�2 � qnrn�3 = : : : = ax0 + by0;

kus x0; y0 2Z. Seega a(x0s) + b(y0s) = (ax0 + by0)s = rns = c, s.t. x0s; y0s on v~orrandi (2) lahend.

Enne teise v�aite t~oestamist m�argime, et esimesest v�aitest saab teha j�areldused 1.10, 1.11 ja 1.12

Oletame n�u�ud, et meile on teada v~orrandi (2) mingi lahend x0; y0. Kui x0; y0 on selle v~orrandi mingi teine

lahend, siis ax0 + by0 = c = ax0 + by0, millest saame, et a(x0 � x0) = b(y0 � y0). Kui v�ahemalt �uks arvudest a ja b

ei ole 0, siis (a; b) 6= 0. T�ahistades d = (a; b), saame leida sellised t�aisarvud a0 ja b0, et a = da0 ja b = db0, kusjuures

j�arelduse 1.10 p~ohjal (a0; b0) =�ad; bd

�= 1. Asendades a ja b ning jagades v~orduse m~olemaid pooli arvuga d, saame

a0(x0 � x0) = b0(y0 � y0): (3)

Meil on olukord, kus a0 j b0(y0 � y0) ja (a0; b0) = 1. Kasutades j�areldust 1.11 saame, et a0 j (y0 � y0), s.t. leidub

selline t 2Z, et y0 � y0 = a0t. Asendades y0 � y0 v~orduses (3) ning jagades arvuga a0, saame x0 � x0 = b0t: Seega

oleme saanud, et lahend x0; y0 avaldub kujul x0 = x0 + b0t = x0 +b

(a;b)t , y0 = y0 � a0t = y0 � a

(a;b)t.

Teisest k�uljest, on lihtne n�aha, et iga t 2Zkorral sellised arvud rahuldavad v~orrandit (2):

a

�x0 +

b

(a; b)t

�+ b

�y0 �

a

(a; b)t

�= ax0 + by0 = c:

2

M�arkus 1.8. Kirjutame korraks v~orrandi (2) lahendeid paaridena hx; yi. Vaatleme v~orrandit ax + by = c �ule

reaalarvude ning eeldame, et v�ahemalt �uks arvudest a ja b ei ole 0. Siis lineaarv~orrandis�usteemide teooria p~ohjal

on teada, et sellest v~orrandist koosnevale s�usteemile vastava homogeense s�usteemi ax + by = 0 lahendite funda-

mentaals�usteem sisaldab �uhe lahendi hx1; y1i (selleks v~oib v~otta n�aiteks paari hx1; y1i =D

b(a;b)

;� a(a;b)

E2 R2)

ning s�usteemi ax + by = c k~oigi reaalarvuliste lahendite hulk avaldub kujul hx0; y0i + fthx1; y1i j t 2 Rg =

fhx0 + tx1; y0 + ty1i j t 2 Rg, kus hx0; y0i 2 R2 on selle v~orrandi mingi erilahend (vt. [1], teoreem 5.5.3). Teoreem

1.7 �utleb, et kui vaadelda v~orrandit ax + by = c �ule t�aisarvude, siis tema k~oigi lahendite hulk avaldub sisuliselt

samamoodi.

N�aide 1.9. Lahendame diofantilise v~orrandi

172x+ 20y = 1000:

Selleks leiame Eukleidese algoritmi abil (172; 20). Saame, et

172 = 8 � 20 + 12

20 = 1 � 12 + 8

12 = 1 � 8 + 4

8 = 2 � 4;

kust n�aeme, et (172; 20) = 4. Kuna 4 j 1000, siis v~orrandil on lahend olemas. Avaldame n�u�ud arvu 4 arvude 172 ja

20 \lineaarkombinatsioonina":

4 = 12� 8 = 12� (20� 12) = 2 � 12� 20 = 2 � (172� 8 � 20)� 20 = 2 � 172 + (�17) � 20:

Korrutades saadud seose m~olemaid pooli arvuga 250, saame 1000 = 500 � 172 + (�4250) � 20; seega x0 = 500; y0 =

�4250 on antud v~orrandi �uheks lahendiks. K~oik �ulej�a�anud t�aisarvulised lahendid saame arvutada valemeist

x = 500+ 204t = 500 + 5t;

y = �4250� 1724t = �4520� 43t;

kus t on t�aisarv.

Leiame veel n�aiteks k~oik positiivsed lahendid (s.t. lahendid, kus x > 0 ja y > 0). Positiivsete lahendite korral

peab t rahuldama v~orratusi 500+5t > 0 ja�4250�43t > 0, ehk samav�a�arselt�100 < t < �983643. Ainus t�aisarv, mis

neid tingimusi rahuldab, on t = �99. Seega antud v~orrandil on vaid �uks positiivne lahend x = 500+ 5 � (�99) = 5,

y = �4520� 43 � (�99) = 7.

5

Page 6: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

J�areldus 1.10. Iga a; b; d 2Z; d 6= 0; korral on v~ordus (a; b) = d samav�a�arne v~ordusega�ad; bd

�= 1.

T~oestus. N�aitame, et esimesest v~ordusest j�areldub teine. Et d on a ja b jagaja, siis adja b

don t�aisarvud. Teoreemi

1.7 esimese v�aite p~ohjal leiduvad sellised t�aisarvud x ja y, et ax + by = d. Jagades selle v~orduse pooli arvuga d

saame, et adx+ b

dy = 1, millest j�allegi teoreemi 1.7 p~ohjal saame, et

�ad; bd

�j 1 ehk

�ad; bd

�= 1.

Oletame n�u�ud, et kehtib�ad; bd

�= 1. Siis lause 1.5 osa 3. p~ohjal d = d

�ad; bd

�= (a; b). 2

J�areldus 1.11. Kui a j bc ja (a; b) = 1, a; b; c 2Z, siis a j c.

T~oestus. Kuna (a; b) = 1, siis leiduvad sellised t�aisarvud x ja y, et ax + by = 1. J�arelikult axc + byc = c. Et a

jagab selle v~orduse vasakut poolt, siis peab ta jagama ka paremat poolt, s.t. a j c. 2

Meenutame, et algarvuks nimetatakse naturaalarvu p > 1, mille ainsad naturaalarvulised jagajad on 1 ja p.

Naturaalarvu, mis on suurem kui 1 ja mis pole algarv, nimetatakse kordarvuks.

J�areldus 1.12. Kui p on algarv ja p j bc, b; c 2Z, siis kas p j b v~oi p j c.

T~oestus. Algarvu p ainsad t�aisarvulised jagajad on �1 ja �p. Seega (p; b) = p v~oi (p; b) = 1. Esimesel juhul p j b.Teisel juhul saame j�arelduse 1.11 p~ohjal, et p j c. 2

Induktsiooniga saab n�u�ud lihtsalt t~oestada j�argmise v�aite.

J�areldus 1.13. Kui p on algarv ja p j a1a2 : : : an; a1; a2; : : : ; an 2Z; siis leidub k 2 f1; 2; : : : ; ng, nii et p j ak.

Kuna algarvu ainsad naturaalarvulised jagajad on 1 ja see arv ise, siis saame j�argmise tulemuse.

J�areldus 1.14. Kui p; q1; q2; : : : ; qn on algarvud ja p j q1q2 : : : qn; siis leidub k 2 f1; 2; : : : ; ng, nii et p = qk.

N�aitena nende omaduste rakendamisest vaatleme j�argmist v�aidet, mille t~oestas juba Pythagoras (569{500

e.m.a.).

N�aide 1.15.p2 ei ole ratsionaalarv.

Oletame vastuv�aiteliselt, etp2 on ratsionaalarv, s.t.

p2 = b

a, kus a ja b on t�aisarvud ja (a; b) = 1. Ruutu v~ottes

saame b2 = 2a2 , seega a j b2. Kui a > 1, siis j�arelduse 1.11 p~ohjal peaks a j b ja j�arelikult (a; b) = a > 1, mis

pole v~oimalik. Seega a = 1 ja j�arelikult b2 = 2, mis on vastuolu, sest �uhegi t�aisarvu ruut pole 2. Saadud vastuolu

n�aitabki, etp2 ei saa olla ratsionaalarv.

J�argnevalt t~oestame v�aite, millele tugineb suur osa naturaalarvude aritmeetikas t~oestatavatest teoreemidest ja

mis p�arineb Eukleidese (u. 350 e.m.a.) \Elementide" IX raamatust.

Teoreem 1.16 (Aritmeetika p~ohiteoreem). Iga naturaalarv n > 1 esitub algarvude korrutisena ja see esituson �uhene tegurite j�arjekorra t�apsuseni.

T~oestus. N�aitame esiteks induktsiooniga, et iga naturaalarv n > 1 esitub algarvude korrutisena. Arvu n = 2 korral

on v�aide ilmne. Oletame, et n > 2 ja iga naturaalarv 1 < m < n esitub algarvude korrutisena. Naturaalarv n peab

olema kas algarv v~oi kordarv. Esimesel juhul pole midagi t~oestada. Kui aga n on kordarv, siis leidub naturaalarv

d j n, kusjuures 1 < d < n: Valime selliste naturaalarvude d hulgast v�alja v�ahima, olgu see p. Siis p on algarv.

T~oepoolest, kui leiduks naturaalarv c nii, et c j p ja 1 < c < p, siis seostest c j p ja p j n j�arelduks, et c j n; mis aga

on vastuolus arvu p valikuga. Seega n = pm; kus p on algarv ja 1 < m < n. Induktsiooni eelduse p~ohjal avaldub m

algarvude korrutisena ning j�arelikult ka n avaldub algarvude korrutisena.�Uhesuse n�aitamiseks oletame, et n esitub algarvude korrutisena kahel viisil:

n = p1p2 : : : pr = q1q2 : : : qs;

kus (�uldsust kitsendamata) r � s ja algarvud pi ja qj on mittekahanevas j�arjekorras, s.t. p1 � p2 � : : : � pr ja

q1 � q2 � : : : � qs. Kuna p1 j q1q2 : : : qs; siis j�arelduse 1.14 p~ohjal p1 = qk mingi k 2 f1; : : : ; sg korral; kuid siis

p1 � q1. Samamoodi saame q1 � p1 ning seega p1 = q1. Taandades p1 saame p2p3 : : : pr = q2q3 : : : qs. Korrates seda

m~ottek�aiku saame p2 = q2 ja p3p4 : : : pr = q3q4 : : : qs. Kui r < s; siis niimoodi j�atkates saame 1 = qr+1qr+2 : : : qs,

mis on aga v~oimatu, sest k~oik qi > 1. Seega r = s ning p1 = q1; p2 = q2; : : : ; pr = qr, mida oligi vaja n�aidata. 2

M�argime, et kuigi siin me andsime aritmeetika p~ohiteoreemi vahetuma t~oestuse, on see teoreem tegelikult

otseseks j�arelduseks teoreemile, mis v�aidab, et iga Eukleidese ring on faktoriaalne ([1], teoreem 6.13.4.).

Naturaalarvu esitust algarvude korrutisena nimetame tema algtegureiks lahutuseks ning selles lahutuses esinevaidalgarve nimetame antud arvu algtegureiks. S~oltuvalt tegurite j�arjekorrast v~oib algtegureiks lahutusi olla mitu. Vahel

on siiski otstarbekam kasutada arvu �uhesemat esitust.

6

Page 7: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

J�areldus 1.17. Iga naturaalarv n > 1 esitub �uheselt kujul

n = pk11 pk22 : : : pkss ; (4)

kus ki > 0, pi on algarv iga i = 1; 2; : : : ; s korral ning p1 < p2 < : : : < ps.

Naturaalarvu n esitust kujul (4) nimetame selle arvu standardkujuks.

N�aide 1.18. 180 = 2 � 5 � 2 � 3 � 3 = 2 � 2 � 3 � 3 � 5 = 22 � 32 � 51, kus viimane korrutis on arvu 180 standardkuju.

Aritmeetika p~ohiteoreem annab �uhe v~oimaluse S�UT ja V�UK arvutamiseks. Kui m;n > 1 on naturaalarvud

ja fp1; : : : ; psg on nende arvude algtegurite hulkade �uhend, siis v~oime need arvud esitada kujul m = pk11 : : : pkss ,

n = pl11 : : : plss , kus p1; : : : ; ps on paarikaupa erinevad algarvud ja ki � 0; li � 0, i = 1; : : : ; s. (NB! Tegemist pole

standardkujudega.)

Lause 1.19. Olgu m;n > 1 naturaalarvud, m = pk11 : : : pkss , n = pl11 : : : plss , kus p1; : : : ; ps on paarikaupa erinevadalgarvud ja ki � 0; li � 0, i = 1; : : : ; s. Siis

1. m j n parajasti siis, kui ki � li; i = 1; : : : ; s ;

2. (m;n) = pu11 : : : puss , kus ui = min(ki; li), i = 1; : : : ; s;

3. [m;n] = pv11 : : : pvss , kus vi = max(ki; li), i = 1; : : : ; s.

T~oestus. 1. Tarvilikkus. Olgu m j n. See t�ahendab, et leidub selline a 2 N, et ma = n. Kui a = 1, siis j�areldub

v�aide vahetult aritmeetika p~ohiteoreemist. Kui a > 1, siis t�anu aritmeetika p~ohiteoreemile ei saa a algtegurite

hulgas olla selliseid algarve, mis ei ole n algtegurid. Seega on a kujul a = pj11 : : : pjss , kus j1; : : : ; js � 0. J�arelikult

pk1+j11 : : : pks+jss =

�pk11 : : : pkss

��pj11 : : : pjss

�= ma = n = pl11 : : : plss :

Aritmeetika p~ohiteoreemi p~ohjal ki + ji = li, millest j�areldubki, et ki � li, i = 1; : : : ; s.

Piisavus. Olgu ki � li, i = 1; : : : ; s. Siis m�pl1�k11 : : : pls�kss

�= n, ehk m j n.

2. T�ahistame d = pu11 : : : puss . Kuna ui � ki ja ui � li, i = 1; : : : ; s, siis v�aite 1 p~ohjal d j m ja d j n. Oletame, et

c j m ja c j n, kusjuures c = pj11 : : : pjss . J�allegi

v�aite 1 p~ohjal ji � ki ning ji � li, i = 1; : : : ; s. Seega ji � min(ki; li) = ui, i = 1; : : : ; s, millest j�areldub, et

c j d.3. saab t~oestada analoogiliselt. 2

Kuna mistahes mittenegatiivsete t�aisarvude k ja l korral min(k; l)+max(k; l) = k+ l; siis kehtib j�argmine v�aide.

Lause 1.20. Mistahes naturaalarvude a ja b korral

(a; b) [a; b] = ab:

N�aide 1.21. Olgu m = 36 ja n = 27. Lahutame nad algarvude astmete korrutiseks: m = 22 � 32 ja n = 20 � 33.Kasutades lauset 1.19 saame, et (m;n) = 20 � 32 = 9 ja [m;n] = 22 � 33 = 108:

Tuleb m�arkida, et lause 1.19 omab t�ahtsust pigem teoreetilistes arutlustes, sest naturaalarvu algtegureiks la-

hutamine on reeglina vga tmahukas. Suurima �uhisteguri praktiliseks leidmiseks kasutatakse reeglina Eukleidese

algoritmi.

7

Page 8: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

2. Algarvud

Meenutame veelkord, et naturaalarvu p > 1 nimetatakse algarvuks, kui tema ainsad naturaalarvulised jagajad

on 1 ja p. Naturaalarvu, mis on suurem kui 1 ja mis pole algarv, nimetatakse kordarvuks.Kuidas antud naturaalarvu korral teha kindlaks, kas ta on algarv v~oi kordarv? K~oige lihtsam viis on jagada

seda arvu k~oigi talle eelnevate naturaalarvudega. Kui ta �uhegagi neist (v�alja arvatud 1) ei jagu, siis on ta algarv,

vastasel juhul kordarv. Kuigi see meetod on lihtne, ei k~olba ta praktikas kasutamiseks arvutuste liiga suure mahu

t~ottu.

Arvutuste mahtu saab veidi v�ahendada, kui paneme t�ahele j�argmist kordarvude omadust. Olgu a > 1 kordarv,

s.t. a = bc, kus 1 < b; c < a. Eeldades, et n�aiteks b � c, saame, et b2 � bc = a ja seega b �pa. Et b > 1, siis

leidub arvul b v�ahemalt �uks algtegur p. Siis p � b �pa, ning kuna p j b ja b j a, siis p j a. Seega, kui a on kordarv,

siis tal leidub selline algtegur, mis pole suurem kuipa. Ehk samav�a�arselt, kui �ukski algarv p �

pa ei ole arvu a

jagaja, siis a on algarv. Seega arvu a algarvulisuse kontrollimiseks piisab, kui kontrollime, kas ta jagub algarvudega

p �pa.

N�aide 2.1. Kas 101 on algarv?

Et 10 <p101 < 11, siis tuleb kontrollida jaguvust algarvudega 2, 3, 5 ja 7. Kuna 101 neist �uhegagi ei jagu, siis

on ta algarv.

Eespool n�agime, et kui �ukski algarv p �pa ei ole arvu a jagaja, siis a on algarv. Sellel faktil p~ohineb kreeka

matemaatiku Eratosthenese (276{194 e.m.a.) poolt v�alja t�o�otatud meetod mingist �kseeritud naturaalarvust n

mittesuuremate algarvude leidmiseks, mida nimetatakse \Eratosthenese s~oelaks". Allj�argnev kirjeldus on p�arit

Boethiuse (u. 480{524 m.a.j.) raamatust \Aritmeetika alustest".

\Nende arvude [algarvude] genereerimine ja leidmine on v~oetud uurimusest, mida Eratosthenes, muuhulgas,

nimetas \s~oelaks", sest kui k~oik paaritud arvud on pandud keskele kokku, siis kunsti abil, mida me tahame edasi

anda, s~oelutakse teiste hulgast v�alja iga arv, mis on kas esimest v~oi kolmandat liiki [s.t. on algarv]. Olgu k~oik

paaritud arvud alates kolmest paigutatud mistahes pikkusega j�arjestatud ritta: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21,

23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47. Nende arvude sellise jada korral peame vaatama, mis on esimene

arv, mida saab m~o~ota esimene arv reas. Siis ta j�argmisena m~o~odab arvu, mis on kahe arvu kaugusel esimesest ja

selleks, et m~o~ota arvu tolle m~o~odetud arvu j�arel, peab veel kaks arvu vahele j�atma ning samamoodi edasi, kui need

kaks arvu on vahele j�aetud, siis arv, mida j�alle kord m~o~odetakse, on m~o~odetud esimese arvu poolt; niimoodi iga

m~o~odetava arvu ja eelmise m~o~odetud arvu vahel on kaks ja nii j�atkatakse esimesest arvust l~opmatuseni.

Kuid las ma teen seda mitte �uldisel ja segasel moel. Esimene arv m~o~odab oma suurusega seda, mis paikneb

kahe arvu j�arel p�arast teda ennast. Nii kolm, j�attes kaks arvu vahele, see on 5 ja 7, m~o~odab �uheksat ja m~o~odab

teda iseenda suurusega, see on kolm korda. Kolm korda kolm m~o~odab �uheksat. Kui p�arast �uheksat j�atan vahele

kaks arvu, siis saan arvu, mis tuleb nende j�arel ja on m~o~odetud esimese paaritu arvu poolt teise paaritu arvu

suuruse abil, see on viie abil. Nii et kui p�arast 9-t me j�atame vahele 2 arvu, see on 11 ja 13, siis kolmandat arvu,

15, m~o~odetakse [jada] teise arvu suuruse abil, see on viie abil, kolm m~o~odab 15-t viis korda. J�alle, kui alustades

viieteistk�umnest ma j�atan vahel kaks arvu, mis on paigutatud jadas tema j�arele, siis esimene arv on tema [s.o. arvu

21] m~o~ot jada kolmanda paaritu arvu abil. Kui p�arast 15-t ma j�atan vahele 17 ja 19, siis ma j~ouan 21-ni, mis on

m~o~odetud arvu kolm poolt seitse korda. Arvust 21 on kolm seitsmendikosa, ja tehes seda l~opmatult, ma leian, et

jada esimene arv, kui jadas kaks arvu j�arjest vahel j�atta, suudab m~o~ota k~oiki j�argnevaid arve, ja seda j�arjest selle

jada paaritute arvude suuruste abil.

Kui arvu viis korral, mis asub jadas teisel kohal, tahaks keegi leida esimese ja j�argnevad arvud, millele 5 on

m~o~oduks, tuleks vahel j�atta 4 paaritut arvu p�arast 5-t, kuni tuleb see, mida 5 m~o~ota saab. Vahele j�aetakse 4

paaritut arvu, see on 7, 9, 11 ja 13. P�arast neid on 15, mida viis m~o~odab esimese paaritu arvu suurusega, see

on kolmega. 5 m~o~odab 15-t kolm korda. Kui seej�arel j�aetakse vahele neli arvu, siis seda, mis asetseb nende j�arel,

m~o~odab jada teine arv, see on 5, oma suurusega. Nii p�arast 15-t, kui arvud 17, 19, 21 ja 23 j�atad vahele, siis p�arast

neid leiame 25, mida viis m~o~odab iseenda suurusega. Viis korrutades viiega kasvab 25-ni. Kui p�arast seda j�aetakse

vahele j�argmised neli arvu, s�ailitades sellega sellesama jada konstantsuse, siis arvu, mis j�argneb, m~o~odab viis jada

kolmanda arvu, see on seitsme, suurusega; ja see protsess on l~opmatu.

Kui kolmas arv, millega saab m~o~ota, on v�alja otsitud, ja kuus kohta on vahele j�aetud, siis j~ouab j�arjestus

seitsmenda arvuni, seda saab m~o~ota esimese arvu, see on kolme, suurusega; ja p�arast seda arvu, kui kuus arvu

paned vahele, siis arvu, mille jada siis annab, saab m~o~ota viiega, jada teise arvuga, ja see m~o~odab 15-t kolm

korda. Kui siis j�aetaks vahele veel kuus vahep�a�alset arvu, siis arvu, mis j�argneb, seitsmendat arvu [21] saab m~o~ota

seitsmega kolme suuruse abil; ja see kindel kord j�atkub jada viimase arvuni."

Juba Eukleides leidis, et ei saa olla suurimat algarvu.

Teoreem 2.2 (Eukleides). Algarvude hulk on l~opmatu.

T~oestus. Olgu algarvud t�ahistatud p1 = 2; p2 = 3; p3 = 5, p4 = 7; : : : . Oletame vastuv�aiteliselt, et leidub suurim

algarv pn. Vaatleme naturaalarvu a = p1p2 : : : pn + 1. Et a > 1, siis peab leiduma algarv, mis arvu a jagab. Kuna

8

Page 9: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

oletasime, et p1; : : : ; pn on ainsad algarvud, siis peab leiduma selline i 2 f1; : : : ; ng, et pi j a. Seega saame lause 1.2

p~ohjal, et pi j a� p1p2 : : : pn = 1, mis on vastuolus sellega, et pi > 1. 2

Lause 1.6 t~ottu v~oib iga naturaalarvu esitada �uheselt kas kujul 4k, 4k + 1, 4k + 2 v~oi 4k + 3, kus k 2 N[ f0g,s~oltuvalt sellest, millise j�a�agi annab see naturaalarv jagamisel 4-ga. On selge, et arvud 4k ja 4k+ 2 = 2(2k+ 1) on

paarisarvud ja seega kordarvud. Paaritud arvud jagunevad kahte l~opmatusse jadasse: �uhed, mis on kujul 4k + 1;

s.t.

1; 5; 9; 13; 17; 21; : : :

ja teised, mis on kujul 4k + 3, s.t.

3; 7; 11; 15; 19; 23; : : : :

M~olemas jadas on nii alg- kui kordarve. Osutub, et analoogiliselt eelmise teoreemiga, saab t~oestada, et teine jada

sisaldab l~opmata palju algarve. Selleks t~oestame enne �uhe tillukese lemma.

Lemma 2.3. Kui kaks naturaalarvu on kujul 4k+ 1, siis nende korrutis on samal kujul.

T~oestus. Olgu m = 4k + 1 ja n = 4l + 1, k; l 2 N[ f0g. Siis mn = (4k + 1)(4l + 1) = 4(4kl + k + l) + 1. 2

Teoreem 2.4. On l~opmata palju algarve kujul 4k+ 3.

T~oestus. Oletame j�allegi, et on vaid l~oplik arv algarve kujul 4k + 3. Olgu nad t�ahistatud q1; : : : ; qn. Vaatleme

naturaalarvu a = 4q1q2 : : : qn � 1 = 4(q1q2 : : : qn � 1) + 3. Olgu a = r1r2 : : : rs arvu a lahutus algtegureiks. Kuna a

on paaritu arv, siis �ukski ri ei ole 2. Seega iga ri on kas kujul 4k+1 v~oi 4k+3. Lemma 2.3 t~ottu peab v�ahemalt �uks

tegureist r1; : : : ; rs olema kujul 4k + 3. Olgu ri = 4k + 3; k 2 N[ f0g. Siis peab leiduma selline j, et ri = qj > 1.

J�arelikult ri j a� 4q1q2 : : : qn = �1, vastuolu. 2

Tegelikult ka jadas (4k + 1)k2N[f0g on l~opmata palju algarve (vt. lause 9.8) ja veelgi enam, kehtib Dirichlet'

poolt 1837. a. t~oestatud teoreem algarvude kohta aritmeetilises jadas.

Teoreem 2.5 (Dirichlet). Kui a ja b on �uhistegurita naturaalarvud, siis aritmeetilises jadas

a; a+ b; a+ 2b; a+ 3b; : : :

on l~opmata palju algarve.

Teisest k�uljest, ei ole �uhtegi aritmeetilist jada a; a+b; a+2b; : : := (a+kb)k2N[f0g; a; b 2 N, mis koosneks ainult

algarvudest. T~oepoolest, kui k~oik selle jada liikmed on kordarvud, siis on v�aide ilmne. Kui aga leidub l 2 N[ f0gnii, et a + lb = p, kus p on algarv, siis a + (l + p)b = a + lb + pb = p(1 + b) on kordarv. Veelgi enam, iga m 2 Nkorral a + (l +mp)b = a+ lb+mpb = p(1 +mb) on kordarv ja seega jada (a+ kb)k2N[f0g sisaldab l~opmata palju

kordarve.

On p�ustitatud h�upotees, et mistahes naturaalarvu n korral leidub aritmeetiline jada pikkusega n, mis koosneb

algarvudest. N�aiteks n = 3 ja n = 4 korral on sellisteks jadadeks 41; 47; 53 ja 251; 257; 263;269.

Et algarvude hulk on l~opmatu, oleks huvitav teada, kuidas nad paiknevad teiste naturaalarvude seas. J�arjesti-

kuste algarvude vahe v~oib olla v�aike, nagu n�aiteks paaride 11 ja 13, 17 ja 19 v~oi 1 000 000 000 061 ja 1 000 000 000 063

korral. Selliseid j�arjestikuste algarvude p ja p+2 paare nimetatakse algarvukaksikuiks. Kas selliseid paare on l~opmata

palju v~oi mitte, ei ole teada.

Samas v~oivad kaks j�arjestikust algarvu olla teineteisest kuitahes kaugel. T�apsemalt, iga naturaalarvu n korral

leidub n j�arjestikust kordarvu. Nendeks on n�aiteks

(n + 1)! + 2; (n+ 1)! + 3; : : : ; (n+ 1)! + (n + 1):

N�aiteks, kui tahame saada 4 j�arjestikust kordarvu, v~oime v~otta

5! + 2 = 122 = 2 � 615! + 3 = 123 = 3 � 415! + 4 = 124 = 4 � 315! + 5 = 125 = 5 � 25:

Loomulikult on ka v�aiksemate j�arjestikuste kordarvude nelikuid, nt. 24; 25; 26; 27 v~oi 32; 33; 34; 35.

J�argmine teoreem �utleb, et naturaalarvule n j�argnevat algarvu ei pea siiski otsima v�aga kaugelt.

Teoreem 2.6 (T�seb~o�sev). Kui n > 3 on naturaalarv, siis n ja 2n� 2 vahel leidub v�ahemalt �uks algarv.

9

Page 10: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Selle teoreemi t~oestas esimesena 1850. a. vene matemaatik T�seb~o�sev (1821{1894). H�upoteesina s~onastas selle

v�aite 1845. a. prantsuse matemaatik Bertrand (1822{1900) ning seet~ottu kutsutakse seda v�aidet vahel ka Bertrand'i

postulaadiks. Tegelikult kehtib isegi tugevam v�aide.

Teoreem 2.7. Kui n > 5 on naturaalarv, siis n ja 2n vahel leidub v�ahemalt kaks erinevat algarvu.

Veel on loomulik k�usida, et kui palju on antud naturaalarvust v�aiksemaid algarve. Naturaalarvu n korral olgu

�(n) k~oigi arvust n v�aiksemate algarvude arv. T�apset valemit �(n) arvutamiseks pole. Mitmed matemaatikud

leidsid proovides, et suurte naturaalarvude korral on �(n) ligikaudu v~ordne avaldisega n= ln(n): Ja t~oepoolest,

1896. aastal ~onnestus prantsuse matemaatikuil Hadamard'il ja Vall�e Poussinil teineteisest s~oltumatult t~oestada, et

limn!1

�(n)

n= ln(n)= 1:

Sajandeid on matemaatikud otsinud valemit, mille j�argi saaks v�alja arvutada k~oik algarvud. Kui see ei ~onnestu,

siis v�ahemalt leida selline funktsioon, mille m�a�aramispiirkond oleks naturaalarvude hulk ja muutumispiirkond oleks

algarvude hulga mingi alamhulk. Keskajal oli laialt levinud arvamus, et ruutfunktsioon

f(n) = n2 + n+ 41

omandab vaid algarvulisi v�a�artusi. Tegelikult see muidugi nii ei ole, sest n = 40 ja n = 41 korral saame vastavalt

f(40) = 40 � 41 + 41 = 412 ja f(41) = 41 � 42 + 41 = 41 � 43. J�argmine v�a�artus f(42) = 1747 osutub j�alle algarvuks.

Pole teada, kas funktsioonil f on l~opmata palju algarvulisi v�a�artusi.

See, et n = 40 ja n = 41 korral saime kordarvud, polnud sugugi juhuslik. Kehtib �uldisem teoreem, mille

t~oestamisel kasutame j�argmist fakti (vt. [1], lause 7.1.9.).

Lause 2.8. n: astme pol�unoomil �ule nullitegureita kommutatiivse ringi ei ole selles ringis rohkem kui n juurt.

Teoreem 2.9 (Euler). �Uhegi t�aisarvuliste kordajatega mittekonstantse pol�unoomi v�a�artused ei ole k~oigi argumendinaturaalarvuliste v�a�artuste korral algarvud.

T~oestus. Oletame vastuv�aiteliselt, et leidub mittekonstantne pol�unoom

f(x) = akxk + ak�1x

k�1 + : : :+ a2x2 + a1x+ a0;

kus a0; : : : ; ak 2Z; mille v�a�artus iga naturaalarvu n korral on algarv. Siis muuhulgas f(1) = ak + : : :+ a0 = p on

algarv. Kui t 2 N[ f0g, siis kasutades Newtoni binoomvalemit saame

f(1 + tp) = ak(1 + tp)k + : : :+ a1(1 + tp) + a0 = (ak + : : :+ a1 + a0) + pg(t) = p+ pg(t) = p(1 + g(t));

kus g(t) on t�aisarvuliste kordajatega pol�unoom t suhtes. J�arelikult p j f(1 + tp), millest eelduse t~ottu saame, et

f(1 + tp) = p iga t 2 N [ f0g korral. Seega mittekonstantsel pol�unoomil f(x) � p on l~opmata palju t�aisarvulisi

juuri, mis on vastuolus lausega 2.8 2

1947. a. t~oestas Mills, et leidub selline positiivne reaalarv r , et avaldis f(n) =�r3

n�, kus btc t�ahistab reaalarvu

t alumist t�aisosa, s.t. suurimat t�aisarvu, mis ei ole suurem kui x, on algarv iga n 2 N korral. Arvu r tegeliku

v�a�artuse kohta pole aga midagi teada.

�Uheks kuulsamaks algarvude kohta k�aivaks lahendamata probleemiks on Goldbachi (1690{1764) poolt kirjava-

hetuses Euleriga 1742. a. p�ustitatud h�upotees.

Probleem 2.10 (Goldbach). Iga positiivne paarisarv on esitatav summana a+b, kus nii a kui ka b on kas algarvv~oi 1.

V~oi natuke �uldisemalt: kas iga 2-st suurem paarisarv on esitatav kahe algarvu summana. On lihtne n�aha, et

v�aikeste paarisarvude korral see t~oesti nii on:

2 = 1 + 1

4 = 2 + 2 = 1 + 3

6 = 3 + 3 = 1 + 5

8 = 3 + 5 = 1 + 7

10 = 3 + 7 = 5 + 5

12 = 5 + 7 = 1 + 11

14 = 3 + 11 = 7 + 7 = 1 + 13

16 = 3 + 13 = 5 + 11

18 = 5 + 13 = 7 + 11 = 1 + 17

20 = 3 + 17 = 7 + 13 = 1 + 19:

10

Page 11: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Kui Goldbachi h�upotees peaks paika pidama, siis saab iga 5-st suurema paaritu arvu esitada kolme paaritu algarvu

summana. Nimelt, kui n on 5-st suurem paaritu arv, siis n�3 on paarisarv ja suurem kui 2. Kui n�3 saaks esitada

kahe paaritu algarvu summana, siis n oleks kolme paaritu algarvu summa. K~oige enam on Goldbachi h�upoteesile

t~oestust otsides saavutanud vene matemaatik Vinogradov, kes 1937. a. n�aitas, et leidub selline naturaalarv N

(kaks aastat hiljem leiti, et N =jee

e41;96k), et k~oik sellest suuremad paaritud arvud on esitatavad kolme algarvu

summana. Sellest j�areldub, et k~oik piisavalt suured paarisarvud on esitatavad �ulimalt 4 paaritu algarvu summana.

Goldbachi probleem kuulub arvuteooria valdkonda, mida nimetatakse aditiivseks (s.o. liitmisega seotud) arvu-teooriaks. Veel tuntum, kui Goldbachi probleem, on aga j�argmine aditiivse arvuteooria probleem.

Teoreem 2.11 (Fermat' suur teoreem). Kui n > 3 on naturaalarv, siis v~orrandil

xn + yn = zn (5)

ei ole mittetriviaalseid ratsionaalarvulisi lahendeid.

Triviaalseks loetakse lahendit, mille v�ahemalt �uks komponent on 0.

Sellise h�upoteesi p�ustitas juba 1630. aastate l~opus prantsuse matemaatik Pierre de Fermat (1601{1665). Ta ise

andis selle v�aite t~oestuse juhul, kui n = 4. Kolme aastasaja kestel n�aitasid paljud matemaatikud Fermat' teoreemi

t~oestust otsides, et v~orrandil (5) ei ole lahendeid ikka suuremate ja suuremate astendajate korral. Korrektne

t~oestus �uldjuhul ~onnestus aga leida alles m�o�odunud sajandi l~opul. 23. juunil 1993. aastal teatas inglise matemaatik

Andrew Wiles (s�und. 1953) Cambridge'is peetud loengus, et on t~oestanud Fermat' teoreemi. T~oestamiseks kasutas

ta algebralise geomeetria vahendeid, muuhulgas elliptilisi k~overaid ja modulaarseid vorme. See t~oestus, mille ta

v�alja pakkus, oli k�ull pisut vigane, kuid ta suutis need vead parandada ning l~oplikult ilmus tema t�o�o ajakirja

Annals of Mathematics 1995. a mainumbris.

11

Page 12: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

3. Kongruentsi m~oiste ja lihtsamad omadused

Kongruentsi m~oiste v~ottis kasutusele Gauss (1777{1855) oma teoses \Disquisitiones Arithmeticae", mis pani

aluse kaasaegsele arvuteooriale.

De�nitsioon 3.1. Olgu a; b 2 Zja n 2 N. �Oeldakse, et a ja b on kongruentsed mooduli n j�argi (ja kirjutatakse

a � b (mod n)), kui n j b� a, s.t. kui leidub selline k 2Z, et b = a+ kn ehk a = b+ (�k)n.

N�aide 3.2. 7 � 22 (mod 5), sest 5 j 22� 7 = 15 ehk 22 = 7 + 3 � 5.

Kuna mooduli 1 j�argi on k~oik t�aisarvud paarikaupa kongruentsed, siis see juhtum ei paku meile huvi. Edaspidises

eeldame kongruentsidest k~oneldes, et moodul n on v�ahemalt 2.

Lause 3.3. Mistahes t�aisarvude a ja b korral a � b (mod n) parajasti siis, kui a ja b annavad arvuga n j�a�agigajagamisel sama j�a�agi.

T~oestus. Tarvilikkus. Olgu a � b (mod n), s.t. leidugu selline k 2Z, et b = a+ kn. Jagades a arvuga n, saame

mingi j�a�agi r: a = qn+ r, kus 0 � r < n. J�arelikult b = a+ kn = (qn+ r) + kn = (q+ k)n+ r, mis t�ahendabki, et

b annab arvuga n jagades sama j�a�agi r, mis a.

Piisavus. Oletame, et a = q1n + r ja b = q2n + r, kus 0 � r < n. Siis b� a = (q2n + r)� (q1n+ r) = (q2 � q1)n,

kust saame, et n j b� a ehk a � b (mod n). 2

Lause 3.4. T�aisarvude kongruentsusseos on ekvivalentsusseos.

T~oestus. Olgu a; b; c 2Zja n 2 N:Re eksiivsus. Kuna a� a = 0 ja n j 0, siis a � a (mod n).

S�ummeetrilisus. Kui a � b (mod n); ehk n j b� a; siis ka n j a� b, ehk b � a (mod n).

Transitiivsus. Oletame, et a � b (mod n) ja b � c (mod n). Siis n j b�a ja n j c�b. J�arelikult n j (c�b)+(b�a) =

c� a; ehk a � c (mod n). 2

T�ahistame s�umboliga a k~oigi selliste t�aisarvude hulga, mis on kongruentsed t�aisarvuga a mooduli n j�argi, s.o.

a = fb 2Zj a � b (mod n)g = fa+ kn j k 2Zg;

ja nimetame selliseid hulki j�a�agiklassideks mooduli n j�argi. Kongruentsusseose re eksiivsuse t~ottu a 2 a iga t�aisarvu

a korral.

Lause 3.5. 1. Iga a; b 2Zkorral a = b parajasti siis, kui a � b (mod n).

2. Mooduli n j�argi leidub t�apselt n erinevat j�a�agiklassi.

T~oestus. 1. Tarvilikkus. Kui a = b , siis b 2 a ja j�arelikult a � b (mod n).

Piisavus. Kui a � b (mod n), siis b 2 a. Mistahes t�aisarvu c korral, kui c 2 b, s.t. b � c (mod n), siis kong-

ruentsusseose transitiivsuse t~ottu ka a � c (mod n) ja c 2 a. Seega b � a. Analoogiliselt saab n�aidata, et a � b

ning j�arelikult a = b.

2. Vaatleme j�a�agiklasse 0; 1; : : : ; n� 1 mooduli n j�argi. Kui a 2 Z ja a jagamisel arvuga n tekib j�a�ak r, s.t.

a = nq + r; 0 � r < n, siis a � r (mod n) ning 1. p~ohjal a = r. Seega iga j�a�agiklass mooduli n j�argi on

v~ordne �uhega j�a�agiklassidest 0; 1; : : : ; n� 1. Lause 3.3 t~ottu iga i; j 2 f0; 1; : : : ; n� 1g korral, kui i 6= j, siis i 6� j

(mod n) (sest i ja j annavad arvuga n jagades erinevad j�a�agid i ja j) ja v�aite 1 t~ottu siis ka i 6= j, s.t. j�a�agiklassid

0; 1; : : : ; n� 1 on k~oik erinevad. 2

Kongruentsusseost v~oib vaadelda kui v~ordusseose �uldistust: kui t�aisarvud on v~ordsed, siis on nad kongruentsed,

kuid mitte tingimata vastupidi. Sellegipollest on kongruentsidel mitmed v~ordustega sarnased omadused. N�aiteks

v~oib kongruentside vastavaid pooli omavahel liita ja korrutada.

Lause 3.6. Kui a1 � b1 (mod n) ja a2 � b2 (mod n), siis a1 + a2 � b1 + b2 (mod n) ja a1a2 � b1b2 (mod n).

T~oestus. Oletame, et n j b1�a1 ja n j b2�a2. Siis n j (b1�a1)+(b2�a2) = (b1+b2)�(a1+a2), s.t. a1+a2 � b1+b2(mod n). Et b1b2 � a1a2 = b1(b2 � a2) + a2(b1 � a1), siis n j b1b2 � a1a2 ning j�arelikult a1a2 � b1b2 (mod n). 2

J�areldus 3.7. Kui f(x) on t�aisarvuliste kordajatega pol�unoom ning a � b (mod n); siis f(a) � f(b) (mod n).

12

Page 13: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Olgu f(x) = akxk+ ak�1x

k�1+ : : :+ a1x+ a0; kus a0; : : : ; ak 2Z, ning olgu a � b (mod n). Kasutades

lauset 3.6 saame, et iga i = 1; : : : ; k korral ai � bi (mod n). Kuna ai � ai (mod n), siis j�allegi lauset 3.6 kasutades

saame, et aiai � aib

i (mod n) iga i = 1; : : : ; k korral. Siis aga ka

f(a) = akak + ak�1a

k�1 + : : :+ a1a+ a0 � akbk + ak�1b

k�1 + : : :+ a1b+ a0 = f(b) (mod n):

2

N�aide 3.8. N�aitame, et pol�unoomil x2 � 117x+ 31 ei ole t�aisarvulisi juuri.

Vaatleme moodulit n = 2. Siis iga t�aisarvu a korral kas a � 0 (mod 2) v~oi a � 1 (mod 2) ja seega, kui f(x)

on t�aisarvuliste kordajatega pol�unoom, siis j�arelduse 3.7 p~ohjal kas f(a) � f(0) (mod 2) v~oi f(a) � f(1) (mod 2).

Kui f(x) = akxk + ak�1x

k�1 + : : : + a1x + a0, siis f(0) = a0 ja f(1) = ak + ak�1 + : : : + a1 + a0. Seega, kui

f(x) 2Z[x] ning f(0) ja f(1) on m~olemad paaritud arvud (s.o. kongruentsed 1-ga mooduli 2 j�argi), siis pol�unoomil

f(x) ei ole t�aisarvulisi juuri, sest kui a 2Zoleks pol�unoomi f(x) juur, siis oleks f(a) = 0 � 0 (mod 2).

Et 31 ja 1�117+31 on paaritud arvud, siis pol�unoomil x2�117x+31 ei saa olla t�aisarvulisi juuri. Samamoodi

ei saa t�aisarvulisi juuri olla ka n�aiteks pol�unoomidel 2x2 � 2x+ 1 ja 3x3 + 2x2 + x+ 3.

T~oestame veel m~oned kongruentsusseose omadused.

Lause 3.9. Iga t�aisarvu k 6= 0 korral a � b (mod n) parajasti siis, kui ka � kb (mod kn).

T~oestus. Olgu k 6= 0. Siis kasutades seda, et nullist erineva t�aisarvu v~oib taandada, saame

a � b (mod n) () n j b� a() (9x 2Z)(nx= b� a)

() (9x 2Z)((kn)x= kb� ka)() kn j kb� ka() ka � kb (mod kn):

2

Lause 3.10. Kui ka � kb (mod n) ja k 6= 0, siis a � b (mod n(k;n)

).

T~oestus. Olgu d = (k; n), n = dn0 ja k = dk0, siis j�arelduse 1.10 p~ohjal (n0; k0) = 1. Kuna n j kb� ka, siis leidub

selline x 2Z, et nx = kb� ka. Asendades n ja k saame, et dn0x = dk0b� dk0a. Kuna k 6= 0, siis ka d 6= 0 ja seega

n0x = k0b� k0a. Sellest, et n0 j k0b� k0a = k0(b � a) ja (n0; k0) = 1, saame j�arelduse 1.11 p~ohjal, et n0 = ndj b � a,

ehk a � b (mod nd). 2

J�areldus 3.11. Kui ka � kb (mod n), k 6= 0, ja (k; n) = 1, siis a � b (mod n).

N�aide 3.12. Sellest, et 33 � 15 (mod 9) ja (3; 9) = 3, saame lause 3.10 p~ohjal, et 11 � 5 (mod 3). Sellest, et

�35 � 45 (mod 8) ja (5; 8) = 1, saame j�arelduse 3.11 p~ohjal, et �7 � 9 (mod 8).

N�aitena kongruentside lihtsamate omaduste rakendamisest vaatame, kuidas nende abil p~ohjendada jaguvustun-

nuseid.

Lause 3.13. Olgun = ak � 10k + ak�1 � 10k�1 + : : :+ a1 � 10 + a0 = akak�1 : : :a1a0;

kus 0 � ai � 9 (s.o. n on arv, mille k�umnendnumbreiks on ak; : : : ; a0). Siis

1. 3 j n() 3 j a0 + a1 + : : :+ ak;

2. 9 j n() 9 j a0 + a1 + : : :+ ak;

3. 11 j n() 11 j a0 � a1 + a2 � : : :+ (�1)kak:

T~oestus. Olgu f(x) = akxk + ak�1x

k�1 + : : :+ a1x+ a0. Siis n = f(10).

2. Kuna 10 � 1 (mod 9), siis j�arelduse 3.7 p~ohjal n = f(10) � f(1) = a0 + a1 + : : :+ ak (mod 9). Seega arvud n

ja a0 + a1 + : : :+ ak annavad 9-ga jagades sama j�a�agi, s�a�aljuures n jagub 9-ga (s.o. annab j�a�agi 0) parajasti siis,

kui a0 + a1 + : : :+ ak jagub 9-ga.

Tunnuse 1. saab t~oestada analoogiliselt.

3. Et 10 � �1 (mod 11), siis n = f(10) � f(�1) = a0 � a1 + a2� : : :+ (�1)kak (mod 11), millest j�areldubki, et n

jagub 11-ga parajasti siis, kui a0 � a1 + a2 � : : :+ (�1)kak jagub 11-ga. 2

13

Page 14: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

4. J�a�agiklassiringid

T�ahistame k~oigi j�a�agiklasside hulka (mooduli n > 1 j�argi) s�umboligaZn, s.t.

Zn = fa j a 2Zg=�0; 1; : : : ; n� 1

:

Selle hulga saame muuta kommutatiivseks ringiks de�neerides liitmise ja korrutamise v~ordustega

a+ b = a + b;

ab = ab;

iga a; b 2Zn korral. Lausest 3.6 j�areldub, et need de�nitsioonid on korrektsed, s.t. ei s~oltu j�a�agiklasside esindajate

valikust. Ringi de�nitsiooni tingimuste t�aidetus j�areldub t�aisarvude vastavatest omadustest. RingiZn nimetatakse

j�a�agiklassiringiks mooduli n j�argi. J�a�agiklassiringi, mille iga nullist (s.o. j�a�agiklassist 0) erinev element on p�o�oratav,

nimetatakse j�a�agiklassikorpuseks.

Edaspidises l�aheb vaja kahte lemmat.

Lemma 4.1. Kui arvud n1; : : : ; ns; n 2 N on sellised, et iga i = 1; : : : ; s korral (ni; n) = 1, siis (n1 : : : ns; n) = 1.

T~oestus. Oletame, et (n1 : : :ns; n) = d > 1. Siis leidub selline algarv p; et p j d ning seega p j n1 : : : ns ja p j n.J�arelduse 1.13 p~ohjal peab leiduma selline i, et p j ni. Siis aga p j (ni; n), mis on vastuolus sellega, et (ni; n) = 1. 2

Lemma 4.2. Kui arvud n1; : : : ; ns; a 2 N on sellised, et iga i = 1; : : : ; s korral ni j a ja iga i; j = 1; : : : ; s korral(ni; nj) = 1, siis n1 : : : ns j a.

T~oestus. T~oestame selle v�aite induktsiooniga s j�argi. Kui s = 1, siis on k~oik korras. Oletame n�u�ud, et s > 1 ja et

s� 1 korral v�aide kehtib. Siis n1 : : :ns�1 j a. Lemma 4.1 p~ohjal (n1 : : :ns�1; ns) = 1. J�arelikult teoreemi 1.7 p~ohjal

leiduvad sellised t�aisarvud x ja y, et n1 : : : ns�1x + nsy = 1. Korrutades viimase v~orduse m~olemaid pooli arvuga

a saame n1 : : : ns�1ax+ nsay = a. N�aeme, et n1 : : : ns jagab selle v~orduse vasakut poolt ja seega peab jagama ka

paremat poolt ehk arvu a. 2

J�a�agiklassiringide uurimisel kasutame m~oningaid ringide �uldisi omadusi, andes ka nende omaduste t~oestused

�uldjuhul. Seejuures r~ohutame veelkord, et selles kursuses vaatleme vaid selliseid ringe, mis on assotsiatiivsed ja

�uhikelemendiga.

Meenutame, kuidas de�neeritakse ringide R1; : : : ; Rs otsekorrutis R1 � : : : � Rs. Nimelt v~oetakse hulkade

R1; : : : ; Rs otsekorrutis

R1 � : : :�Rs = f(r1; : : : ; rs) j ri 2 Rigja de�neeritakse sellel hulgal tehted komponentide kaupa, s.t.

(r1; : : : ; rs) + (r01; : : : ; r0

s) = (r1 + r01; : : : ; rs + r0s);

(r1; : : : ; rs)(r0

1; : : : ; r0

s) = (r1r0

1; : : : ; rsr0

s):

Tulemuseks on ring, mille nullelemendiks on (0; : : : ; 0), kus elemendi (r1; : : : ; rs) vastandelemendiks on element

(�r1; : : : ;�rs) ning �uhikelemendiks on (1; : : : ; 1).

Teoreem 4.3. Kui arvud n1; : : : ; ns 2 N on paarikaupa �uhistegurita ja n = n1 : : : ns, siis ringid Zn ja Zn1� : : :�Zns on isomorfsed.

T~oestus. De�neerime kujutuse f :Zn �!Zn1 � : : :�Zns j�argmiselt:

f(a) = (a1; : : : ; as) ;

mistahes a 2Zn korral, kus ai on arvu a j�a�agiklass mooduli ni j�argi.

Veendume, et f on korrektselt de�neeritud. Selleks oletame, et a = b, s.t. n j b � a. Et ni j n, i = 1; : : : ; s, siis

jaguvusseose transitiivsuse t~ottu ni j b� a, s.t. ai = bi ja (a1; : : : ; as) = (b1; : : : ; bs).

N�aitame, et f on injektiivne. Selleks oletame, et f(a) = f(b), see t�ahendab, et (a1; : : : ; as) =�b1; : : : ; bs

�. Siis

ai = bi, millest j�areldub, et ni j b � a iga i = 1; : : : ; s korral. Et arvud n1; : : : ; ns on paarikaupa �uhistegurita, siis

lemma 4.2 p~ohjal n j b� a ehk a = b.

Sellest, et f on injektiivne ja jZnj = n = n1 : : :ns = jZn1 � : : :�Znsj, j�areldub, et f on s�urjektiivne.

Arvestades, et tehted ringide otsekorrutisel on de�neeritud komponenthaaval, saame, et

f(a + b) = f(a + b) =�a+ b1; : : : ; a+ bs

�=�a1 + b1; : : : ; as + bs

�= (a1; : : : ; as) +

�b1; : : : ; bs

�= f (a) + f

�b�

ja analoogiliselt f�ab�= f (a) f

�b�. Lisaks sellele f(1) = (11; : : : ; 1s):

Seega f on ringide isomor�sm. 2

14

Page 15: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Lause 4.4. Ringi R p�o�oratavate elementide hulk U (R) on r�uhm.

T~oestus. Olgu a; b 2 U (R). Siis leiduvad sellised x; y 2 R, et ax = xa = 1 ja by = yb = 1. J�arelikult (ab)(yx) =

a(by)x = ax = 1 ja (yx)(ab) = y(xa)b = yb = 1, s.t. ab 2 U (R). Seega korrutamine on algebraline tehe hulgal

U (R). Korrutamine on assotsiatiivne kogu ringil, seega ka hulgal U (R). Lisaks sellele 1 2 U (R) ja U (R) iga elemendi

p�o�ordelement on samuti p�o�oratav. 2

Lause 4.5. Kui f : R ! S on ringide R ja S isomor�sm, siis f(U (R)) = U (S). Seega f jU(R) on r�uhmadeisomor�sm.

T~oestus. Olgu a 2 U (R), s.t. leidub x 2 R, nii et ax = xa = 1. N�aitame, et f(a) 2 U (S). T~oepoolest, f(a)f(x) =

f(ax) = f(1) = 1 ja analoogiliselt f(x)f(a) = 1: Seega f(U (R)) � U (S).

Olgu n�u�ud u 2 U (S), s.t. leidub v 2 S nii, et uv = vu = 1. Kujutuse f s�urjektiivsuse t~ottu leiduvad a; b 2 R nii,

et f(a) = u ja f(b) = v. Seega f(1) = 1 = uv = f(a)f(b) = f(ab): Kujutuse f injektiivsusest j�areldub, et ab = 1.

Analoogiliselt ba = 1, a 2 U (R) ja seega u = f(a) 2 f(U (R)). J�arelikult ka U (S) � f(U (R)). 2

J�areldus 4.6. Kui arvud n1; : : : ; ns 2 N on paarikaupa �uhistegurita ja n = n1 � : : : � ns, siis r�uhmad U (Zn) jaU (Zn1 � : : :�Zns) on isomorfsed.

Leiame ringi Zn p�o�oratavad elemendid.

Teoreem 4.7. Iga n > 1 korralU (Zn) = fa 2Zn j (a; n) = 1g :

T~oestus. Olgu a 2 Zn p�o�oratav, s.t. leidugu selline b, et 1 = ab = ab. Lause 3.5 p~ohjal t�ahendab see seda, et

ab � 1 (mod n). J�arelikult leidub selline k 2Z, et ab = 1 + kn ehk ab� kn = 1. Teoreemi 1.7 t~ottu siis (a; n) = 1.

Seega U (Zn) � fa 2Zn j (a; n) = 1g.N�aitame vastupidist sisalduvust. Olgu (a; n) = 1. Siis leiduvad sellised k; l 2Z, et ak + nl = 1. J�arelikult

1 = ak + nl = ak + nl = ak + 0l = ak. S.t. a on p�o�oratav ja seega fa 2Zn j (a; n) = 1g � U (Zn). 2

N�aide 4.8. RingiZ9 p�o�oratavate elementide hulk

U (Z9) = fa 2Z9 j (a; 9) = 1g =�1; 2; 4; 5; 7; 8

:

Seejuures 1�1

= 1, 2�1

= 5 (ja seega 5�1

= 2), 4�1

= 7 ja 8�1

= 8.

Lause 4.9. J�a�agiklassiring Zn on korpus parajasti siis, kui n on algarv.

T~oestus. Tarvilikkus. Oletame, etZn on korpus, kuid n ei ole algarv, s.t. leiduvad sellised a; b 2 N , 1 < a; b < n,

et n = ab. Siis ab = n = 0, kuid a 6= 0 ja b 6= 0. Korpuse igal nullist erineval elemendil on olemas p�o�ordelement.

Korrutades v~orduse ab = 0 m~olemad pooled elemendiga a�1 saame, et b = 0, vastuolu. Seega n on algarv.

Piisavus. Olgu n algarv. Siis iga a 2Zkorral kas (a; n) = 1 v~oi (a; n) = n. Viimasel juhul n j a ja a = 0. Seega

kui a 2Zn n�0, siis (a; n) = 1 ja a 2 U (Zn). Kuna iga nullist erinev element on p�o�oratav, siis Zn on korpus. 2

15

Page 16: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

5. Arvuteoreetilisi funktsioone

�Uks t�ahtsam arvuteoreetiline funktsioon on Euleri funktsioon, mis loetleb, kui palju on antud naturaalarvust

v�aiksemaid ja selle arvuga �uhistegurita naturaalarve.

De�nitsioon 5.1. Euleri funktsioon ' : N �! N de�neeritakse v~ordusega

'(n) = jfx 2 N j 1 � x � n; (x; n) = 1gj :

Kui n � 2, siis (n; n) = n > 1. Seega kui n � 2, siis

'(n) = jfx 2 N j 1 � x < n; (x; n) = 1gj :

Silmas pidades teoreemi 4.7 saame, et iga n � 2 korral

'(n) = jU (Zn)j ;

s.t. '(n) on ringi Zn p�o�oratavate elementide arv.

N�aide 5.2. '(30) = 8, sest naturaalarvude seas, mis pole suuremad kui 30, on 8 sellist, mis on 30-ga �uhistegurita,

nimelt 1; 7; 11; 13; 17;19;23 ja 29.

Kui p on algarv, siis k~oik temast v�aiksemad naturaalarvud on temaga �uhistegurita ja ka vastupidi, kui na-

turaalarvul pole �uhiseid tegureid temast v�aiksemate naturaalarvudega, siis on ta algarv. Seega saame j�argmise

v�aite.

Lause 5.3. Naturaalarv p on algarv siis ja ainult siis, kui

'(p) = p� 1:

Teame, et mistahes naturaalarvu n > 1 saab esitada algarvude astmete korrutisena. P�u�uame leida valemit,

mille abil saaks leida '(n), kui on teada n esitus algarvude astmete korrutisena. Selleks leiame algul ' v�a�artuse

algarvu astmetel.

Lause 5.4. Kui p on algarv ja k naturaalarv, siis

'(pk) = pk � pk�1 = pk�1(p� 1):

T~oestus. Iga x 2 N korral on (x; pk) > 1 parajasti siis, kui p j x. Arve x, mis jaguvad arvuga p, on hulgas

f1; 2; : : : ; pkg pk�1 t�ukki; nimelt p; 2p; 3p; : : : ; (pk�1)p. Seega hulgas�1; 2; : : : ; pk

on t�apselt pk � pk�1 arvu, mis

on arvuga pk �uhistegurita. 2

N�aide 5.5. '(32) = 32 � 31 = 32�1(3 � 1) = 6. Need kuus 9-st v�aiksemat ja temaga �uhistegurita arvu on

1; 2; 4; 5; 7;8 (vt. ka n�aidet 4.1).

Lause 5.6. Mistahes ringide R1; : : : ; Rs korral

U (R1 � : : :�Rs) = U (R1)� : : :� U (Rs):

M�arkus 5.7. Selle v~orduse vasakul poolel on r�uhm ja paremal poolel samuti: r�uhmade U (R1); : : : ; U (Rs) otse-

korrutis, mis saadakse kui hulkade otsekorrutisel

U (R1)� : : :� U (Rs) = f(u1; : : : ; us) j ui 2 U (Ri)g

de�neeritakse korrutamine komponenthaaval.

T~oestus. Mistahes elementide r1 2 R1; : : : ; rs 2 Rs korral

(r1; : : : ; rs) 2 U (R1 � : : :�Rs)

() (9(r01; : : : ; r0s) 2 R1 � : : :� Rs) [(r1; : : : ; rs)(r01; : : : ; r

0s) = (r01; : : : ; r

0s)(r1; : : : ; rs) = (1; : : : ; 1)]

() (9(r01; : : : ; r0s) 2 R1 � : : :� Rs)h(r1r

0

1; : : : ; rsr0

s) = (r01r1; : : : ; r0

srs) = (1; : : : ; 1)i

() (9(r01; : : : ; r0s) 2 R1 � : : :� Rs)(8i 2 f1; : : : ; sg)hrir

0

i = r0iri = 1i

() (8i 2 f1; : : : ; sg) [ri 2 U (Ri)]

() (r1; : : : ; rs) 2 U (R1)� : : :� U (Rs):

2

16

Page 17: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Teoreem 5.8. Kui n1; : : : ; ns on paarikaupa �uhistegurita naturaalarvud, siis

'(n1 : : :ns) = '(n1) : : : '(ns)

(Euleri funktsioon on n~orgalt multiplikatiivne).

T~oestus. T�ahistame n = n1 : : : ns. Kasutades j�areldust 4.6 ja lauset 5.6 saame, et

'(n) = jU (Zn)j = jU (Zn1 � : : :�Zns)j = jU (Zn1)� : : :� U (Zns)j= jU (Zn1)j � : : : � jU (Zns)j = '(n1) : : :'(ns):

2

Teoreem 5.9. Kui n > 1 ja n = pk11 : : : pkss on arvu n standardkuju, siis

'(n) = pk1�11 : : : pks�1s (p1 � 1) : : : (ps � 1):

T~oestus. Kuna p1; : : : ; ps on paarikaupa erinevad algarvud, siis pk11 ; : : : ; pkss on paarikaupa �uhistegurita ning seega

teoreemist 5.8 ja lausest 5.4 j�areldub, et

'(n) = '(pk11 ) : : :'(pkss ) = pk1�11 (p1 � 1) : : : pks�1s (ps � 1) = pk1�11 : : : pks�1s (p1 � 1) : : : (ps � 1):

2

N�aide 5.10. '(360) = '(23 � 32 � 5) = 23�1 � 32�1 � 51�1(2� 1)(3� 1)(5� 1) = 4 � 3 � 2 � 4 = 96;

'(2002) = '(2 � 7 � 11 � 13) = 6 � 10 � 12 = 720.

Toome �ara veel m~oned Euleri funktsiooni omadused.

Lause 5.11. Kui n ja d on naturaalarvud ning d j n, siis

jfx 2 N j 1 � x � n; (x; n) = dgj = '�nd

�:

T~oestus. T�ahistame fx 2 N j 1 � x � n; (x; n) = dg = K. Siis hulka K kuuluvad arvud peavad jaguma arvuga

d. Seega hulka K kuuluvad sellised naturaalarvud x = kd 2�d; 2d; : : : ; n

dd

=�kd j k 2 N; 1� k � n

d

, mis

rahuldavad tingimust (kd; n) = d. J�areldusest 1.10 saame, et v~ordus (kd; n) = d on samav�a�arne v~ordusega (k; nd) =

1. Seega hulga K elemente on niipalju, kuipalju on naturaalarve k, 1 � k � nd, mille korral

�k; n

d

�= 1. Teiselt poolt

aga vastavalt Euleri funktsiooni de�nitsioonile ka '�nd

�=���k 2 N j 1 � k � n

d;�k; n

d

�= 1�� = jKj. 2

J�argmist Euleri funktsiooni omadust m�arkas esimesena Gauss.

Teoreem 5.12 (Gauss). Iga naturaalarvu n korralXdjn

'(d) = n:

T~oestus. Olgu 1=d1; d2; : : : ; ds=n arvu n k~oik naturaalarvulised jagajad. T�ahistame

Ki = fx 2 N j 1 � x � n; (x; n) = dig :

Hulgad K1; : : : ;Ks on l~oikumatud jaFs

i=1Ki = f1; 2; : : : ; ng ; sest iga a 2 f1; 2; : : : ; ng korral leidub selline i, et

(a; n) = di. Kasutades seda, et fd1; : : : ; dsg =n

nd1; : : : ; n

ds

oja lauset 5.11, saame

n =

�����sG

i=1

Ki

����� =sX

i=1

jKij =sX

i=1

'

�n

di

�=

sXi=1

'(di):

2

�Uks kasulikumaid Euleri funktsiooni rakendusi on j�argmine v�aide, mida edaspidi kutsume Euleri teoreemiks.

Teoreem 5.13 (Euler). Kui a 2Z, n 2 N ja (a; n) = 1, siis

a'(n) � 1 (mod n):

17

Page 18: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Vaatleme j�a�agiklassiringiZn p�o�oratavate elementide r�uhma (U (Zn); �). Et (a; n) = 1, siis teoreemi 4.7

p~ohjal a 2 U (Zn). Olgu m elemendi a j�ark r�uhmas U (Zn), s.t. tema poolt moodustatud alamr�uhma hai j�ark,

s.o. v�ahim selline naturaalarv, et am = 1 ([1], lk. 156, 164). Kuna l~opliku r�uhma elemendi j�ark jagab Lagrange'i

teoreemi t~ottu r�uhma j�arku, siis m j jU (Zn)j = '(n), s.t leidub selline k 2 N, et mk = '(n). Seega r�uhmas U (Zn)

saame, et

a'(n) = a'(n) = amk = (am)k = 1k= 1:

J�arelikult lause 3.5 p~ohjal a'(n) � 1 (mod n). 2

Euleri teoreem annab �uhe v~oimaluse r�uhma U (Zn) elemendi a p�o�ordelemendi leidmiseks. Nimelt v~ordusest

1 = a'(n) = a � a'(n)�1 j�areldub, et

a�1 = a'(n)�1: (6)

J�allegi, arvutuslikult on p�o�ordelemendi leidmiseks otstarbekam kasutada Eukleidese algoritmi.

J�areldusena Euleri teoreemist ja lausest 5.3 saame Fermat' v�aikse teoreemi.

Teoreem 5.14 (Fermat' v�aike teoreem). Kui p on algarv, ja a on t�aisarv, mis ei jagu arvuga p, siis

ap�1 � 1 (mod p):

J�areldus 5.15. Kui p on algarv, siis iga t�aisarvu a korral

ap � a (mod p):

T~oestus. Kui p j a, siis ap � 0 � a (mod p) . Kui p 6 j a, siis Fermat v�aikse teoreemi t~ottu ap�1 � 1 (mod p),

millest j�areldub, et ap � a (mod p). 2

N�aide 5.16. Euleri teoreemi rakendusena leiame arvu 3256 kaks viimast numbrit.

Selleks tuleb leida j�a�ak, mis tekib arvu 3256 jagamisel 100-ga, s.o. v�ahim mittenegatiivne t�aisarv, millega 3256

on kongruentne mooduli 100 j�argi. Kuna (3; 100) = 1 ja '(100) = '(22 � 52) = 2 � 5 � 4 = 40, siis Euleri teoreemi

p~ohjal 340 � 1 (mod 100). Et 256 = 6 � 40 + 16, siis

3256 = 36�40+16 = (340)6 � 316 � 316 (mod 100):

Seega j�a�ab veel vaid leida, millega on 316 kongruentne mooduli 100 j�argi:

316 = 814 � (�19)4 = 3612 � 612 � 21 (mod 100):

J�arelikult arv 3256 l~opeb numbritega 2 ja 1.

J�argnevalt vaatleme M�obiuse funktsiooni.

De�nitsioon 5.17. M�obiuse funktsioon � : N! N de�neeritakse v~ordusega

�(n) =

8<:

1; kui n = 1;

0; kui leidub algarv p nii, et p2 j n;(�1)s; kui n = p1 � : : : � ps; kus p1; : : : ; ps on paarikaupa erinevad algarvud.

Teoreem 5.18. Kui n 2 N, siis Xdjn

�(d) =

�1

n

�=

�1; kui n = 1;

0; kui n > 1:

T~oestus. Kui n = 1, siis on v�aide ilmne. Olgu n > 1 ja esitame ta standardkujul n = pk11 : : : pkss . SummassePdjn �(d) tulevad nullist erinevad liidetavad ainult d = 1 ja selliste jagajate d korral, mis on erinevate algarvude

korrutised. SeegaXdjn

�(d) = �(1) + �(p1) + : : :+ �(ps) + �(p1p2) + : : :+ �(ps�1ps) + : : :+ �(p1p2 : : : ps)

= 1 +

�s

1

�(�1) +

�s

2

�(�1)2 + : : :+

�s

s

�(�1)s = (1� 1)s = 0:

2

Euleri ja M�obiuse funktsioon on seotud j�argmise valemi abil.

18

Page 19: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Teoreem 5.19. Kui n 2 N , siis

'(n) =Xdjn

�(d)n

d:

T~oestus. Euleri funktsiooni de�nitsiooni p~ohjal on ilmne, et

'(n) =

nXk=1

�1

(n; k)

�:

Kasutades teoreemi 5.18, kus n osas on v~oetud (n; k), saame

'(n) =

nXk=1

Xdj(n;k)

�(d) =

nXk=1

Xdjn

djk

�(d):

Kui �kseerida arvu n jagaja d, siis tuleb arvu �(d) liita iseendale niimitu korda, kuipalju on hulgas f1; 2; : : : ; ngarvu d kordseid. Kuna neid on n

dt�ukki, siis

'(n) =Xdjn

ndX

i=1

�(d) =Xdjn

�(d)

ndX

i=1

1 =Xdjn

�(d)n

d:

2

Vaatleme veel m~oningaid arvuteoreetilisi funktsioone.

De�nitsioon 5.20. Kui n on naturaalarv, siis t�ahistagu � (n) arvu n k~oigi naturaalarvuliste jagajate arvu ning

�(n) arvu n k~oigi naturaalarvuliste jagajate summat.

N�aide 5.21. Kuna arvu 12 naturaalarvulisteks jagajateks on 1; 2; 3; 4; 6 ja 12, siis � (12) = 6 ja �(12) = 1 + 2 +

3 + 4 + 6 + 12 = 28:

Kui on teada arvu n algtegureiks lahutus, siis j�argmine teoreem annab lihtsa v~oimaluse funktsioonide � ja �

arvutamiseks.

Teoreem 5.22. Kui n > 1 ja n = pk11 pk22 : : : pkss on arvu n standardkuju, siis

1.� (n) = (k1 + 1)(k2 + 1) : : : (ks + 1);

2.

�(n) =pk1+11 � 1

p1 � 1� p

k2+12 � 1

p2 � 1� : : : � p

ks+1s � 1

ps � 1:

T~oestus. 1. T�anu lausele 1.19 on arvu n jagajaiks need ja ainult need arvud, millel on kuju pl11 : : : plss , kus

0 � li � ki, i = 1; : : : ; s. Aritmeetika p~ohiteoreemi t~ottu annavad erinevad astendajate komplektid erinevad n

jagajad. Astendaja l1 valikuks on k1 + 1 v~oimalust, astendaja l2 valikuks on k2 + 1 v~oimalust jne. Seega on arvul

n kokku (k1 + 1)(k2 + 1) : : : (ks + 1) erinevat jagajat.

2. Et leida �(n) v�a�artust, vaatleme korrutist

(1 + p1 + p21 + : : :+ pk11 )(1 + p2 + p22 + : : :+ pk22 ) : : : (1 + ps + p2s + : : :+ pkss ):

Kui sulud avada, siis saadavas summas esineb arvu n iga naturaalarvuline jagaja t�apselt �uhe korra, seega

�(n) = (1 + p1 + p21 + : : :+ pk11 ) : : : (1 + ps + p2s + : : :+ pkss ):

Kasutades geomeetrilise jada summa valemit saame, et iga i = 1; : : : ; s korral

1 + pi + p2i + : : :+ pkii =pki+1i � 1

pi � 1;

millest j�areldubki v�aide 2. 2

Funktsiooniga � on seotud huvitav lahendamata probleem. Naturaalarvu n nimetatakse t�aiuslikuks , kui �(n) =2n: N�aiteks arvud 6 ja 28 on t�aiuslikud. �Uldisemalt, kui 2m � 1 on algarv, siis n = 2m�1(2m � 1) on t�aiuslik. Selle

t~oestas juba Eukleides. Euler n�aitas, et mistahes paarisarvuline t�aiuslik arv on sellisel kujul. Seega paarisarvuliste

t�aiuslike arvude leidmise probleem taandub algarvude 2m � 1 otsimisele. Selliseid algarve nimetatakse Mersenne'ialgarvudeks. Praeguse seisuga (11. veebr. 2002) on teada 39 Mersenne'i algarvu, neist suurim on 213466917 � 1,

millel on 4; 053 946 numbrit. Otsingud j�atkuvad (vt. ka http://www.mersenne.org). Lahendamata on probleemid:

kas leidub l~opmata palju t�aiuslikke arve ja kas leidub m~oni paaritu t�aiuslik arv.

19

Page 20: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

6. Tundmatut sisaldavad kongruentsid. Hiina j�a�agiteoreem.

6.1. �Ulesande p�ustitusest

Vaatleme tundmatut x sisaldavaid kongruentse

f(x) � 0 (mod n); (7)

kus

f(x) = akxk + ak�1x

k�1+ : : :+ a1x+ a0 (8)

on t�aisarvuliste kordajatega pol�unoom muutuja x suhtes ja ak 6� 0 (mod n). Kui k = 1, siis k~oneldakse lineaar-

kongruentsidest , kui k = 2, siis ruutkongruentsidest , jne. �Utleme, et t�aisarv x0 on kongruentsi (7) lahend, kuif(x0) � 0 (mod n): Kui mingi t�aisarv x0 on kongruentsi (7) lahend, siis t�anu j�areldusele 3.7 ka k~oik arvuga x0mooduli n j�argi kongruentsed arvud on selle kongruentsi lahendid. Seep�arast loeme kongruentsi (7) lahendiks tervet

j�a�agiklassi x0 2Zn ja lahendit m�argime ka j�argmiselt:

x � x0 (mod n):

See, et f(x0) � 0 (mod n) on lause 3.3 t~ottu samav�a�arne sellega, et f(x0) = 0 ringis Zn. Arvestades seda,

kuidas on de�neeritud liitmine ja korrutamine j�a�agiklassiringis, on viimane samav�a�arne sellega, et f (x0) = 0, kus

f (x) = akxk + ak�1x

k�1 + : : :+ a1x+ a0 2Zn [x] :

Seega kongruentsi (7) lahendamine on samav�a�arne v~orrandi

f (x) = 0 (9)

lahendamisega j�a�agiklassiringisZn.

Et mooduli n j�argi on olemas t�apselt n j�a�agiklassi, siis v~orrandi (9) (ja seega ka kongruentsi (7)) lahendid saame

k�atte, kui lihtsalt proovime l�abi k~oik n j�a�agiklassi. V�aikese mooduli n korral ei ole see liiga raske, kuid suure n

korral on proovimismeetod arvutuslikult �a�armiselt ebaefektiivne.

N�aide 6.1. Lahendame proovimismeetodil kongruentsi

3x4 + 2x2 � 1 � 0 (mod 5):

Proovime k~oiki j�a�agiklasse 0; 1; 2; 3; 4 mooduli 5 j�argi:

3 � 04 + 2 � 02 � 1 = 4 6= 0;

3 � 14 + 2 � 12 � 1 = 3 + 2� 1 = 4 6= 0;

3 � 24 + 2 � 22 � 1 = 3 � 1 + 2 � 4� 1 = 10 = 0;

3 � 34 + 2 � 32 � 1 = 3 � 1 + 2 � 4� 1 = 10 = 0;

3 � 44 + 2 � 42 � 1 = 3 � 1 + 2 � 1� 1 = 4 6= 0:

Seega antud kongruentsi lahendeiks on j�a�agiklassid 2 ja 3 mooduli 5 j�argi, ehk pisut teistmoodi kirjapanduna v~oime

lahendi esitada kujul x � 2 (mod 5), x � 3 (mod 5).

M�argime, et f (x0) leidmiseks v~oib kasutada ka Horneri skeemi. N�aiteks skeemi

3 0 2 0 �12 3 0 + 2 � 3 = 1 2 + 2 � 1 = 4 0 + 2 � 4 = 3 �1 + 2 � 3 = 0

abil n�aeme, et 2 on eespoolvaadeldud kongruentsi lahend.

6.2. Lineaarkongruentsid

K~oige lihtsamad kongruentsid on lineaarkongruentsid, s.o. kongruentsid kujul

ax � b (mod n); (10)

kus a 6� 0 (mod n). Osutub, et sellel kongruentsil v~oib olla �uks, mitu v~oi mitte �uhtegi lahendit.

Lause 6.2. Lineaarkongruents (10) omab lahendit parajasti siis, kui (a; n) j b. Kui (a; n) j b, siis sellel kongruentsilon (a; n) lahendit. Need on

x0; x0 + n0; x0 + 2n0; : : : ; x0 + (d� 1)n0; (11)

kus n0 = n(a;n)

ja x0 on selle kongruentsi mingi (eri)lahend.

20

Page 21: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Olgu d = (a; n) , n0 = ndja a0 = a

d. Kui x0 on lahend, siis leidub selline t�aisarv k; et b = ax0+ kn. Kuna

d jagab viimase v~orduse paremat poolt, siis ka d j b. Vastupidi, oletame, et d j b ning olgu b = db0, b0 2Z. Teoreemi

1.7 p~ohjal leiduvad sellised t�aisarvud x00 ja y00, et ax00 + ny00 = d. Korrutame v~orduse m~olemad pooled arvuga b0.

Siis a(x00b0) +n(y00b

0) = b. V~ottes x0 = x00b0 saame, et ax0 � b (mod n). Sellega on n�aidatud, et kongruents (10) on

lahenduv parajasti siis, kui d j b.Oletame n�u�ud, et d j b, s.t. leidub selline b0 2Z, et db0 = b, ning olgu x0 kongruentsi (10) mingi lahend. N�aitame,

et j�a�agiklassid (11) on kongruentsi (10) lahendid. T~oepoolest, iga k 2 f0; : : : ; d� 1g, korral

a(x0 + kn0) = ax0 + a0dkn0 � b+ a0kn � b (mod n):

N�aitame, et lahendid (11) on k~oik erinevad. Selleks oletame vastuv�aiteliselt, et x0 + in0 = x0 + jn0, 0 � i <

j � d� 1, s.t. x0 + in0 � x0 + jn0 (mod n). Siis n j (x0 + jn0)� (x0 + in0) = (j � i)n0, mis aga pole v~oimalik, sest

0 < (j � i)n0 < dn0 = n.

L~opetuseks n�aitame, et kongruentsi (10) mistahes lahend x1 on v~ordne �uhega lahendeist (11). Sellest, et ax0 � b

(mod n) ja ax1 � b (mod n), j�areldub kongruentside vastavaid pooli lahutades, et a(x1 � x0) � 0 (mod n); mis

t�ahendab, et leidub selline k 2Z, et a(x1� x0) = kn. Jagades viimase v~orduse m~olemaid pooli arvuga d saame, et

a0(x1 � x0) = kn0. Kuna j�arelduse 1.10 t~ottu (a0; n0) = 1, siis j�arelduse 1.11 p~ohjal n0 j x1 � x0, s.t. leidub selline

l 2 Z, et x1 � x0 = ln0 ehk x1 = x0 + ln0. Lause 1.6 p~ohjal leiduvad selised q; r 2Z, et l = qd + r ja 0 � r < d.

J�arelikult

x1 = x0 + (qd+ r)n0 = x0 + rn0 + qn � x0 + rn0 (mod n)

ja seega x1 on v~ordne �uhega lahendeist (11). 2

M�arkus 6.3. Kongruentsi a0x � b0 (mod n0) lahend on lause 3.9 t~ottu ka kongruentsi ax � b (mod n) lahend.

Seega kongruentsi ax � b (mod n) mingi erilahendi leidmiseks piisab leida kongruentsi a0x � b0 (mod n0) mingi

lahend.

J�areldus 6.4. Kongruents (10) on �uheselt lahenduv parajasti siis, kui (a; n) = 1.

N�aide 6.5. Lahendame kongruentsi 5x � 3 (mod 16):

Selle kongruentsi lahendamine on samav�a�arne v~orrandi 5x = 3 lahendamisega ringis Z16. Kuna (5; 16) = 1, siis

5 2 U (Z16) ja seega saame x leida korrutades selle v~orrandi m~olemaid pooli elemendiga 5�1. Et r�uhma elemendi

p�o�ordelement on �uheselt m�a�aratud, siis ka x on �uheselt m�a�aratud (sedasama v�aidab meile ka j�areldus 6.4). Leiame

5�1. Valemi (6) abil saame

5�1

= 5'(16)�1

= 57=�53�2� 5 =

�9 � 5

�2 � 5 = �32 � 5 = 9 � 5 = �3 = 13

ja seega

x = 5�1 � 3 = �3 � 3 = �9 = 7:

Kontrollime: 5 � 7 � 3 (mod 16).

6.3. Hiina j�a�agiteoreem

Selles punktis vaatleme lineaarkongruentside s�usteemide lahendamist. P~ohitulemus on j�argmine.

Teoreem 6.6 (Hiina j�a�agiteoreem). Olgu a1; : : : ; as t�aisarvud, n1; : : : ; ns paarikaupa �uhistegurita naturaalar-vud ja n = n1 : : :ns. Siis kongruentside s�usteemil8<

:x � a1 (mod n1)

: : :

x � as (mod ns)

(12)

on olemas �uhene lahend mooduli n j�argi.

Anname sellele teoreemile kaks t~oestust.

T~oestus 1. Kui n1; : : : ; ns paarikaupa �uhistegurita, siis teoreemi 4.3 t~oestuse p~ohjal kujutus f :Zn �!Zn1�: : :�Zns, f(a) = (a1; : : : ; as), kus ai on arvu a j�a�agiklass mooduli ni j�argi, on ringide isomor�sm. Vaatleme elementi

((a1)1 ; : : : ; (as)s) 2Zn1� : : :�Zns (siin (ai)i on arvu ai j�a�agiklass mooduli ni j�argi). Kujutuse f s�urjektiivsusest

j�areldub, et leidub selline a 2Z, et f(a) = ((a1)1 ; : : : ; (as)s). Teiselt poolt aga vastavalt f de�nitsioonile f(a) =

(a1; : : : ; as). Seega (ai)i = ai; i = 1; : : : ; s. See t�ahendab, et iga i korral a � ai (mod ni) ning j�arelikult x = a ongi

s�usteemi (12) lahend.

21

Page 22: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Veendume, et see lahend on �uhene mooduli n j�argi. Olgu ka b s�usteemi (12) lahend. Siis b � ai (mod ni) iga

i korral, s.t. bi = (ai)i ning f(a) = ((a1)1 ; : : : ; (as)s) =�b1; : : : ; bs

�= f(b). Kujutuse f injektiivsuse t~ottu a = b,

ehk a � b (mod n). 2

T~oestus 2. Leiame iga i = 1; : : : ; s korral

mi =n

ni=Yj 6=i

nj :

Kuna (nj ; ni) = 1, kui j 6= i, siis lemma 4.1 p~ohjal ka (mi; ni) = 1. Seega mi 2 U (Zni). Iga i = 1; : : : ; s korral

leiame elemendi mi p�o�ordelemendi ringis Zni

ki = mi�1 2 U (Zni);

s.t. sellise ki 2Z; et kimi = 1, ehk kimi � 1 (mod ni). T�ahistame

x =

sXj=1

ajkjmj :

Siis x =Ps

j=1 ajkjmj � aikimi � ai (mod ni) iga i = 1; : : : ; s korral, sest j 6= i korral ni j mj . Seega x on

s�usteemi (12) lahend.

Kui ka y on s�usteemi (12) lahend, siis iga i = 1; : : : ; s korral x � ai � y (mod ni) ning kuna n1; : : : ; ns on

paarikaupa �uhistegurita, siis lemma 4.2 p~ohjal x � y (mod n). 2

N�aide 6.7. Lahendame kongruentside s�usteemi8<:

3x � 5 (mod 7)

2x � 3 (mod 5)

x � 4 (mod 3):

Selleks lahendame esialgu iga kongruentsi eraldi. Et ringis Z7 on 3�1

= 5, siis x � 5 � 5 � 4 (mod 7). Kuna ringis

Z5 on 2�1

= 3, siis x � 3 � 3 � 4 (mod 5). Lisaks sellele x � 4 (mod 3) parajasti siis, kui x � 1 (mod 3). Seega

tuleb lahendada kongruentside s�usteem 8<:

x � 4 (mod 7)

x � 4 (mod 5)

x � 1 (mod 3):

Selle s�usteemi lahendi saame k�atte Hiina j�a�agiteoreemi abil. Selleks t�ahistame m1 = 15, m2 = 21, m3 = 35 ning

leiame, et ringis Z7 k1 = m1�1 = 1

�1= 1, ringis Z5 k2 = m2

�1 = 1�1

= 1 ja ringis Z3 k3 = m3�1 = 2

�1= 2.

Seega

x = 4 � 1 � 15 + 4 � 1 � 21 + 1 � 2 � 35 = 60 + 84 + 70 = 214

ja

x � 4 (mod 105):

N�aide 6.8. Lahendame j�argmise �ulesande, mis on p�arit Hiinast, 7. sajandist.

Kui v~otta korvist mune 2, 3, 4, 5 v~oi 6 kaupa, siis j�a�ab l~opuks j�argi vastavalt 1, 2, 3, 4 v~oi 5 muna. Kui v~otta

korvist mune 7 kaupa, siis ei j�a�a l~opuks �uhtegi muna �ule. Leidke v�ahim v~oimalik munade arv korvis.

Kui otsitav munade arv t�ahistada t�ahega x, siis saame x leidmiseks j�argmise kongruentside s�usteemi:8>>>>>><>>>>>>:

x � 1 (mod 2)

x � 2 (mod 3)

x � 3 (mod 4)

x � 4 (mod 5)

x � 5 (mod 6)

x � 0 (mod 7):

Lihtne on n�aha, et selle s�usteemi kaks esimest kongruentsi on j�arelduseks �ulej�a�anutest. Seet~ottu on see s�usteem

samav�a�arne oma alams�usteemiga 8>><>>:

x � 3 (mod 4)

x � 5 (mod 6)

x � 4 (mod 5)

x � 0 (mod 7):

22

Page 23: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Paneme t�ahele, et siin ei ole moodulid �uhistegurita ning seega ei saa lahendada nii nagu eelmises �ulesandes. Selle

�ulesande saab siiski lahendada kasutades j�argmist meetodit (lahendame n.�o. j�ark-j�argult). See seisneb selles, et iga

j�argmise kongruentsi lahendeid otsitakse vaid k~oigist eelnevatest kongruentsidest koosneva osas�usteemi lahendite

hulgast. Igal sammul tuleb siinjuures lahendada teatud lineaarkongruents. Selle lahendite puudumine toob kaasa

kogu s�usteemi mittelahenduvuse. Lineaarkongruentside lahendite olemasolu k~oigil etappidel tagab s�usteemi lahendi

olemasolu. Vastus j�a�ab mooduli j�argi, mis on antud moodulite v�ahim �uhiskordne.

Esimese kongruentsi lahendeiks on k~oik t�aisarvud kujul x = 4t + 3; t 2 Z. Leiame nende hulgas need, mis

rahuldavad ka teist kongruentsi. Asendades saame 4t + 3 � 5 (mod 6); kust 2t � 1 (mod 3) ja seega t � 2

(mod 3). Niisiis t = 3u+ 2; u 2Zja x = 12u+ 11. (Seega x � 11 (mod 12) ja edasi v~oiks p~ohim~otteliselt kasutada

Hiina j�a�agiteoreemi, kuid j�atkame siin siiski sama meetodiga.) Otsime selliste arvude hulgast neid, mis rahuldavad

ka kolmandat kongruentsi. Nende korral 12u+11 � 4 (mod 5); kust saame u � �1 (mod 5). Seega u = 5v�1; v 2Zja x = 60v � 1. Viimasesse kongruentsi asendades saame 60v � 1 � 0 (mod 7) ehk 4v � 1 (mod 7); kust v � 2

(mod 7). Seega v = 7w + 2, w 2Z; ja x = 420w+ 119. J�arelikult v�ahim v~oimalik munade arv on 119.

6.4. Kongruentsid algarvu astme j�argi

Uurime, kuidas lahendada kongruentse

f(x) � 0 (mod pk); (13)

kus f(x) on pol�unoom kujul (8), p on algarv ja k on naturaalarv. Oletame, et meil on mingil viisil (nt. proovimis-

meetodil, �uldjuhul paremat meetodit polegi) leitud kongruentsi

f(x) � 0 (mod p) (14)

k~oik lahendid. Kui x0 2 Zp on selle kongruentsi mingi lahend, siis iga t�aisarvu y korral f(x0 + py) � 0 (mod p).

Paneme t�ahele, et kongruentsi

f(x) � 0 (mod p2) (15)

iga lahend on ka kongruentsi (14) lahend (kuid vastupidine �uldjuhul ei kehti). Seet~ottu tuleks kongruentsi (15)

lahendite saamiseks eraldada kongruentsi (14) lahendite hulgast v�alja need, mis rahuldavad kongruentsi (15), s.t.

kongruentsi (14) iga lahendi x0 = fx0 + py j y 2Zg 2Zp korral tuleks leida k~oik sellised t�aisarvud y, mille korral

f(x0 + py) � 0 (mod p2). Kuna Newtoni binoomvalemi p~ohjal

f(x0 + py) = ak(x0 + py)k + ak�1(x0 + py)k�1 + : : :+ a2(x0 + py)2 + a1(x0 + py) + a0

� akxk0 + ak

�k

1

�xk�10 py + ak�1x

k�10 + ak�1

�k � 1

1

�xk�20 py + : : :+ a2x

20 + a2

�2

1

�x0py + a1x0 + a1py + a0

� (akkxk�10 + ak�1(k � 1)xk�20 + : : :+ a22x0 + a1)py + pm = f 0(x0)py + pm (mod p2);

kus f(x0) = pm, m 2Z(sest f(x0) � 0 (mod p)), siis tuleks leida lineaarkongruentsi

f 0(x0)py + pm � 0 (mod p2);

(muutuja y suhtes), mis on lause 3.9 p~ohjal samav�a�arne kongruentsiga

f 0(x0)y +m � 0 (mod p);

lahendid.

Analoogiliselt j�atkame, kuni saame k�atte kongruentsi (13) lahendid.

N�aide 6.9. Lahendame kongruentsi

4x3 + 7x2 � 7x� 10 � 0 (mod 32): (16)

Selle kongruentsi lahendamiseks lahendame k~oigep�a�alt kongruentsi

4x3 + 7x2 � 7x� 10 � 0 (mod 3)

ehk

x3 + x2 � x� 1 � 0 (mod 3):

Et j�arelduse 5.15 t~ottu mistahes x korral x3 � x (mod 3), siis viimane kongruents on samav�a�arne kongruentsiga

x2 � 1 � 0 (mod 3);

23

Page 24: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

mille lahendeiks on x1 � 1 (mod 3) ja x2 � 2 � �1 (mod 3).

Otsime kongruentsi (16) lahendit kujul x = 1 + 3y. Asendades kongruentsi (16) saame

4(1 + 3y)3 + 7(1 + 3y)2 � 7(1 + 3y) � 10 � 0 (mod 9)

ehk

4 + 4 � 3 � 3y + 7 + 7 � 2 � 3y � 7� 7 � 3y � 10 � 0 (mod 9):

Seega lahendada tuleb lineaarkongruents

21y � 6 (mod 9)

ehk

7y � 2 (mod 3);

kust saame, et y � 2 (mod 3): Seega x = 1 + 3 � 2 = 7, s.t. x � 7 (mod 9) on kongruentsi (16) lahend.

Otsime n�u�ud kongruentsi (16) lahendit kujul x = �1 + 3y. Asendades kongruentsi (16) saame

4(�1 + 3y)3 + 7(�1 + 3y)2 � 7(�1 + 3y) � 10 � 0 (mod 9)

ehk

�4 + 4 � 3 � 3y + 7� 7 � 2 � 3y + 7� 7 � 3y � 10 � 0 (mod 9):

Viimasest saame kongruentsi 0 � 0 (mod 9), mis on rahuldatud iga y korral, s.t. y � 0; 1; 2 (mod 3). Seega

kongruentsi (16) lahendeiks on veel x � 2 (mod 9), x � 5 (mod 9) ja x � 8 (mod 9).

6.5. Kongruentsid suvalise mooduli j�argi

Vaatleme kongruentsi (7) lahendamist �uldjuhul. Olgu moodul n = pk11 : : : pkss antud standardkujul. Asendame

selle kongruentsi teatava kongruentside s�usteemiga.

Lause 6.10. Kongruents

f(x) � 0 (mod p1k1 : : : ps

ks) (17)

on samav�a�arne kongruentside s�usteemiga 8<:

f(x) � 0 (mod p1k1)

: : :

f(x) � 0 (mod psks)

(18)

(s.t. neil on samad lahendid).

T~oestus. Kui f(x0) � 0 (mod pk11 : : : pkss ), siis pk11 : : : pkss j f(x0). Kuid siis ka iga i = 1; : : : ; s korral pkii j f(x),ehk f(x0) � 0 (mod pkii ). Seega kongruentsi (17) iga lahend on ka s�usteemi (18) lahend.

N�aitame vastupidist. Oletame, et x0 rahuldab s�usteemi (18), s.t. iga i = 1; : : : ; s korral pkii j f(x). Kuna iga

i 6= j korral�pkii ; p

kjj

�= 1, siis lemma 4.2 p~ohjal ka pk11 : : : pkss j f(x0), ehk f(x0) � 0 (mod pk11 : : : pkss ). 2

Oletame, et iga i = 1; : : : ; s korral on leitud kongruentsi f(x) � 0 (mod pkii ) mingi lahend xi. Siis kongruentside

s�usteemi 8<:

x � x1 (mod p1k1)

: : :

x � xs (mod psks)

(19)

iga lahend on ka s�usteemi (18) lahend. Ka vastupidi, kui x0 on s�usteemi (18) lahend, siis ta peab iga i = 1; : : : ; s

korral mooduli pkii j�argi olema kongruentne kongruentsi f(x) � 0 (mod pkii ) mingi lahendiga xi. Niisiis, kui me

oskaksime lahendada kongruentse f(x) � 0 (mod pkii ), siis s�usteemi (18) (ja seega kongruentsi (17)) k~oik lahendid

saame, kui lahendame Hiina j�a�agiteoreemi abil k~oikv~oimalikud s�usteemid (19), kus iga i = 1; : : : ; s korral xi on

kongruentsi f(x) � 0 (mod pkii ) mingi lahend. Kui ri on kongruentsi f(x) � 0 (mod pkii ) lahendite arv, siis selliseid

s�usteeme (ja seega ka kongruentsi (17)) lahendeid on r1r2 : : : rs t�ukki.

24

Page 25: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

N�aide 6.11. Lahendame kongruentsi

4x3 + 7x2 � 7x� 10 � 0 (mod 225): (20)

Kuna 225 = 32 � 52, siis taandub selle kongruentsi lahendamine kongruentside s�usteemi

4x3 + 7x2 � 7x� 10 � 0 (mod 32) (21)

4x3 + 7x2 � 7x� 10 � 0 (mod 52) (22)

lahendamisele. Esimene neist kongruentsidest on lahendatud n�aites 6.9.

Asume kongruentsi (22) lahendama. Selleks lahendame esialgu kongruentsi

4x3 + 7x2 � 7x� 10 � 0 (mod 5)

ehk

�x3 + 2x2 � 2x � 0 (mod 5):

Proovimise teel saame, et selle kongruentsi lahendeiks on x � 0 (mod 5), x � 3 (mod 5) ja x � 4 (mod 5).

Otsime kongruentsi (22) lahendit kujul x = 5y. Asendades kongruentsi (22) saame

4(5y)3 + 7(5y)2 � 7(5y) � 10 � 0 (mod 25)

ehk �10y � 10 � 0 (mod 25): Seega 2y � �2 (mod 5); s.t. y � 4 (mod 5), ning x � 20 (mod 25) on kongruentsi

(22) lahend.

Otsime kongruentsi (22) lahendit kujul x = 3 + 5y. Asendades kongruentsi (22) saame

4(3 + 5y)3 + 7(3 + 5y)2 � 7(3 + 5y) � 10 � 0 (mod 25)

ehk

4 � 33 + 4 � 3 � 32 � 5y + 7 � 32 + 7 � 2 � 3 � 5y � 7 � 3� 7 � 5y � 10 � 0 (mod 25):

Seega lahendada tuleb lineaarkongruents �10y � 10 � 0 (mod 25) ehk j�allegi y � 4 (mod 5): Seega x � 23

(mod 25) on kongruentsi (22) lahend.

Otsime kongruentsi (22) lahendit kujul x = 4 + 5y. Asendades kongruentsi (22) saame

4(4 + 5y)3 + 7(4 + 5y)2 � 7(4 + 5y) � 10 � 0 (mod 25)

ehk

4 � 43 + 4 � 3 � 42 � 5y + 7 � 42 + 7 � 2 � 4 � 5y � 7 � 4� 7 � 5y � 10 � 0 (mod 25):

Seega lahendada tuleb lineaarkongruents 5y + 5 � 0 (mod 25) ehk y � 4 (mod 5): Seega x � 24 (mod 25) on

kongruentsi (22) lahend.

Saime, et kongruentsi (21) lahendeiks on x � 2; 5; 7; 8 (mod 9) ja kongruentsi (22) lahendeiks x � 20; 23; 24

(mod 25). Seega kongruentsil (20) on 12 lahendit. Need saame, kui Hiina j�a�agiteoreemi abil lahendame 12 lineaar-

kongruentside s�usteemi. Lahendame neist �uhe:�x � 2 (mod 9)

x � �5 (mod 25):

Ringis Z25 9�1

= �11 = 14 ja ringis Z9 25�1

= 4. Seega kongruentsi (20) �uheks lahendiks on

x = 2 � 25 � 4 + (�5) � 9 � 14 = �430

ehk x � 20 (mod 225). �Ulej�a�anud lahendite saamiseks tuleb x avaldises v~otta 2 ja �5 asemel teised arvud. Nii

tehes saame lahendeiks x � 20; 23; 70; 74;95;98;124; 149;170;173; 223; 224 (mod 225).

25

Page 26: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

7. Algjuured

Meenutame, et l~opliku r�uhma j�arguks nimetatakse tema elementide arvu. Kui G on l~oplik r�uhm ja a 2 G, siis

elemendi a j�arguks nimetatakse v�ahimat astendajat k 2 N, mille korral ak = 1, kus 1 on selle r�uhma �uhikelement.

Lagrange'i teoreemi p~ohjal on l~opliku r�uhma elemendi j�ark r�uhma j�argu jagaja. R�uhma nimetatakse ts�ukliliseks,kui leidub selline element, mille astmetena avalduvad k~oik selle r�uhma elemendid. Sellist elementi nimetatakse

ts�uklilise r�uhma moodustajaks.Selles paragrahvis uurime, millal on r�uhm U (Zn) ts�ukliline, s.t. millal leidub selline element a 2 U (Zn), mille

j�ark on '(n) = jU (Zn)j, ehk millal leidub element a 2 U (Zn), mille astmetena avalduvad r�uhma U (Zn) k~oik

elemendid.

De�nitsioon 7.1. T�aisarvu a nimetatakse algjuureks mooduli n j�argi, kui a on r�uhma U (Zn) moodustaja, s.t. kui

U (Zn) =�a; a2; : : : ; a'(n)�1; a'(n) = 1

.

Samav�a�arselt v~oiks de�neerida ka nii, et a on algjuur mooduli n j�argi, kui (a; n) = 1 ja '(n) on v�ahim natu-

raalarv, mille korral a'(n) � 1 (mod n).

N�aide 7.2. Kui n = 2, siis U (Z2) =�1on ts�ukliline r�uhm. Kui n = 3, siis U (Z3) =

�1; 2=n2; 2

2oon ts�ukliline

r�uhm moodustajaga 2, seega 2 on algjuur mooduli 3 j�argi. Kui n = 4, siis U (Z4) =�1; 3=n3; 3

2oon ts�ukliline

r�uhm moodustajaga 3, seega 3 on algjuur mooduli 4 j�argi. Kui n = 5, siis U (Z5) =�1; 2; 3; 4

=n2; 2

2; 2

3; 2

4o=n

3; 32; 3

3; 3

4oon ts�ukliline r�uhm, seega 2 ja 3 on algjuured mooduli 5 j�argi. Kui n = 8, siis U (Z8) =

�1; 3; 5; 7

ja

12= 1; 3

2= 1; 5

2= 1; 7

2= 1, seega �uhegi U (Z8) elemendi j�ark pole 4 = '(8), j�arelikult U (Z8) ei saa olla ts�ukliline

r�uhm ning ei leidu �uhtegi algjuurt mooduli 8 j�argi.

Meie eesm�ark on teha kindlaks, milliste moodulite j�argi leidub algjuuri. Selleks t~oestame esialgu paar abitule-

must r�uhmade kohta.

Lemma 7.3. Olgu G r�uhm, a 2 G, olgu elemendi a j�ark m, ning olgu l 2 N. Siis al = 1 parajasti siis, kui m j l.

T~oestus. Tarvilikkus. Olgu al = 1. Lause 1.6 p~ohjal leiduvad sellised q; r 2Z, et l = qm+ r ja 0 � r < m. Siis

1 = al = aqm+r = (am)qar = 1qar = ar. Kuna m on v�ahim naturaalarv, mille korral am = 1, siis r = 0. Seega

l = qm, ehk m j l.Piisavus. Kui leidub selline k 2 N, et mk = l, siis al = (am)

k= 1. 2

Lemma 7.4. Paarisarvulise j�arguga r�uhmas leidub element, mille j�ark on kaks.

T~oestus. Olgu r�uhma G j�ark paarisarv. Kui r�uhmas G ei ole elementi, mille j�ark on kaks, s.t. �uhegi elemendi

1 6= a 2 G korral a2 6= 1 ehk a 6= a�1, siis k~oik G �uhikelemendist erinevad elemendid jagunevad l~oikumatuteks

paarideks�a; a�1

: Seega G j�ark on paaritu arv, vastuolu. J�arelikult kui G j�ark on paarisarv, siis peab leiduma

v�ahemalt �uks teist j�arku element. 2

Lemma 7.5. Paarisarvulise j�arguga ts�uklilises r�uhmas on t�apselt �uks element, mille j�ark on kaks.

T~oestus. Olgu G = hai ts�ukliline r�uhm moodustajaga a ja jGj = 2m; kus m 2 N. Siis a2m = 1 ja G =�1; a; a2; : : : ; a2m�1

. J�arelikult am 6= 1 ja (am)

2= 1, s.t elemendi am j�ark on 2. Oletame, et ka elemendi al, kus

1 � l � 2m� 1, j�ark on 2, s.t.�al�2

= a2l = 1. Siis lemma 7.3 t~ottu 2m j 2l, ehk m j l. Kuna m � l < 2m ja m j l,siis m = l ja am = al. 2

Teoreemist 5.9 j�areldub lihtsalt j�argmine v�aide.

Lemma 7.6. Mistahes naturaalarvu n > 2 korral on '(n) paarisarv.

P�o�ordume tagasi k�usimuse juurde, millal leidub mooduli n j�argi algjuuri.

Olgu n = pk11 : : : pkss arvu n > 1 standardkuju. J�arelduse 4.6 ja lause 5.6 p~ohjal kehtib r�uhmade isomor�sm

U (Zn) �= U (Zpk11) � : : :� U (Z

pkss):

Oletame, et leiduvad erinevad i; j 2 f1; : : : ; sg, nii et pi ja pj on paaritud algarvud. �Uldsust kitsendamata

eeldame, et i = 1 ja j = 2. J�arelikult lemma 7.6 p~ohjal on U (Zpk11) ja U (Z

pk22) paarisarvulist j�arku r�uhmad ning

26

Page 27: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

seega leiduvad lemma7.4 p~ohjal teist j�arku elemendid a 2 U (Zpk11

) ja b 2 U (Zpk22

). Siis ka elemendid�a; 1; 1; : : : ; 1

�,�

1; b; 1; : : : ; 1�2 U (Z

pk11)� : : :�U (Z

pkss) on teist j�arku ja seega lemma 7.5 p~ohjal r�uhm U (Zn) ei saa olla ts�ukliline.

Oletame, et n = 2kpl, kus p > 2 on algarv ja k � 2. Siis j�allegi r�uhmad U (Z2k) ja U (Zpl) on paarisarvulist j�arku,

leiduvad teist j�arku elemendid a 2 U (Z2k) ja b 2 U (Zpl) ning seega ka elemendid (a; 1); (1; b) 2 U (Z2k) � U (Zpl)

on teist j�arku, mist~ottu U (Zn) ei saa olla ts�ukliline.

L~opuks oletame, et n = 2k, kus k � 3. Siis U (Z2k) sisaldab j�alle kaks erinevat teist j�arku elementi (ja seega

ei saa olla ts�ukliline). Nendeks teist j�arku elementideks on 2k�1 � 1 ja 2k�1 + 1. T~oepoolest, kuna k � 3, siis

1 < 2k�1 � 1 < 2k ja 1 < 2k�1 + 1 < 2k, seega 2k�1 � 1 6= 1 6= 2k�1 + 1. Lisaks sellele

�2k�1 � 1

�2= 22k�2 � 2k + 1 � 1 (mod 2k);

s.t. need elemendid on teist j�arku. Ning kuna k � 3, siis 2 6� 0 (mod 2k) ning seet~ottu 2k�1 � 1 6� 2k�1 + 1

(mod 2k), ehk 2k�1� 1 6= 2k�1 + 1 .

Seega kui n ei ole kujul 2; 4; pk ega 2pk, kus p > 2 on algarv, siis mooduli n j�argi ei saa leiduda algjuuri, s.t. me

oleme t~oestanud j�argmise tulemuse.

Lause 7.7. Kui mooduli n j�argi leidub algjuuri, siis n on kujul 2; 4; pk v~oi 2pk, kus p > 2 on algarv.

N�aitame n�u�ud, et kui arvul n on eespoolmainitud kuju, siis mooduli n j�argi leidub algjuuri.

Esimese asjana peaksime n�aitama, et j�a�agiklassikorpuseZp multiplikatiivne r�uhm U (Zp) on ts�ukliline. Osutub,

et selline omadus on mitte ainult j�a�agiklassikorpustel, vaid ka k~oigil teistel l~oplikel korpustel.

Teoreem 7.8. Iga l~opliku (kommutatiivse1) korpuse multiplikatiivne r�uhm on ts�ukliline.

T~oestus. Olgu K l~oplik korpus �uhikelemendiga 1 ja nullelemendiga 0, jKj = q, ja t�ahistaguK� = Knf0g = U (K)

selle korpuse multiplikatiivset r�uhma, s.t. nullist erinevate elementide hulka korrutamise suhtes. Olgu Kd r�uhma

K� k~oigi selliste elementide hulk, mille j�ark on d. Kuna K� iga elemendi j�ark on Lagrange'i teoreemi p~ohjal arvu

q � 1 = jK�j jagaja ning elemendi j�ark on �uheselt m�a�aratud, siis K� = tdjq�1Kd. Gaussi teoreemi (teoreem 5.12)

p~ohjal Xdjq�1

'(d) = q � 1 = jK�j =Xdjq�1

jKdj: (23)

N�aitame, et iga d j q � 1 korral jKdj = '(d), s.t. et r�uhmas K� leidub t�apselt '(d) elementi, mille j�ark on d.

Oletame, et antud d j q � 1 korral Kd 6= ;, s.t. et leidub d: j�arku element a, ning t~oestame, et sellisel juhul

Kd = fak j 1 � k � d; (k; d) = 1g: (24)

Kuna a j�ark on d, siis elemendid a; a2; : : : ; ad on erinevad ning nad rahuldavad v~orrandit

xd � 1 = 0;

sest (ak)d = (ad)k = 1 iga k = 1; : : : ; d korral. Kuna d: astme pol�unoomil �ule korpuse K ei saa lause 2.8 p~ohjal olla

rohkem kui d juurt korpuses K, siis a; a2; : : : ; ad on pol�unoomi xd � 1 ainsad juured, j�arelikult iga element b 2 Kd

on v~ordne �uhega neist elementidest; olgu b = ak. Oletame vastuv�aiteliselt, et (k; d) = d0 > 1. Siis elemendi b j�ark

oleks v�aiksem kui d, sest bd

d0 =�ak� d

d0 =�ad� k

d0 = 1 ja dd0

< d. Sellega oleme t~oestanud, et Kd � fak j 1 � k �d; (k; d) = 1g. Oletame n�u�ud, et 1 � k � d, (k; d) = 1 ja elemendi ak j�ark on m � d. Siis amk =

�ak�m

= 1. Kuna

a j�ark on d, siis lemma 7.3 p~ohjal d j mk: Seega j�arelduse 1.11 p~ohjal d j m, mis koos v~orratusega m � d annab, et

m = d, s.t. ak 2 Kd. Sellega oleme t~oestanud v~orduse (24).

Niisiis iga d j q� 1 korral kas jKdj = '(d) v~oi Kd = ;. T�anu v~ordusele (23) ei ole aga viimane v~ordus v~oimalik.

Seega iga d j q � 1 korral on t�apselt '(d) elementi, mille j�ark on d. Muuhulgas, kuna q � 1 j q � 1, siis leidub

'(q � 1) elementi, mille j�ark on q � 1, s.o. leidub '(q � 1) r�uhma K� moodustajat. Kui a on mingi moodustaja,

siis �ulej�a�anud moodustajaiks on eespoolt~oestatu p~ohjal astmed ak, kus 1 � k � q � 1 ja (k; q � 1) = 1. 2

J�areldus 7.9. Kui p on algarv, siis mooduli p j�argi leidub algjuuri.

T~oestus. Teoreemi 7.8 p~ohjal leidub '(p � 1) � 1 r�uhmaZ�p = U (Zp) moodustajat. 2

J�argnevalt n�aitame, kuidas leida algjuurt mooduli p2 j�argi, kui on teada mingi algjuur mooduli p j�argi.

1Iga l~oplik korpus on Wedderburni teoreemi (vt. [11], teoreem 1.3.10) t~ottu kommutatiivne.

27

Page 28: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Teoreem 7.10. Olgu p algarv. Kui a on algjuur mooduli p j�argi, siis arvudest a ja a+ p v�ahemalt �uks on algjuurmooduli p2 j�argi.

T~oestus. Olgu a algjuur mooduli p j�argi. Siis a 2 U (Zp), s.t. p - a ning a j�ark selles r�uhmas on jU (Zp)j ='(p) = p � 1. Kuna p - a; siis ka p - a + p ja seega

�p2; a

�= 1 =

�p2; a+ p

�, mis t�ahendab, et a; a+ p 2 U (Zp2).

Tuleb n�aidata, et kas a v~oi a+ p j�ark r�uhmas U (Zp2) on��U (Zp2)

�� = '(p2) = p(p � 1). Olgu m elemendi a j�ark

r�uhmas U (Zp2). Siis am � 1 (mod p2), j�arelikult ka am � 1 (mod p), s.t. am = 1 r�uhmas U (Zp). Seega lemma 7.3

p~ohjal p� 1 j m. Lagrange'i teoreemi t~ottu aga m j p(p � 1). Seega leiduvad sellised u; v 2 N, et (p � 1)u = m ja

mv = p(p � 1). J�arelikult (p � 1)uv = p(p � 1), millest p � 1 taandamisel saame, et uv = p ehk u = p v~oi v = p

(sest p on algarv). Seega kas m = (p� 1)p v~oi m = p� 1.

Kui a on algjuur mooduli p j�argi, siis ka a+ p on algjuur mooduli p j�argi, sest ringis Zp on a = a + p. Seet~ottu

saame a+ p jaoks l�abi viia sama arutelu, mis a jaoks. See t�ahendab, et ka elemendi a+ p j�ark r�uhmas U (Zp2) on

kas (p � 1)p v~oi p � 1. Oletame, et nii a kui ka a + p j�ark r�uhmas U (Zp2) on p � 1, s.t. ap�1 � 1 (mod p2) ja

(a+ p)p�1 � 1 (mod p2). Kasutades Newtoni binoomvalemit saame siis, et

1 � (a + p)p�1 � ap�1 + (p � 1)ap�2p � 1 + (p � 1)ap�2p (mod p2);

millest saame, et (p� 1)ap�2p � 0 (mod p2). Lause 3.9 p~ohjal (p� 1)ap�2 � 0 (mod p) ehk p j (p� 1)ap�2. Kuna

p on algarv, siis (p; p � 1) = 1 ning j�arelikult p j a, vastuolu. Seega peab kas elemendi a v~oi a+ p j�ark r�uhmas

U (Zp2) olema (p� 1)p, s.t. v�ahemalt �uks arvudest a ja a + p on algjuur mooduli p2 j�argi. 2

J�areldus 7.11. Kui p on algarv, a on algjuur mooduli p j�argi, b 2 fa; a + pg ja bp�1 6� 1 (mod p2), siis b onalgjuur mooduli p2 j�argi.

N�aide 7.12. Leiame mingi algjuure mooduli 25 j�argi. Nagu eespool n�agime on �uheks algjuureks mooduli 5 j�argi

arv 2. J�arelduse 7.11 p~ohjal on algjuureks mooduli 25 j�argi see arvudest 2 ja 2 + 5, mille j�a�agiklassi j�ark r�uhmas

U (Z52) ei ole 5 � 1 = 4. Kuna 72= 49 = �1, siis 74 = �12 = 1, s.t. elemendi 7 j�ark r�uhmas U (Z52) on 4. Seega

algjuureks mooduli 25 j�argi peab olema 2.

Selleks, et minna ruudult �ule k~orgemaile p astmeile, vajame j�argmist abitulemust.

Lemma 7.13. Kui p on algarv ja 1 � k � p� 1 on naturaalarv, siis p jagab binoomkordajat�p

k

�.

T~oestus. De�nitsiooni j�argi �p

k

�=

p(p� 1) : : : (p� k + 1)

k!;

ehk�pk

�k! = p(p�1) : : : (p�k+1). Kuna p jagab selle v~orduse paremat poolt, siis peab ta jagama ka vasakut poolt.

Et aga p - k!, siis p j�p

k

�. 2

Teoreem 7.14. Olgu p > 2 algarv. Siis iga algjuur mooduli p2 j�argi on ka algjuur mooduli pk j�argi, kus k > 2.

T~oestus. Olgu a algjuur mooduli p2 j�argi. T~oestame induktsiooniga l j�argi, et

iga l 2 N korral leidub tl 2Znii, et a(p�1)pl�1

= 1 + tlpl ja p - tl: (25)

Vaatleme k~oigep�a�alt juhtu l = 1: Kuna a on algjuur mooduli p2 j�argi, siis a 2 U (Zp2) ja seega p - a. Fermat'

v�aikse teoreemi p~ohjal ap�1 � 1 (mod p). J�arelikult leidub selline t1 2Z, et ap�1 = 1 + t1p. Kui oletada, et p j t1,siis ap�1 � 1 (mod p2) ehk ap�1 = 1 r�uhmas U (Zp2), mis on vastuolus sellega, et a on algjuur mooduli p2 j�argi.

Seega p - t1.

Oletame n�u�ud, et l > 1 ja l � 1 korral leidub selline t�aisarv tl�1; et a(p�1)pl�2

= 1 + tl�1pl�1 ja p - tl�1: Siis

a(p�1)pl�1

=�a(p�1)p

l�2�p

= (1 + tl�1pl�1)p

= 1 +

�p

1

�tl�1p

l�1 +

�p

2

�t2l�1

�pl�1

�2+ : : :+

�p

p� 1

�tp�1l�1

�pl�1

�p�1+

�p

p

�tpl�1

�pl�1

�p= 1 +

�tl�1 +

�p

2

�t2l�1p

2(l�1)�l + : : :+

�p

p� 1

�tp�1l�1 p

(p�1)(l�1)�l + tpl�1p

p(l�1)�l

�pl

= 1 + tlpl;

28

Page 29: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

kus tl = tl�1 +�p

2

�t2l�1p

2(l�1)�l + : : : +�

p

p�1

�tp�1l�1 p

(p�1)(l�1)�l + tp

l�1pp(l�1)�l ja pl sulgude taha v~otmisel oleme

arvestanud, et iga m � 2 korral m(l � 1) � l = m(l � 1) � l + 1 � 1 = (m � 1)(l � 1) � 1 � 0. Kuna p > 2; siis

p(l�1)�l = (p�1)(l�1)�1 � 1 ja seega p j tpl�1pp(l�1)�l. Lisaks sellele, lemma7.13 t~ottu p jPp�1

i=2

�p

i

�til�1p

i(l�1)�l

ning seega p jPp

i=2

�p

i

�til�1p

i(l�1)�l = tl � tl�1. Kui oletada, et p j tl, siis ka p j tl�1, mis ei ole aga induktsiooni

eelduse t~ottu v~oimalik. Seega p - tl ja v�aide (25) on t~oestatud.

Olgu m elemendi a j�ark r�uhmas U (Zpk). Siis am = 1 ehk am � 1 (mod pk) ja m j��U (Zpk)�� = '(pk) =

(p� 1)pk�1. Tuleb n�aidata, et m = (p� 1)pk�1. Kuna am � 1 (mod pk), siis ka am � 1 (mod p), j�arelikult lemma

7.3 p~ohjal p � 1 j m (sest a j�ark r�uhmas U (Zp) on p � 1). Niisiis leiduvad sellised u; v 2 Z, et mu = (p � 1)pk�1

ja (p � 1)v = m ning seega (p � 1)pk�1 = (p � 1)vu. Taandades p � 1 saame, et pk�1 = vu. Seega v = pr�1, kus

1 � r � k, ning m = (p� 1)pr�1. J�arelikult

1 + trpr = a(p�1)p

r�1

= am � 1 (mod pk);

millest saame, et trpr � 0 (mod pk) ehk pk j trpr. Kuna p - tr siis pk j pr ehk k � r. Teisest k�uljest aga r � k.

Seega kokkuv~ottes r = k ja m = (p � 1)pk�1. 2

Teoreem 7.15. Kui a on algjuur mooduli pk j�argi, kus p > 2 on algarv, siis algjuureks mooduli 2pk j�argi on paarituarv arvudest a ja a+ pk.

T~oestus. Kuna pk on paaritu arv, siis �uks arvudest a ja a + pk peab olema paaritu. Oletame, et a on paaritu

(juhul kui a+pk on paaritu, saab v�aite t~oestada analoogiliselt). Kui a on algjuur mooduli pk j�argi, siis a 2 U (Zpk);

millest j�areldub, et (a; pk) = 1: Kuna a on paaritu, siis ka (a; 2) = 1 ja seega (a; 2pk) = 1; s.t. a 2 U (Z2pk). Sellest,

et a on algjuur mooduli pk j�argi, j�areldub, et elemendi a j�ark r�uhmas U (Zpk) on m =��U (Zpk)

�� = pk�1(p�1). Olgu

n elemendi a j�ark r�uhmas U (Z2pk). Siis n j��U (Z2pk)

�� = pk�1(p � 1) =��U (Zpk)�� = m, j�arelikult n � m. Teiselt

poolt aga sellest, et an � 1 (mod 2pk) j�areldub, et an � 1 (mod pk) ja seega lemma 7.3 p~ohjal m � n. Oleme

saanud, et n = m, mida oligi tarvis t~oestada. 2

Tehtu v~oime kokku v~otta j�argmise teoreemina.

Teoreem 7.16. Mooduli n j�argi leidub algjuuri parajasti siis, kui n on kujul 2, 4, pk v~oi 2pk, kus p > 2 on algarv.

Teoreemid 7.10, 7.14 ja 7.15 annavad lihtsa v~oimaluse algjuurte leidmiseks mooduli pk v~oi 2pk j�argi, kui teame

mingit algjuurt mooduli p j�argi. Algjuuri mooduli p j�argi aitab leida j�argmine lemma.

Olgu G r�uhm ning jGj = pk11 : : : pkss = n, kus p1; : : : ; ps on paarikaupa erinevad algarvud.

Lemma 7.17. Iga a 2 G korral, hai 6= G parajasti siis kui leidub selline i 2 f1; : : : ; sg, et anpi = 1.

T~oestus. Tarvilikkus. Oletame, et hai 6= G. Olgu m elemendi a j�ark. Siis m j n ning seega m = pl11 : : : plss , kus

iga i 2 f1; : : : ; sg korral 0 � li � ki. Kuna hai 6= G, siis a j�ark on v�aiksem kui n. Seega peab leiduma selline i, et

li < ki. Sellisel juhul m j npi

ja seega anpi = 1.

Piisavus. Kui anpi = 1, siis lemma 7.3 p~ohjal a j�ark on v�aiksem kui n ning j�arelikult hai 6= G. 2

J�areldus 7.18. Iga a 2 G korral, hai = G parajasti siis, kui iga i 2 f1; : : : ; sg korral anpi 6= 1.

J�areldus 7.19. Olgu p > 2 algarv. Siis a on algjuur mooduli p j�argi parajasti siis, kui arvu p � 1 iga algteguri q

korral ap�1q 6� 1 (mod p):

T~oestus. Rakendame j�areldust 7.18 juhul G = U (Zp): 2

N�aide 7.20. Olgu p = 13. Kuna p � 1 = 12 = 22 � 3, 26 = 64 � �1 6� 1 (mod 13) ja 24 = 16 � 3 6� 1 (mod 13),

siis 2 on algjuur mooduli 13 j�argi.

Teoreem 7.21. Kui mooduli n j�argi leidub algjuuri, siis on nende arv '('(n)).

T~oestus. Olgu a algjuur mooduli n j�argi. Siis U (Zn) =�1; a; a2; : : : ; a'(n)�1

. Olgu jU (Zn)j = '(n) = pk11 : : : pkss ,

kus p1; : : : ; ps on paarikaupa erinevad algarvud. N�aitame, et ak, 1 � k � '(n) � 1; on algjuur parajasti siis, kui

(k; '(n)) = 1 (sellest j�areldubki, et algjuurte arv on '('(n))). Selleks n�aitame, etak�6= U (Zn) parajasti siis, kui (k; '(n)) 6= 1:

Oletame, etak�6= U (Zn). Lemma 7.17 p~ohjal leidub siis selline pi, et

�ak�'(n)

pi = 1 r�uhmas U (Zn). Lemma 7.3

p~ohjal '(n) j k'(n)pi, s.t. leidub selline u 2 N, et '(n)u =

k'(n)

pi. J�arelikult upi = k, millest saame, et pi j k. Seega

(k; '(n)) � pi > 1. Vastupidi, oletame, et (k; '(n)) = d > 1. Siis leidub selline pi, et pi j d. J�arelikult ka pi j k.Olgu k = pik

0. Siis�ak�'(n)

pi = ak0'(n) = 1 ning lemma 7.17 p~ohjal

ak�6= U (Zn). 2

29

Page 30: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

8. L~oplikud korpused

Selles paragrahvis uurime l~oplikke korpusi. Nagu mainitud, on Wedderburni teoreemi p~ohjal k~oik l~oplikud

korpused kommutatiivsed. K~oige lihtsamaks n�aiteks l~oplikest korpustest on j�a�agiklassikorpusedZp, kuid osutub, et

on ka teisi l~oplikke korpusi.

8.1. L~oplike korpuste ehitus

Olgu K l~oplik korpus �uhikelemendiga 1 ja nullelemendiga 0. Edaspidises kasutame mistahes naturaalarvu m ja

elemendi a 2 K korral t�ahistusi

ma = a+ a+ : : :+ a| {z }m liidetavat

0a = 0 ning (�m)a = �(ma). Lihtne on n�aha, et nii de�neeritud korpuse elemendi kordsete jaoks kehtivad

j�argmised omadused:

� (8m; k 2Z)(8a 2 K)((m + k)a = ma + ka);

� (8m; k 2Z)(8a 2 K)((mk)a = m(ka));

� (8m 2Z)(8a; b2 K)(m(a + b) = ma +mb);

� (8m 2Z)(8a; b2 K)(m(ab) = (ma)b);

� (8m; k 2Z)(8a; b2 K)((ma)(kb) = (mk)(ab)).

Kuna K on l~oplik, siis (K;+) on l~oplik r�uhm ja seega peavad k~oik tema elemendid olema l~oplikku j�arku. Olgu

p �uhikelemendi 1 2 K j�ark aditiivses r�uhmas (K;+), s.t. v�ahim selline naturaalarv p, et p1 = 0: Siis �oeldakse, et

korpuse K karakteristika on p ja t�ahistatakse charK = p. De�nitsioonist j�areldub, et kui charK = p; siis iga a 2 K

korral pa = 0; sest

pa = p(1 � a) = (p1)a = 0a = 0:

Lause 8.1. L~opliku korpuse karakteristika on algarv.

T~oestus. Olgu p elemendi 1 2 K j�ark r�uhmas (K;+). N�aitame, et p on algarv. Selleks oletame vastuv�aiteliselt,

et p = kl, kus 1 < k; l < p. Siis k1 6= 0 ja l1 6= 0, kuid (k1) � (l1) = (kl)(1 � 1) = (kl)1 = p1 = 0. Korrutades seda

v~ordust elemendiga (k1)�1 saame vastuolu l1 = 0. Seega p on algarv. 2

De�nitsioon 8.2. Kui korpus K on korpuse L alamkorpus, siis �oeldakse, et korpus L on korpuse K laiend.

Lause 8.3. Korpuse iga laiendi karakteristika on v~ordne selle korpuse karakteristikaga.

T~oestus. Olgu L korpuse K laiend ja charK = p. Siis K kui korpuse L alamkorpus peab sisaldama korpuse L

�uhikelemendi 1, mis on seega ka K �uhikelemendiks. Kuna elemendi 1 j�ark r�uhmas (K;+) on p, siis ka tema j�ark

r�uhmas (L;+) on p ja seega charL = p. 2

Teoreem 8.4. L~opliku korpuse elementide arv on algarvu aste.

T~oestus. Olgu K l~oplik korpus, mille karakteristika on p. Vaatleme hulka

P = f1;1+ 1;1+ 1+ 1; : : : ; (p� 1)1; p1 = 0g = fm1 j m 2Zg � K:

Kuna mistahes k; l 2 f1; : : : ; pg korral k1 + l1 = (k + l)1 2 P , �(k1) = (p � k)1 2 P; (k1) � (l1) = (kl)1 2 P ja

kui k 6= p, siis (k1)�1

= u1 2 P , kus ku � 1 (mod p) (ehk u = k�1

korpuses Zp), siis P on korpuse K alamkorpus.

Korpus P on isomorfne korpusega Zp, kusjuures isomor�smi realiseerib kujutus f : P �!Zp,

f(k1) = k:

Korpust K v~oib vaadelda (l~opliku) vektorruumina �ule korpuse P : liitmine on korpuse K liitmine ning vektori

a 2 K ja skalaari k1 2 P korrutise de�neerime v~ordusega

(k1)a = ka:

Selles, et t~oesti k~oik vektorruumi aksioomid on t�aidetud, pole raske veenduda.

On h�asti teada, et igas l~oplikum~o~otmelises vektorruumis on olemas baas ([1], teoreem 3.2.3). Olgu e1; : : : ; enbaas vektorruumis K �ule korpuse P . Siis iga a 2 K esitub �uheselt lineaarkombinatsioonina a = �1e1 + : : :+�nen,

kus �1; : : : ; �n 2 P . Selliseid lineaarkombinatsioone on pn t�ukki. Seega jKj = pn: 2

Selle teoreemi t~oestuse k�aigus n�aitasime, et kehtib j�argmine v�aide.

30

Page 31: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

J�areldus 8.5. Kui korpuse K karakteristika on p, siis see korpus sisaldab j�a�agiklassikorpusega Zp isomorfse alam-korpuse.

Edasises l�aheb meil vaja j�argmisi abitulemusi.

Lemma 8.6. Kui korpuse K karakteristika on p, siis iga a; b 2 K ja n 2 N korral

(a+ b)pn

= apn

+ bpn

:

T~oestus. T~oestame v�aite induktsiooniga n j�argi. Olgu n = 1. Kuna K on kommutatiivne, siis (a+ b)p=Pp

i=0

�pi

�ap�ibi. Lemma 7.13 p~ohjal mistahes i, 1 � i � p � 1, korral p j

�pi

�, s.t. leidub ki 2 N nii, et kip =

�pi

�.

J�arelikult iga i, 1 � i � p� 1, korral�p

i

�ap�ibi = (kip)(a

p�ibi) = ki(p(ap�ibi)) = ki0 = 0;

seega (a+ b)p = ap + bp; s.t. kehtib induktsiooni alus.

Oletame n�u�ud, et (a + b)pk

= apk

+ bpk

. Siis kasutades �asjat~oestatut saame

(a + b)pk+1

=�(a+ b)p

k�p

=�ap

k

+ bpk�p

=�ap

k�p

+�bp

k�p

= apk+1

+ bpk+1

:

2

J�argmise lemma �uheks erijuhuks on Fermat' v�aike teoreem.

Lemma 8.7. Kui K on l~oplik korpus ning jKj = q, siis iga a 2 K� = K n f0g korral aq�1 = 1.

T~oestus. Olgu m elemendi a j�ark korpuse K multiplikatiivses r�uhmas K�. Siis m j q�1 = jK�j. Olgu mk = q�1.

Siis aq�1 = amk = (am)k= 1. 2

Teoreemi 7.8 p~ohjal on l~opliku korpuse multiplikatiivne r�uhm ts�ukliline. Selle r�uhma moodustajaid nimetatakse

korpuse primitiivseteks elementideks. (N�aiteks korpuse Zp primitiivsed elemendid on algjuured mooduli p j�argi.)

Olgu L korpuse K laiend, kusjuures jKj = q ja jLj = qm; m 2 N. Kui b 2 L; siis elemente

b; bq; bq2

; : : : ; bqm�1

nimetatakse elemendi b kaaselementideks korpuse K suhtes.

Lause 8.8. Elemendi b 2 L� kaaselementidel qm-elemendilise korpuse L q-elemendilise alamkorpuse K suhtes onsama j�ark r�uhmas L�.

T~oestus. Olgu b; bq; bq2

; : : : ; bqm�1

elemendi b 2 L� kaaselemendid alamkorpuse K suhtes. Olgu a korpuse L

primitiivne element. Siis leidub selline k, et b = ak. Saab t~oestada, et kuiG on s. j�arku ts�ukliline r�uhmmoodustajaga

g, siis elemendi gk j�ark on s(k;s)

. Kuna iga l 2 f0; : : : ;m � 1g korral (ql; qm � 1) = 1; siis elemendi bql

= akql

j�ark

on qm�1(kql;qm�1)

= qm�1(k;qm�1)

ja seega ei s~oltu l-st. 2

J�areldus 8.9. Kui a on korpuse L primitiivne element, siis tema kaaselemendid mistahes alamkorpuse suhtes onsamuti primitiivsed.

Olgu K kommutatiivne korpus ja vaatleme pol�unoomide ringi K[x]. Kui p(x) 2 K[x] on mingi pol�unoom �ule

korpuse K, siis selle pol�unoomi poolt tekitatud p�a�aideaali t�ahistame hp(x)i. Seega

hp(x)i = fp(x)h(x) j h(x) 2 K[x]g

(hp(x)i koosneb k~oigist pol�unoomidest ringis K[x], mis jaguvad pol�unoomiga p(x)). K~orvalklass esindajaga f(x) 2K[x] ideaali hp(x)i j�argi on hulk

[f(x)] = f(x) + hp(x)i = ff(x) + p(x)h(x) j h(x) 2 K[x]g:

Muuhulgas [0] = hp(x)i = [p(x)]. Tihti k~orvalklassid samastatakse nende esindajatega ja kirjutatakse [f(x)] asemel

lihtsalt f(x). Saab n�aidata, et

[f(x)] = [g(x)]() f(x) � g(x) 2 hp(x)i () p(x) j f(x) � g(x): (26)

31

Page 32: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Kui k~orvalklasside hulgal de�neerida tehted esindajate abil, s.t.

[f(x)] + [g(x)] = [f(x) + g(x)];

[f(x)] � [g(x)] = [f(x)g(x)];

saame ringi, mida nimetatakse ringiK[x] faktorringiks ideaali hp(x)i j�argi (vt. [1], lk. 169) ja t�ahistatakseK[x]=hp(x)i =f[f(x)] j f(x) 2 K[x]g.

Mittekonstantset pol�unoomi p(x) nimetatakse taandumatuks, kui ta ei esitu mittekonstantsete pol�unoomide

korrutisena, s.t. kui v~ordusest p(x) = f(x)g(x) j�areldub, et kas pol�unoom f(x) on konstantne v~oi g(x) on konstantne.

J�argmised kaks v�aidet on t~oestatud raamatus [1], lk 217{219.

Lause 8.10. Olgu K kommutatiivne korpus ja p(x) 2 K[x] taandumatu pol�unoom, mille aste d � 2. Siis faktorringL = K[x]=hp(x)i on korpus, mis sisaldab korpusega K isomorfset alamkorpust ning milles pol�unoomil p(x) onolemas juur. Seejuures kui jKj = pm; siis jLj = pmd.

Olgu

L = K[x]=hp(x)i = f[f(x)] j f(x) 2 K[x]g

ringi K[x] faktorring ideaali hp(x)i j�argi. Meenutame, et elemendi [0] 6= [f(x)] 2 L p�o�oratavus j�areldub sellest, et

p(x) ei jaga pol�unoomi f(x) ja p(x) on taandumatu (seega (p(x); f(x)) = 1), korpusega K isomorfseks alamkorpu-

seks korpuses L on konstantsete pol�unoomide k~orvalklasside hulk K0 = f[k] j k 2 Kg ning pol�unoomi p(x) �uheks

juureks korpuses L on lineaarpol�unoomi x k~orvalklass [x] (s.t. p([x]) = [0]).

N�aitame veel, et korpuses L on pmd elementi. Selleks t~oestame, et

K[x]=hp(x)i = f[f(x)] j f(x) 2 K[x]; deg f(x) < dg:

N�aitame, et f[f(x)] j f(x) 2 K[x]g � f[f(x)] j f(x) 2 K[x]; deg f(x) < dg: V~ottes g(x) 2 K[x] v~oime selle

pol�unoomi jagada j�a�agiga pol�unoomiga p(x), s.t. leida q(x); r(x) 2 K[x], nii et

g(x) = p(x)q(x) + r(x) ja deg r(x) < deg p(x) = d:

J�arelikult [g(x)] = [p(x)][q(x)] + [r(x)] = [0][q(x)] + [r(x)] = [r(x)] 2 f[f(x)] j f(x) 2 K[x]; degf(x) < dg:Vastupidine sisalduvus on ilmne. Seega iga k~orvalklassi esindajaks saab valida sellise pol�unoomi, mille aste on

v�aiksem kui d:

L = f[kd�1xd�1 + : : :+ k1x+ k0] j k0; : : : ; kd�1 2 Kg: (27)

Erinevaid selliseid pol�unoome on jKjd t�ukki ning erinevatele sellistele pol�unoomidele vastavad erinevad k~orvalklas-

sid, sest kui f(x); g(x) 2 K[x], f(x) 6= g(x); deg f(x) < d ja deg g < d; siis f(x) � g(x) 6= 0; deg(f(x) � g(x)) < d;

mist~ottu p(x) ei jaga pol�unoomi f(x) � g(x) ja seega (26) p~ohjal [f(x)] 6= [g(x)]. Sellega oleme t~oestanud, et

jLj = pmd.

Teoreem 8.11. Olgu f(x) 2 K [x] pol�unoom kordajatega kommutatiivsest korpusest K ning olgu f(x) aste n � 1.Siis leidub korpuse K selline laiend L, milles pol�unoomil f(x) on n juurt.

Kui need juured on a1; : : : ; an 2 L; siis f(x) lahutub lineaartegurite korrutiseks �ule korpuse L:

f(x) = b(x� a1) : : : (x� an); kus b 2 K on xn kordaja pol�unoomis f(x).

De�nitsioon 8.12. Korpuse K laiendit L nimetatakse pol�unoomi f(x) 2 K[x] lahutuskorpuseks, kui f(x) lahutublineaartegurite korrutiseks �ule L,

f(x) = b(x� a1) : : : (x� an);

kus a1; : : : ; an 2 L; ning L on korpuse K v�ahim laiend, mis sisaldab elemendid a1; : : : ; an. Kui K on l~oplik, siis ka

f(x) lahutuskorpus L on l~oplik.

Teoreem 8.11 �utleb, et igal mittekonstantsel pol�unoomil �ule kommutatiivse korpuse on lahutuskorpus olemas.

Veelgi enam, kehtib j�argmine teoreem, mida me siinkohla ei t~oesta (vt. [12], lk. 343{350).

Teoreem 8.13. Pol�unoomi lahutuskorpus on isomor�smi t�apsuseni �uheselt m�a�aratud.

Teoreem 8.4 v�aitis, et l~opliku korpuse elementide arv on algarvu aste. J�argnevalt veendume, et kehtib ka selle

teoreemi p�o�ordteoreem.

Teoreem 8.14. Iga algarvu p ja naturaalarvu n korral leidub korpus, milles on pn elementi. See korpus on iso-mor�smi t�apsuseni �uheselt m�a�aratud.

32

Page 33: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Olgu q = pn. Vaatleme pol�unoomi xq � x 2Zp [x]. Olgu L pol�unoomi xq � x lahutuskorpus ning olgu

xq � x = (x� a1) : : : (x� aq);

kus a1; : : : ; aq 2 L. Kuna Zp � L on alamkorpus, siis korpuse L karakteristika on p, s.t. p1 = 0 ja seega ka q1 = 0.

J�arelikult (xq � x)0 = q1xq�1 � 1 = �1 2 L [x] ning seega pol�unoomi xq � x ja tema tuletise suurim �uhistegur

ringis L[x] on

((xq � x); (xq � x)0) = ((xq � x);�1) = 1:

N�aitame, et sellest j�areldub, et pol�unoomil xq � x ei ole kordseid juuri. Oletame vastuv�aiteliselt, et a 2 L on

pol�unoomi xq � x kordne juur, s.t. xq � x = (x � a)kg(x), kus k � 2 ja g(x) 2 L [x]. Siis korrutise tuletise reegli

p~ohjal

(xq � x)0 = k(x� a)k�1g(x) + (x� a)kg0(x) = (x� a)�k(x� a)k�2g(x) + (x� a)k�1g0(x)

�:

Seega (x � a) j ((xq � x); (xq � x)0) = 1 ringis L[x], vastuolu. J�arelikult t~oesti pol�unoomil xq � x pole kordseid

juuri, s.t. elemendid a1; : : : ; aq on erinevad.

Vaatleme q-elemendilist alamhulka

K = fa1; : : : ; aqg = fa 2 L j aq = ag � L:

N�aitame, et K on korpuse L alamkorpus. Selleks n�aitame, et K on kinnine tehete suhtes. Olgu a; b 2 K, s.t. aq = a

ja bq = b. Lemma 8.6 p~ohjal

(a+ b)q= (a+ b)p

n

= apn

+ bpn

= aq + bq = a+ b;

s.t. a + b 2 K. Kui p = 2; siis a+ a = 0 ehk a = �a: Kui aga p > 2; siis

(�a)q = ((�1)a)q = (�1)q aq = (�1) a = �a;

s.t. �a 2 K: Korrutamise kommutatiivsuse t~ottu ka

(ab)q= aqbq = ab;

s.t. ab 2 K. Olgu a 6= 0. Siis

(a�1)q = (aq)�1 = a�1;

s.t. a�1 2 K. Seega K on alamkorpus.

Kuna L on v�ahim korpus, mis sisaldab Zp ja elemendid a1; : : : ; aq; siis L = K, j�arelikult jLj = jKj = q.�Uhesuse n�aitamiseks paneme t�ahele, et mistahes q-elemendiline korpuse L0 korral on lemma 8.7 t~ottu k~oik

tema elemendid pol�unoomi xq � x 2 Zp[x] juured. Kuna sellel pol�unoomil ei saa olla �ule q juure, siis on L selle

pol�unoomi lahutuskorpus. Kuna pol�unoomi mistahes kaks lahutuskorpust on isomorfsed, siis on ka korpus L0

isomorfne korpusega L. 2

Korpust, milles on q = pn elementi, t�ahistatakse tihti kas Fq v~oi GF(q) (GF=Galois �eld). Sellise korpuse konst-rueerimiseks v~oime kasutada lauset 8.10. V~otame n�aiteks korpuseZp, leiame mingin: astme taandumatu pol�unoomi

�ule Zp ning moodustame faktorringi Zp[x]=hp(x)i. Tulemus on pn-elemendiline korpus, mis t�anu teoreemile 8.14

ongi Fq .

8.2. Aritmeetika l~oplikes korpustes

L~opliku korpuse elementide esitamiseks on mitmeid v~oimalusi. �Uks viis on kasutada faktorringi Fq [x]=hp(x)i,kus p(x) on taandumatu pol�unoom �ule Fq . Teine v~oimalus on kasutada fakti, et r�uhm F�q on ts�ukliline ja seega tema

elemendid on esitatavad moodustaja (primitiivse elemendi) astmetena. On selge, et liita on lihtsam elemente, mis

on esitatud pol�unoomidena ning korrutada on lihtsam r�uhma moodustaja astmeid. Osutub, et neid kahte viisi saab

omavahel kombineerida, mis annab v~oimaluse aritmeetiliste tehete efektiivseks sooritamiseks l~oplikus korpuses.

N�aide 8.15. Vaatleme l~oplikku korpust F16 kui korpuse F2 =Z2 = f0; 1g (0 ja 1 asemel kirjutame 0 ja1) laiendit.

N�aitame, et pol�unoom p(x) = x4 + x + 1 on taandumatu �ule F2. Selleks paneme t�ahele, et kui p(x) oleks

taanduv, siis ta peaks omama kas lineaar- v~oi ruuttegurit. Kuna p(0) 6= 0 ja p(1) 6= 0, siis pol�unoomil p(x) pole

lineaartegureid. Veendumaks, et pol�unoom p(x) ei jagu �uhegi ruutpol�unoomiga, m�argime, et �ule F2 on t�apselt neli

erinevat ruutpol�unoomi, need on

x2; x2 + 1; x2 + x; x2+ x+ 1;

ning vahetu kontroll n�aitab, et neid pol�unoome omavahel korrutades me ei saa pol�unoomi p(x).

33

Page 34: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Kuna pol�unoomi p(x) aste on 4, siis lause 8.10 p~ohjal

F2[x]=hx4+ x+ 1i = F16:

T�ahistame a = [x] ning samastame k~orvlaklassid [0] ja [1] esindajatega 0 ja 1. Kui vaatleme pol�unoomile p(x)

vastavat pol�unoomi ~p(y) = y4+y+1 2 F16[y], siis a on pol�unoomi ~p(y) juur, sest ~p(a) = a4+a+1 = [x]4+[x]+[1] =

[x4 + x+ 1] = [0]. T�anu v~ordusele (27) v~oib korpuse F16 elemente esitada kui �ulimalt kolmanda astme pol�unoome

a suhtes:konstantsed 0; 1;

lineaarsed a; a+ 1;

ruutpol�unoomid a2; a2 + 1; a2 + a; a2 + a + 1

kuuppol�unoomid a3; a3 + 1; a3 + a; a3 + a2; a3 + a+ 1;

a3 + a2 + 1; a3 + a2 + a; a3 + a2 + a+ 1:

Sellisel kujul elementide liitmine on lihtne, sest see on lihtsalt pol�unoomide liitmine. Ent korrutamine n~ouab taan-

damist \mooduli p(x) j�argi", s.o. j�a�agiga jagamist pol�unoomigax4+x+1; kuid v~oib kasutada ka seost a4+a+1 = 0

ehk a4 = a+ 1. N�aiteks

a15 = (a5)3 = (a � a4)3 = (a � (a+ 1))3 = a3(a + 1)3 = a3 � (a3 + a2 + a + 1)

= a6 + a5 + a4 + a3 = (a3 + a2) + (a2 + a) + (a + 1) + a3 = 1;

Kuna a 6= 0; siis a 2 F�16, ning kuna a3 6= 1 ja a5 = a2+a 6= 1, siis j�arelduse 7.18 p~ohjal on a r�uhma F�16 moodustaja.

Seega

F16 = f0; 1; a; : : : ; a14g:

Sellisel viisil esitatud elementide korrutamine on lihtne, kuid liitmine on t�ulikas.

Need kaks esitust saab omavahel siduda, kui arvutada v�alja tabel, mis n�aitab, kuidas element ak esitub �ulimalt

kolmanda astme pol�unoomina a suhtes. Kasutades seost a4 = 1 + a saame

a4 = a+ 1;

a5 = a � a4 = a(a + 1) = a2 + a;

a6 = a � a5 = a3 + a2;

a7 = a � a6 = a4 + a3 = a3 + a+ 1

ja nii edasi. Tulemused v~otame kokku allj�argneva tabelina, kus elemendi ak asemel kirjutame lihtsalt k ning

pol�unoomi a3a3 + a2a

2 + a1a+ a0 asemel kirjutame a3a2a1a0:

0 0001

1 0010

2 0100

3 1000

4 0011

5 0110

6 1100

7 1011

8 0101

9 1010

10 0111

11 1110

12 1111

13 1101

14 1001

Selle tabeli ning seose a15 = 1 abil v~oime n�u�ud n�aiteks arvutada

(a8 + a4 + 1)(a3 + a) = (0101 + 0011+ 0001)(1000+ 0010) = (0111)(1010) = a10 � a9 = a19 = a4 = a+ 1:

Seega arvutamiseks (liitmiseks ja korrutamiseks) l~oplikus korpuses on kasulik teada temamultiplikatiivse r�uhma

moodustajat koos mingi taandumatu pol�unoomiga, mille juureks ta on. �Uldjuhul pole taandumatu pol�unoomi

leidmine lihtne. Siiski on paljude konkreetsete korpuste jaoks leitud taandumatud pol�unoomid ja tabelid (vt. nt.

[13]).

34

Page 35: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

8.3. Juurimine l~oplikes korpustes

De�nitsioon 8.16. Olgu K (suvaline) korpus ja b 2 K. Elementi a 2 K nimetatakse n: astme juureks elemendist

b, kui an = b: n: astme juurt korpuse K �uhikelemendist 1 nimetatakse n: astme �uhejuureks .

Lause 8.17. Kommutatiivse korpuse K k~oigi n. astme �uhejuurte hulk Hn on r�uhma K� alamr�uhm.

T~oestus. Olgu

Hn = fa 2 K� j an = 1g

ning olgu a1; a2 2 Hn, s.t. an1 = 1 ja an2 = 1. Siis ka (a1a2)

n = an1an2 = 1. Kui a 2 Hn, s.t. a

n = 1, siis ka�a�1

�n= (an)

�1= 1

�1 = 1. Seega Hn on r�uhma K� alamr�uhm. 2

Kuna n: astme �uhejuured on pol�unoomi xn � 1 2 K[x] juured, siis lause 2.8 t~ottu ei saa neid olla rohkem kui

n t�ukki. On tuntud fakt, et kompleksarvude korpuses C on n n: astme �uhejuurt ja �uhejuurte r�uhm on ts�ukliline,

kuid iga korpuse korral see nii ei ole.

De�nitsioon 8.18. Kui n: astme �uhejuuri korpuses K on n t�ukki ning k~oik nad on esitatavad n: astme �uhejuure �

astmetena (s.t. kui Hn on n: j�arku r�uhm ja � on r�uhma Hn moodustaja), siis �uhejuurt � nimetatakse primitiivseksn: astme �uhejuureks.

Teoreem 8.19. Olgu n � 2 naturaalarv ja a korpuse Fq primitiivne element, s.t. F�q =�a; a2; : : : ; aq�2; aq�1 = 1

.

Siis

1. iga k 2 f1; : : : ; q� 1g korral, ak on n. astme �uhejuur parajasti siis, kui q � 1 j kn;

2. n: astme �uhejuuri on (n; q � 1) t�ukki;

3. korpuses Fq leidub primitiivne n: astme �uhejuur parajasti siis, kui n j q � 1;

4. elemente, mis omavad n: astme juurt, on q�1(n;q�1)

t�ukki.

T~oestus. 1. Olgu ak n: astme �uhejuur. Siis akn = 1, ning kuna elemendi a j�ark r�uhmasK� on q�1, siis lemma 7.3

p~ohjal q� 1 j kn. Vastupidi, oletame, et leidub t�aisarv u, nii et (q � 1)u = kn. Kuna a 2 K�, siis lemma 8.7 p~ohjal�ak�n

= a(q�1)u =�aq�1

�u= 1, s.t. ak on n: astme �uhejuur.

2. T�ahistame d = (q � 1; n). Siis leiduvad sellised m;n0 2 N, et q � 1 = md ja n = n0d, kusjuures (m;n0) = 1.

J�arelikult iga k 2 f1; : : : ; q � 1g korral, q � 1 j kn (s.t. md j kn0d) parajasti siis, kui m j k. Selliseid astendajaid

k 2 f1; : : : ; q�1g, midam jagab, on d t�ukki: m; 2m; : : : ; dm = q�1. Seega on olemas t�apselt d n: astme �uhejuurt,

Hn = fam; a2m; : : : ; a(d�1)m; adm = 1g = hami;

ning k~oik �uhejuured avalduvad �uhejuure am astmetena.

3. Osa 2 p~ohjal on Hn d: j�arku ts�ukliline r�uhm moodustajaga am. On selge, et primitiivne �uhejuur leidub

parajasti siis, kui (n; q� 1) = d = n, mis on samav�a�arne sellega, et n j q� 1. Primitiivseks n: astme �uhejuureks on

sel juhul am.

4. Vaatleme k~orvalklasse alamr�uhma Hn j�argi, s.t hulki

cHn = fcb j b 2 Hng = fcaim j i 2 f1; : : : ; dgg;

c 2 K�. Need k~orvalklassid ei l~oiku ning k~oigi k~orvalklasside v~oimsused on v~ordsed, s.t. iga c 2 K� korral

jcHnj = jHnj ([1], lk. 155-156). K~orvalklasside arv on seegajK�

j

jHnj= q�1

d= m. N�aitame, et elemendid kuulu-

vad samasse k~orvalklassi parajasti siis, kui nende n: astmed on v~ordsed. Olgu cb 2 cHn; b 2 Hn. Siis (cb)n =

cnbn = cn1 = cn, seega k~orvalklassi cHn k~oigi elementide n: astmed on v~ordsed k~orvalklassi esindaja c n: astmega

(s.t. k~oik k~orvalklassi cHn elemendid on n: astme juurteks elemendist cn). Vastupidi, oletame, et cn1 = cn2 . Siis�c�12 c1

�n=�c�12

�ncn1 = (cn2 )

�1cn1 = 1, seega c�12 c1 2 Hn. J�arelikult c1 = c2c

�12 c1 2 c2Hn. Seega c1Hn � c2Hn.

Analoogiliselt c2Hn � c1Hn ning kokkuv~ottes c1Hn = c2Hn. (Seega erinevatesse k~orvalklassidesse kuuluvad ele-

mendid on erinevate elementide n: astme juured.) 2

J�areldus 8.20. Kui (n; q � 1) = 1, siis 1 on ainus n: astme �uhejuur korpuses Fq .

J�areldus 8.21. Element �1 2 Fq , kus q on paaritu arv, omab ruutjuurt korpuses Fq parajasti siis, kui q � 1

(mod 4).

35

Page 36: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. N�aitame, et ruutjuured elemendist �1 on t�apselt 4: astme primitiivsed �uhejuured. Olgu � ruutjuur

elemendist �1, s.t. �2 = �1. Siis �; �2 = �1; �3 = ��; �4 = 1 on neli erinevat 4: astme �uhejuurt ning seega �

on primitiivne 4: astme �uhejuur. Vastupidi, olgu � primitiivne 4: astme �uhejuur. Siis �4 = 1, j�arelikult �4 � 1 =

(�2+1)(�2�1) = 0. Kuna � on primitiivne 4: astme �uhejuur, siis ei ole v~oimalik, et �2 = 1, sest siis me saaksime �

astmetena k�atte vaid kaks 4: astme �uhejuurt (� ise ja 1). Seega, kuna korpus ei sisalda nullitegureid, peab �2+1 = 0,

ehk �2 = �1. Sellega oleme n�aidanud, et ruutjuured elemendist �1 on parajasti 4: astme primitiivsed �uhejuured.

Teoreemi 8.19 p~ohjal leidub korpuses K primitiivseid 4: astme �uhejuuri parajasti siis, kui 4 j q � 1 ehk q � 1

(mod 4). 2

M�arkus 8.22. Kui q = 2l, siis 1 = �1 ja seega �1 omab ruutjuurt.

N�aide 8.23. Korpuses Z13 on ruutjuurteks elemendist �1 elemendid 5 ja 8. Korpuses Z7 aga elemendil �1 ruut-

juurt ei ole, sest 7 � 3 (mod 4).

N�aide 8.24. Vaatleme korpust F16 n�aitest 8.15. Kuna (2; 15) = 1, siis 1 on ainus 2. astme �uhejuur korpuses F16.

Kuna (3; 15) = 3; siis kolmanda astme �uhejuuri korpuses F16 on 3 t�ukki, need on a5; a10 ja a15 = 1 ehk a2 + a,

a2 + a + 1 ja 1.

36

Page 37: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

9. Ruutj�a�agid

Olgu p > 2 algarv. Selles paragrahvis huvitab meid, millistel j�a�agiklassikorpuse Zp elementidel on olemas

ruutjuur, s.t millised korpuse Zp elemendid on mingi teise elemendi ruudud. Kuna (2; p� 1) = 2, siis teoreemi 8.19

p~ohjal on ruutjuur olemas p�12

nullist erineval elemendil, s.o. t�apselt pooltel Z�p elementidel. Oletame, et mingil

elemendil a 2 Z�p on olemas ruutjuur, s.t. leidub selline b 2 Z�p, et b2= a. Siis ka �b on elemendi a ruutjuur,

sest �b2 = b2= a: Kui oletada, et �b = b, siis 2b = 0, millest p > 2 t~ottu j�areldub, et b = 0, mis aga pole

v~oimalik. Seega b ja �b on erinevad elemendi a ruutjuured. N�u�ud teise astme pol�unoomil x2 � a �ule korpuse Zp

on lause 2.8 p~ohjal �ulimalt 2 juurt, s.t. elemendil a teisi ruutjuuri pole. Seega, kui elemendil a leidub ruutjuur,

siis on neid ruutjuuri t�apselt kaks t�ukki ja nad on teineteise vastandelemendid. K~oik ruutjuurt omavad elemendid

r�uhmasZ�p saab leida, kui arvutada hulgan1; 2; : : : ; p�1

2

ok~oigi elementide ruudud (sest �ulej�a�anud j�a�agiklassid on

sellesse hulka kuuluvate j�a�agiklasside vastandelemendid). Kui aga tahame teada, kas mingil konkreetsel elemendil

on olemas ruutjuur ning p on suur, siis on selline l�ahenemine liiga ebaotstarbekas. Osutub, et leidub palju paremaid

viise.

De�nitsioon 9.1. Olgu p > 2 algarv ja a selline t�aisarv, et p - a. T�aisarvu a nimetatakse ruutj�a�agiks (mitte-ruutj�a�agiks) mooduli p j�argi, kui element a omab (ei oma) ruutjuurt korpuses Zp.

Niisiis a on ruutj�a�ak mooduli p j�argi, kui p - a ja ruutkongruents

x2 � a (mod p)

on lahenduv. Eelneva p~ohjal peab mooduli p j�argi olema p�12

ruutj�a�aki jap�12

mitteruutj�a�aki.

N�aide 9.2. Korpuses Z11 on ruutjuur olemas elementidel 1 = 12= 10

2, 4 = 2

2= 9

2, 9 = 3

2= 8

2, 5 = 4

2= 7

2ja

3 = 52= 6

2. Seega ruutj�a�agid mooduli 11 j�argi on 1; 3; 4; 5; 9 ning mitteruutj�a�agid on 2; 6; 7; 8; 10.

De�nitsioon 9.3. Olgu a t�aisarv ja p > 2 algarv. Legendre'i s�umbol�ap

�de�neeritakse j�argmiselt

�a

p

�=

8<:

0; kui p j a;1; kui a on ruutj�a�ak mooduli p j�argi;

�1; kui a on mitteruutj�a�ak mooduli p j�argi.

(Seda s�umbolit loetakse \a p suhtes".)

Seega eelmises n�aites saadud tulemuse v~oib Legendre'i s�umboli abil kirja panna j�argmiselt:�1

11

�=

�3

11

�=

�4

11

�=

�5

11

�=

�9

11

�= 1;�

2

11

�=

�6

11

�=

�7

11

�=

�8

11

�=

�10

11

�= �1:

Olgu Z�p =�c; c2; : : : ; cp�1 = 1

: Kui k on paarisarv, siis elemendi ck ruutjuureks on c

k2 : Et t�apselt pooled

arvudest 1; : : : ; p� 1 on paarisarvud ja eelneva p~ohjal ruutjuurt omab samuti t�apseltp�12

elementi, siis saame, et

ruutjuurt omavad parajasti need elemendid ck, kus k on paaris.

Lemma 9.4. Kui c on algjuur mooduli p j�argi, siis iga k 2 N korral�ck

p

�= (�1)k:

Lause 9.5 (Euleri kriteerium). Iga t�aisarvu a ja algarvu p > 2 korral�a

p

�� a

p�12 (mod p):

T~oestus. Kui p j a, siis�ap

�= 0 � a

p�12 (mod p). Oletame, et p - a ja a = ck, kusZ�p =

�c; c2; : : : ; cp�1 = 1

: Siis�

cp�12

�2= cp�1 � 1 (mod p). J�arelikult c

p�12 on pol�unoomi x2 � 1 2Zp[x] juur ning seega kas c

p�12 � 1 (mod p)

37

Page 38: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

v~oi cp�12 � �1 (mod p), sest teisi juuri kui 1 ja �1 sellel pol�unoomil pole. Kuna c on r�uhma Z�p moodustaja, siis

esimene v~oimalus langeb �ara ja seega�a

p

�=

�ck

p

�= (�1)k �

�cp�12

�k=�ck� p�1

2 � ap�12 (mod p):

2

Kuigi Euleri kriteeriumi abil saab p~ohim~otteliselt iga arvu korral kindlaks teha, kas ta on ruutj�a�ak, ei ole ta siiski

sobiv suurte algarvude p korral. ~Onneks on Legendre'i s�umbolil terve rida omadusi, mis lihtsustavad arvutamist.

Lause 9.6. Iga algarvu p > 2 korral on Legendre'i s�umbolil j�argmised omadused.

1. Iga a; b 2Zkorral, kui a � b (mod p), siis�ap

�=�bp

�.

2. Iga a; b 2Zkorral �ab

p

�=

�a

p

��b

p

�:

3. Iga a; b 2Z, p - b, korral �ab2

p

�=

�a

p

�:

4. Kehtib�1p

�= 1 ja

��1p

�= (�1)

p�12 =

�1; kui p � 1 (mod 4)

�1; kui p � 3 (mod 4).

T~oestus. 1. j�areldub vahetult Legendre'i s�umboli de�nitsioonist.

2. Kui p j a v~oi p j b, siis on v�aide ilmne. Oletame, et p - a ja p - b. Olgu Z�p = fc; c2; : : : ; cp�1 = 1g, a = ck ja

b = cl. Siis v�aite 1 ja lemma 9.4 p~ohjal�ab

p

�=

�ck+l

p

�= (�1)k+l = (�1)k(�1)l =

�ck

p

��cl

p

�=

�a

p

��b

p

�:

3. Kui p - b, siis vastavalt de�nitsioonile 9.3�b2

p

�= 1 ning seega osa 2. p~ohjal

�ab2

p

�=

�a

p

��b2

p

�=

�a

p

�:

4. V~ordus�1p

�= 1 kehtib sellet~ottu, et 1

2= 1 korpuses Zp. Teine v~ordus j�areldub Euleri kriteeriumist v~ottes

a = �1 v~oi j�areldusest 8.21, sestp�12

on paarisarv parajasti siis kui p� 1 jagub neljaga ehk p � 1 (mod 4). 2

N�aide 9.7. Teeme kindlaks, kas kongruents x2 � �38 (mod 13) on lahenduv. Selleks tuleks leida Legendre'i

s�umboli��3813

�v�a�artus. Kuna 38 � 12 (mod 13) ja (�1)

13�12 = 1, siis saame, et

��3813

�=

��113

��38

13

�=

�12

13

�=

�3 � 2213

�=

�3

13

�:

Viimase s�umboli arvutamiseks kasutame Euleri kriteeriumi. Et�3

13

�� 3

13�12 = 36 = 272 � 1 (mod 13);

siis�313

�= 1 ja seega ka

��3813

�= 1, s.t. kongruentsil x2 � �38 (mod 13) on lahend olemas.

V�aikse k~orvalep~oikena kasutame lauset 9.6 selleks, et n�aidata teatud kujul algarvude hulga l~opmatust.

Lause 9.8. On l~opmata palju algarve kujul 4k + 1.

38

Page 39: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Oletame, et on ainult l~oplik arv selliseid algarve; t�ahistame nad p1; p2; : : : ; pn. Vaatleme naturaalarvu

a = (2p1p2 : : : pn)2 + 1. On selge, et a on paaritu, seega peab leiduma mingi paaritu algarv p, nii et p j a,

ehk (2p1p2 : : : pn)2 � �1 (mod p). See t�ahendab, et �1 on ruutj�a�ak mooduli p j�argi, ehk

��1p

�= 1. Lause 9.6

p~ohjal��1p

�= 1 parajasti siis, kui p = 4k + 1, k 2 N. Seega p on �uks algarvudest p1; : : : ; pn. J�arelikult p j

a� (2p1p2 : : : pn)2 = 1, vastuolu. 2

Teeme n�u�ud kindlaks, millal on arv 2 ruutj�a�ak mooduli p j�argi.

Teoreem 9.9. Iga algarvu p > 2 korral�2

p

�= (�1)

p2�18 =

�1; kui p � �1 (mod 8);

�1; kui p � �3 (mod 8):

T~oestus. Vaatleme j�argmist p�12

kongruentsist koosnevat s�usteemi:

p� 1 � 1(�1)1 (mod p)

2 � 2(�1)2 (mod p)

p� 3 � 3(�1)3 (mod p)

4 � 4(�1)4 (mod p)

: : :

r � p�12(�1)

p�12 (mod p);

kus r on kas p� p�12

(juhul kui p�12

on paaritu arv) v~oip�12

(kui p�12

on paarisarv). Korrutades nende kongruentside

vastavad pooled saame

2 � 4 � 6 � : : : � (p � 1) ��p� 1

2

�!(�1)1+2+:::+

p�12 (mod p):

K~oik tegurid selle kongruentsi vasakul poolel on paarisarvud

ja�1 + p�1

2

�p�14

= p2�18

, j�arelikult

2p�12

�p� 1

2

�! ��p� 1

2

�!(�1)

p2�18 (mod p):

Kuna�p�12

�! 6� 0 (mod p), siis

2p�12 � (�1)

p2�18 (mod p):

Euleri kriteeriumi p~ohjal 2p�12 �

�2p

�(mod p); millest j�areldubki v�aide, sest kuna kongruentsi

�2p

�� (�1) p

2�18

(mod p) m~olemal poolel on kas 0; 1 v~oi �1 ja p > 2 ning 1 6� �1 (mod p) ja loomulikult ka 1 6� 0 6� �1 (mod p),

siis viimase kongruentsi m~olemal poolel peavad olema v~ordsed arvud. 2

Lemma 9.10. Kui G on r�uhm ja a 2 G, siis G = aG, kus aG = fag j g 2 Gg.

T~oestus. Kui g 2 G, siis g = (aa�1)g = a(a�1g) 2 aG, seega G � aG. Vastupidine sisalduvus on ilmne. 2

J�areldus 9.11. Kui n > 1 ja a on �uhistegurita t�aisarvud, siis U (Zn) = a�U (Zn). Teiste s~onadega, kui a1; a2; : : : ; a'(n)on k~oik naturaalarvud, mis on v�aiksemad kui n ja on arvuga n �uhistegurita, siis

aa1; aa2; : : : ; aa'(n)

on mooduli n j�argi kongruentsed arvudega a1; a2; : : : ; a'(n) mingis j�arjekorras.

J�areldus 9.12. Kui q on algarv ja q - a, siis Z�p = a �Z�p, s.t. arvud a; 2a; : : : ; (q � 1)a on mooduli q j�argikongruentsed arvudega 1; 2; : : : ; q � 1 mingis j�arjekorras.

J�argmine, Gaussi poolt 1796. a. t~oestatud teoreem kuulub arvuteooria k~oige ilusamate ja s�ugavamate tulemuste

hulka. Tr�ukis on avaldatud v�ahemalt 150 erinevat t~oestust, Gauss ise andis v�ahemalt 8 erinevat t~oestust.

Teoreem 9.13 (Ruutvastavuss�a�adus). Kui p > 2 ja q > 2 on erinevad algarvud, siis

�p

q

�= (�1)

(p�1)(q�1)4

�q

p

�=

8<:

��q

p

�; kui p � q � 3 (mod 4);�

q

p

�; �ulej�a�anud juhtudel:

39

Page 40: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. Olgu n selline naturaalarv, et pn � 1 (mod q) (n�aiteks v~oib Fermat' v�aikse teoreemi t~ottu v~otta n =

q� 1). Vaatleme pn-elemendilist korpust Fpn . Siis q j pn� 1 ja teoreemi 8.19 p~ohjal leidub selles korpuses q: astme

primitiivne �uhejuur; t�ahistame ta t�ahega �. Siis muuhulgas �q = 1, kus 1 on korpuse Fpn �uhikelement. De�neerime

summa

G =

q�1Xj=1

�j

q

��j 2 Fpn :

N�aitame, et G2 = (�1)q�12 q1 (s.t. et G2 on kas q1 v~oi �q1, s~oltuvalt sellest, kas q�1

2on paaris v~oi paaritu).

Kasutades seda, et kui k omandab v�a�artused 1; 2; : : : ; q � 1; siis ka q � k omandab samad v�a�artused, lauset 9.6,

ning seda, et �q�k = ��k, saame, et

G2 = G �G =

0@q�1X

j=1

�j

q

��j

1A q�1Xk=1

�q � k

q

��q�k

!=

q�1Xj=1

�j

q

��j

q�1Xk=1

��kq

���k

!

=

��1q

� q�1Xj=1

�j

q

��j

q�1Xk=1

�k

q

���k

!= (�1)

q�12

q�1Xj=1

�j

q

��j

q�1Xk=1

�k

q

���k

!:

Kasutades j�areldust 9.12 saame, et kui k omandab k~oik v�a�artused 1; 2; : : : ; q�1, siis iga �kseeritud j 2 f1; : : : ; q�1gkorral

ka jk omandab samad v�a�artused mooduli q j�argi. Seega arvestades, et kui jk = uq + v; kus 0 < v < q; siis�jk

q

���jk =

�uq+vq

���uq�v =

�vq

���v, saame, et

G2 = (�1)q�12

q�1Xj=1

�j

q

��j

q�1Xk=1

�jk

q

���jk

!= (�1)

q�12

q�1Xj=1

q�1Xk=1

�j2k

q

��j(1�k) = (�1)

q�12

q�1Xk=1

�k

q

�0@q�1Xj=1

�j(1�k)

1A

= (�1)q�12

0@q�1X

k=1

�k

q

�0@q�1Xj=0

�j(1�k)

1A �

q�1Xk=1

�k

q

�1

1A = (�1)

q�12

q�1Xk=1

�k

q

�0@q�1Xj=0

�j(1�k)

1A ;

sest mooduli q j�argi on ruutj�a�ake ja mitteruutj�a�ake hulgas f1; : : : ; q � 1g �uhepalju ja seegaPq�1

k=1

�kq

�= 0. Siis

�1� �1�k

� q�1Xj=0

�j(1�k) =

q�1Xj=0

�j(1�k)�q�1Xj=0

�(j+1)(1�k) =

q�1Xj=0

�j(1�k) �qX

j=1

�j(1�k) = �0 � �q(1�k) = 1� 1 = 0:

Et k 2 f2; : : : ; q � 1g korral 1 � �1�k 6= 0 ja korpuses pole nullitegureid, siis iga k = 2; : : : ; q � 1 korral peabPq�1j=0 �

j(1�k) = 0. J�arelikult

G2 = (�1)q�12

�1

q

�0@q�1Xj=0

�0

1A = (�1)

q�12

�1

q

�q1 = (�1)

q�12 q1:

Kasutades saadud v~ordust, Euleri kriteeriumi ja seda, et korpuse Fpn karakteristika on p, saame, et

Gp =�G2� p�1

2 G =�(�1)

q�12 q1

� p�12

G = (�1)q�12 �

p�12 q

p�12 1 �G = (�1)

(p�1)(q�1)4

�q

p

�G:

Teisest k�uljest, kasutades lemmat 8.6, seda, et p on paaritu ning seda, et kui j omandab v�a�artused 1; 2; : : : ; q � 1,

siis ka pj omandab need v�a�artused mooduli q j�argi, saame, et

Gp =

0@q�1X

j=1

�j

q

��j

1Ap

=

q�1Xj=1

�j

q

�p�pj =

q�1Xj=1

�j

q

��pj =

q�1Xj=1

�p2j

q

��pj

=

q�1Xj=1

�p

q

��pj

q

��pj =

�p

q

� q�1Xj=1

�pj

q

��pj =

�p

q

� q�1Xj=1

�j

q

��j =

�p

q

�G:

Seega oleme saanud, et �p

q

�G = (�1)

(p�1)(q�1)4

�q

p

�G:

40

Page 41: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Kuna G2 = q1 v~oi G2 = �(q1) ja korpuse Fpn karakteristika p 6= q, siis G 6= 0. Korrutades viimast v~ordust

elemendiga G�1 2 Fpn , saame, et �p

q

�1 = (�1)

(p�1)(q�1)4

�q

p

�1:

Et korpuse Fpn karakteristika p on suurem kui 2, siis saame sellest v~ordusest, et�p

q

�= (�1)

(p�1)(q�1)4

�q

p

�:

2

N�aide 9.14. Teeme kindlaks, kas algarv 7411 on ruutj�a�ak algarvulise mooduli 9283 j�argi.

Kuna 7411 � 3 (mod 4) ja 9283 � 3 (mod 4) ning 13 � 1 (mod 4), siis

�7411

9283

�= �

�9283

7411

�= �

�1872

7411

�= �

�22�2

7411

!�32

7411

��13

7411

�= �

�13

7411

�= �

�7411

13

�= �

�1

13

�= �1:

Seega 7411 on mitteruutj�a�ak mooduli 9283 j�argi.

Legendre'i s�umboli �uldistuseks on saksa matemaatiku Jacobi (1804{1851) poolt sisse toodud s�umbol.

De�nitsioon 9.15. Olgu a t�aisarv ja n paaritu naturaalarv. Olgu n = p1p2 : : : ps, kus p1; p2; : : : ; ps on algarvud

(nende hulgas v~oib olla v~ordseid). Jacobi s�umbol�an

�de�neeritakse Legendre'i s�umbolite abil j�argmiselt:

� an

�=

�a

p1

��a

p2

�: : :

�a

ps

�:

De�nitsiooni 9.1 loomulikul viisil �uldistades �oeldakse, et t�aisarv a on ruutj�a�ak naturaalarvulise mooduli n j�argi,

kui kongruents x2 � a (mod n) on lahenduv.

M�arkus 9.16. Kui n on kordarv ja�an

�= 1, siis see ei t�ahenda veel, et a on ruutj�a�ak mooduli n j�argi. N�aiteks�

215

�=�23

� �25

�= (�1) (�1) = 1, kuid ei leidu sellist t�aisarvu x, et x2 � 2 (mod 15), sest kui ta leiduks, siis oleks

ka x2 � 2 (mod 3).

K�ull aga sellest, et�an

�= �1 j�areldub, et a on mitteruutj�a�ak mooduli n j�argi, sest siis v�ahemalt �uhe pi korral�

api

�= �1 ja kui vastuv�aiteliselt oletada, et leidub selline x 2Z, et x2 � a (mod n), siis ka x2 � a (mod pi), mis

oleks vastuolu.

Jacobi s�umboli omadused on �usna sarnased Legendre'i s�umboli omadustega.

Lause 9.17. Jacobi s�umbolil on j�argmised omadused.

1. Iga a; b 2Zja paaritu naturaalarvu n korral, kui a � b (mod n), siis�an

�=�bn

�.

2. Iga a; b 2Zja paaritu naturaalarvu n korral�ab

n

�=�an

�� b

n

�:

3. Iga a 2Zja paaritute naturaalarvude n ja m korral� a

nm

�=�an

�� am

�:

T~oestus. Kaks esimest omadust j�arelduvad vahetult Legendre'i s�umboli vastavatest omadustest ning kolmas

j�areldub Jacobi s�umboli de�nitsioonist. 2

Lemma 9.18. Kui k ja l on paaritud naturaalarvud, siis

1. (kl � 1)=2 � (k � 1)=2 + (l � 1)=2 (mod 2);

2. (k2l2 � 1)=8 � (k2 � 1)=8 + (l2 � 1)=8 (mod 2):

41

Page 42: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

T~oestus. 1. Kuna (k� 1)(l� 1) � 0 (mod 4); siis kl� 1 � (k� 1) + (l� 1) (mod 4): V�aide j�areldub n�u�ud lausest

3.9, sest viimase kongruentsi m~olemal poolel on paarisarvud.

2. saab t~oestada analoogiliselt. 2

Lemma 9.19. Kui k1; k2; : : : ; ks on paaritud naturaalarvud, siis

1.Ps

i=1(ki � 1)=2 � (k1k2 : : :ks � 1)=2 (mod 2);

2.Ps

i=1(k2i � 1)=8 � (k21k

22 : : :k

2s � 1)=8 (mod 2):

T~oestus. T~oestame v�aite 1. induktsiooniga s j�argi (v�aite 2. saab t~oestada analoogiliselt). Kui s = 1, siis on v�aide

ilmne. Kui s = 2, siis kasutame eelmist lemmat. Olgu s > 2 ja oletame, et v�aide kehtib, kui arve on v�ahem kui s.

Siis kasutades eelmist lemmat saame

k1 � 1

2+ : : :+

ks�1 � 1

2+

ks � 1

2� k1 : : :ks�1 � 1

2+ks � 1

2� k1 : : :ks�1ks � 1

2(mod 2):

2

�Uldistame n�u�ud teoreemid 9.9 ja 9.13 Jacobi s�umbolite jaoks.

Lause 9.20. Mistahes paaritute naturaalarvude n ja m korral

1.��1n

�= (�1)n�1

2 ;

2.�2n

�= (�1)

n2�18 ;

3.�mn

�= (�1)

(m�1)(n�1)4

�nm

�:

T~oestus. Olgu n = p1p2 : : : ps ja m = q1q2 : : : qr; kus p1; : : : ; ps ja q1; : : : ; qr on algarvud.

1. T�anu lemmale 9.19Ps

i=1(pi � 1)=2 � (p1p2 : : : ps� 1)=2 = (n� 1)=2 (mod 2) ning seet~ottu kasutades lauset 9.6

saame ��1n

�=

��1p1

�: : :

��1ps

�= (�1)

p1�1

2 : : : (�1)ps�12 = (�1)

Psi=1

pi�1

2 = (�1)n�12 :

2. T�anu lemmale 9.19Ps

i=1(p2i � 1)=8 � (p21p

22 : : : p

2s� 1)=8 = (n2� 1)=8 (mod 2) ning seet~ottu kasutades teoreemi

9.9 saame �2

n

�=

�2

p1

�: : :

�2

ps

�= (�1)

p21�1

8 : : : (�1)p2s�1

8 = (�1)Ps

i=1

p2i�1

8 = (�1)n2�1

8 :

3. Kui leiduvad sellised i ja j, et pi = qj, siis vastavalt Legendre'i s�umboli de�nitsioonile�piqj

�=�qjpi

�= 0 ning

seega on t~oestatava v~orduse m~olemal poolel 0: Eeldame n�u�ud, et selliseid v~ordseid algarve ei leidu. Rakendades

veelkord lemmat 9.19 saame

rXi=1

sXj=1

qi � 1

2� pj � 1

2=

rX

i=1

qi � 1

2

!0@ sX

j=1

pj � 1

2

1A � m � 1

2� n� 1

2(mod 2):

Kasutades ruutvastavuss�a�adust ja seda, et�qipj

�2= 1; saame siis

�mn

�� nm

�=

rYi=1

sYj=1

�qi

pj

��pj

qi

�= (�1)

Pri=1

Psj=1

qi�1

2 �pj�1

2 = (�1)m�12 �

n�12 :

2

N�aide 9.21. Leiame Legendre'i�74119283

�s�umboli v�a�artuse ilma arvu 1872 teguriteks lahutamata (v�alja arvatud 2

astmete eraldamine). Kasutades lauset 9.20 saame�7411

9283

�= �

�1872

7411

�= �

�16

7411

��117

7411

�= �

�7411

117

�= �

�40

117

= ��

2

117

��5

117

�=

�5

117

�=

�117

5

�=

�2

5

�= �1:

42

Page 43: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

10. Arvuvallad

Selles paragrahvis uurime, kuidas saab naturaalarvudest l�ahtudes loomulikul viisil konstrueerida t�aisarvud,

t�aisarvudest l�ahtudes ratsionaalarvud, ning veendume, et ratsionaalarvude �uldistusena v~oib lisaks reaalarvudele

vaadelda ka veel hoopis teistsuguseid arvuhulki.

10.1. Naturaalarvudelt t�aisarvudele

Naturaalarvude hulk N on kinnine liitmise suhtes, kuid kahe naturaalarvu vahe ei pruugi olla naturaalarv.

V�ahim hulk, mis sisaldab N ja on kinnine lahutamise suhtes, on t�aisarvude hulk Z. Iga t�aisarvu v~oib esitada

(kuigi mitte �uheselt) kahe naturaalarvu vahena. J�argnevas n�aitame, et kasutades algebralisi konstruktsioone saab

l�ahtudes poolr�uhmast (N;+) konstrueerida r�uhma (Z;+), kusjuures N � Z. Vastava v�aite t~oestame tegelikult

tunduvalt �uldisemal juhul.

De�nitsioon 10.1. Olgu (S;+) kommutatiivne poolr�uhm. �Oeldakse, et S on taandamisega poolr�uhm, kui iga

x; y; z 2 S korral

x+ y = x+ z =) y = z:

Poolr�uhm (N;+) on �uheks taandamisega poolr�uhma n�aiteks.

Teoreem 10.2. Iga kommutatiivse taandamisega poolr�uhma saab sisestada r�uhma.

T~oestus. Olgu (S;+) kommutatiivne taandamisega poolr�uhm.N�aitame, et leidub r�uhmG, mis sisaldab poolr�uhmaga

S isomorfset alampoolr�uhma. Selleks de�neerime hulga S otseruudul S2 = S � S binaarse seose � j�argmiselt:

(x; y) � (u; v)() x+ v = y + u;

mistahes (x; y); (u; v) 2 S2 korral. N�aitame, et � on ekvivalentsusseos.

Re eksiivsus. Et x+ y = y + x, siis (x; y) � (x; y).

S�ummeetrilisus. Kui (x; y) � (u; v), siis x+ v = y + u, j�arelikult u+ y = v + x, s.t. (u; v) � (x; y).

Transitiivsus. Olgu (x; y) � (u; v) ja (u; v) � (w; z). Siis x + v = y + u ja u + z = v + w. Nendest v~ordustest

j�areldub, et x+ v + z = y + u+ z = y + v +w. Taandades v saame, et x+ z = y + w ehk (x; y) � (w; z).

T�ahistame faktorhulga seose � j�argi

G = (S � S)=�= f(x; y)=�j x; y 2 Sg ;

kus (x; y)=� t�ahistab paari (x; y) 2 S � S ekvivalentsiklassi seose � j�argi. N�aitame, et G osutub r�uhmaks, kui

de�neerida hulgal G liitmine � reegliga

(x; y) =� � (u; v) =� = (x+ u; y + v) =� :

Kontrollime, kas see de�nitsioon on korrektne. Selleks oletame, et (x; y) � (x0; y0) ja (u; v) � (u0; v0), s.t. x+ y0 =

y + x0 ja u+ v0 = v + u0. Liites nende v~orduste vastavad pooled ja kasutades seda, et poolr�uhmal S de�neeritud

liitmine on kommutatiivne, saame, et x+ u+ y0 + v0 = y + v + x0+ u0 ehk (x+ u; y+ v) � (x0 + u0; y0 + v0). Seega

t~oesti liitmise tulemus ei s~oltu ekvivalentsiklassi esindajate valikust.

Kuna

(x; y) =� � (u; v) =� = (x+ u; y + v) =�= (u+ x; v + y) =� = (u; v) =� � (x; y) =�;siis liitmistehe � on kommutatiivne. Analoogiliselt j�areldub sellest, et liitmine poolr�uhmal S on assotsiatiivne, see,

et ka tehe � on assotsiatiivne hulgal G. Fikseerime mingi elemendi z 2 S. Siis nullelemendiks on klass (z; z)=�.T~oepoolest, iga (x; y) 2 S2 korral (z; z)=� �(x; y)=� = (z + x; z + y)=� = (x; y)=�, sest z + x + y = z + y + x.

Elemendi (x; y)=� 2 G vastandelemendiks on (y; x)=�, sest (x; y)=� �(y; x)=� = (x + y; y + x)=� = (z; z)=�,kuna x+ y + z = y + x+ z: Seega G on t~oesti r�uhm.

N�aitame, et poolr�uhm (S;+) on isomorfne r�uhma (G;�) mingi alampoolr�uhmaga.

Fikseerime mingi elemendi y 2 S. Vaatleme hulka S0 = f(x + y; y)=�j x 2 Sg � G. Kuna iga x; x0 2 S korral

(x+ y; y)=� �(x0 + y; y)=�= (x+ y + x0 + y; y + y)=�= (x+ x0 + y; y)=�2 S0, siis S0 on r�uhma G alampoolr�uhm.

De�neerime kujutuse ' : S �! S0 j�argmiselt: iga x 2 S korral

'(x) = (x + y; y)=� :

On selge, et ' on p�a�alekujutus. N�aitame, et ' on �uks�uhene. Selleks oletame, et '(x) = '(x0) ehk (x + y; y) �(x0 + y; y). Siis x+ y + y = y + x0 + y. Taandades y + y saame, et x = x0. Seega ' on �uks�uhene. Kuna

'(x + x0) = (x+ x0 + y; y)=� = (x+ x0 + y + y; y + y)=�= (x+ y; y)=� �(x0 + y; y)=� = '(x) � '(x0);

siis ' on poolr�uhmade homomor�sm.

Seega ' on bijektiivne homomor�sm ehk isomor�sm ja S �= S0 = '(S) � G, kus S0 on r�uhma G alampoolr�uhm.

2

43

Page 44: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

De�nitsioon 10.3. R�uhma (G;�) nimetatakse poolr�uhma (S;+) vahede r�uhmaks.

Konstrueerides poolr�uhma (N;+) vahede r�uhma saame r�uhma, mis on isomorfne r�uhmaga (Z;+).

Seega poolr�uhma (N;+) saab sisestada r�uhma (Z;+). Kuid �akki on r�uhmalZm~oni p�arisalamr�uhm, mis samuti

sisaldab poolr�uhma (N;+) alampoolr�uhmana? J�argmine v�aide �utleb, et r�uhm Zsiiski ei sisalda liigseid elemente.

Lause 10.4. Kommutatiivse taandamisega poolr�uhma (S;+) vahede r�uhma (G;�) v�ahim alamr�uhm, mis sisaldabpoolr�uhma S alampoolr�uhmana, on G ise.

T~oestus. Kasutame teoreemi 10.2 t�ahistusi. Olgu G0 r�uhma (G;�) v�ahim alamr�uhm, mis sisaldab poolr�uhma

S �= S0 alampoolr�uhmana. Olgu (u; v)=� 2 G suvaline element. Kuna S0 � G0, siis (u+y; y)=�; (v+y; y)=� 2 G0.

Et G0 on alamr�uhm, siis on ta kinnine vastandelemendi v~otmise ja liitmise suhtes, j�arelikult (y; v+y)=� 2 G0 ning

(u+ y; y)=� �(y; v + y)=� = (u+ y + y; y + v + y)=� = (u; v)=� 2 G0:

Seega G = G0. 2

Tekib veel k�usimus, kas lisaks r�uhmale (Z;+) on veel teisi r�uhmi, mis sisaldavad poolr�uhma (N;+) alam-

poolr�uhmana ja millel pole sama omadusega p�arisalampoolr�uhmi. Osutub, et nii see siiski pole.

Lause 10.5. Kui (S;+) on kommutatiivne taandamisega poolr�uhm, siis iga r�uhm H, mis sisaldab poolr�uhma S

alampoolr�uhmana ja mille v�ahim poolr�uhma S alampoolr�uhmana sisaldav alamr�uhm on see r�uhm ise, on isomorfnepoolr�uhma S vahede r�uhmaga.

T~oestus. Vaatleme sellist r�uhma (H;+) ja tema alamhulka

H0 = fx� y j x; y 2 Sg � H;

Kuna mistahes x�y; x0�y0 2 H0 korral (x�y)+(x0�y0) = (x+x0)�(y+y0) 2 H0 ja �(x�y) = y�x 2 H0, siis H0

on r�uhma H alamr�uhm. Fikseerime z 2 S: Et mistahes x 2 S korral x = (x+ z)� z, siis S � H0 ja et S on r�uhma

H alampoolr�uhm, siis on ta ka r�uhma H0 alampoolr�uhm. Kuna r�uhma H v�ahim poolr�uhma S alampoolr�uhmana

sisaldav alamr�uhm on H ise, siis H0 = H.

De�neerime kujutuse ' : H �! G nii, et

'(x � y) = (x; y)=�

iga x; y 2 S korral. Veendume, et ' de�nitsioon on korrektne. Selleks oletame, et x � y = x0 � y0; x; y; x0; y0 2S. Siis x + y0 = y + x0 ning j�arelikult (x; y) � (x0; y0). Seega ' on de�neeritud korrektselt. On selge, et ' on

s�urjektiivne. N�aitame, et ta on ka injektiivne. Selleks oletame, et (x; y) � (x0; y0); x; y; x0; y0 2 S. Siis vastavalt seose

� de�nitsioonile x + y0 = y + x0 ja j�arelikult x � y = x0 � y0 r�uhmas H. Seega ' on injektiivne. L~opuks, kuna

mistahes x; y; u; v 2 S korral

'((x� y) + (u � v)) = '((x + u)� (y + v)) = (x+ u; y + v)=�= (x; y)=� �(u; v)=� = '(x� y) � '(u� v);

siis ' on r�uhmade homomor�sm. Seega ' on isomor�sm ning r�uhmad G ja H on isomorfsed. 2

Arvestades lauset 10.1 v~oime v�aita, et t�aisarvude r�uhm (Z;+) on v�ahim poolr�uhma (N;+) alampoolr�uhmana

sisaldav Zalamr�uhm ja ta on isomor�smi t�apsuseni �uheselt m�a�aratud.

10.2. T�aisarvudelt ratsionaalarvudele

T�aisarvude hulkZon kinnine liitmise, lahutamise ja korrutamise suhtes, kuid kahe t�aisarvu jagatis ei pruugi olla

t�aisarv. V�ahim hulk, mis sisaldabZja on kinnine nullist erinevate elementidega jagamise suhtes, on ratsionaalarvude

hulkQ. Iga ratsionaalarvu v~oib esitada kahe t�aisarvu jagatisena. Osutub, et analoogilise konstruktsiooni saab j�allegi

l�abi viia �uldisemal juhul.

Teoreem 10.6. Iga kommutatiivse nullitegureita ringi R saab sisestada mingisse korpusse K.

Selle teoreemi t~oestuse v~oib leida raamatust [1], lk. 199{200. Sellist korpust K nimetatakse ringi R jagatis-te korpuseks. Lihtne on veenduda, et konstrueerides ringi Zjagatiste korpuse saame korpuse, mis on isomorfne

ratsionaalarvude korpusega Q.

Analoogiliselt vahede r�uhma juhuga saab n�aidata, et ringiR jagatiste korpusK on korpuseK v�ahim alamkorpus,

mis sisaldab ringi R alamringina. Veelgi enam, korpus, mille v�ahim ringi R sisaldav alamkorpus on see korpus ise,

on isomor�smi t�apsuseni �uheselt m�a�aratud. Seda arvestades v~oib �oelda, et ratsionaalarvude korpus Q on v�ahim

ringi Zalamringina sisaldav korpuse Q alamkorpus ja ta on isomor�smi t�apsuseni �uheselt m�a�aratud.

44

Page 45: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

10.3. Ratsionaalarvudelt reaalarvudele

De�nitsioon 10.7. Hulka (K;+; �;�); kus + ja � on kahekohalised algebralised tehted ja � on binaarne seos hulgal

K nimetatakse reaalarvude hulgaks, kui

R1. (K;+; �) on korpus;

R2. � on lineaarne j�arjestusseos hulgal K (s.t. selline j�arjestusseos, et mistahes �; � 2 K korral kas � � � v~oi

� � �) ning mistahes �; �; ; � 2 K; � > 0; korral

� < � =) �+ < � + ja �� < ��;

R3. (t�aielikkuse aksioom) hulga K igal mittet�uhjal alt t~okestatud alamhulgal on olemas alumine raja hulgas K.

M�arkus 10.8. AksioomisR2. kasutatakse seost <; mis de�neeritakse mistahes j�arjestusseose � korral j�argmiselt:

� < � () � � � ja � 6= �:

10.3.1. Weierstrassi meetod

Weierstrassi teooria j�argi on reaalarv l~opmatu k�umnendmurd pluss- v~oi miinusm�argiga:

�a0; a1a2 : : :an : : : ;

kus a0 on mittenegatiivne t�aisarv ja iga an; n 2 N, on �uks numbreist 0; 1; : : : ; 9. Seejuures l~opmatu k�umnend-

murd perioodiga 9, s.o. k�umnendmurd a0; a1a2 : : : an(9); kus an 6= 9, loetakse v~ordseks l~opmatu k�umnendmurruga

a0; a1a2 : : :an�1(an + 1)000 : : : (juhul n = 0 k�umnendmurruga (a0 + 1); 000 : : :). Arve �n = a0; a1a2 : : : an ja

�n = a0; a1a2 : : : an + 10�n nimetatakse vastavalt reaalarvu � = a0; a1a2 : : :an : : : alumiseks ja �ulemiseks n: j�arkuk�umnendl�ahendiks. Kui reaalarvu � m�ark on pluss (miinus) ja t�aisarvude an; n 2 N, seas on v�ahemalt �uks nullist

erinev, siis �oeldakse, et � on positiivne (negatiivne). Arvu � = �a0; a1a2 : : :an : : : absoluutv�a�artuseks nimetatakse

arvu a0; a1a2 : : :an : : : ning seda t�ahistatakse j�j :Olgu � = a0; a1a2 : : :an : : : ja � = b0; b1b2 : : : bn : : : . Loeme, et � < �, kui kas a0 < b0 v~oi leidub selline

N 2 N[ f0g; et ak = bk; k = 0; 1; : : : ; N , kuid aN+1 < bN+1: Lisaks sellele loeme, et iga negatiivne arv ja 0 on

v�aiksem igast positiivsest arvust ning kui � ja � on negatiivsed ja j�j < j�j ; siis � < �: Lugedes � � � kui � = �

v~oi � < � saame lineaarse j�arjestusseose � :�Oeldakse, et t�aisarvude jada (xk)k2Nstabiliseerub arvuks m; kui leidub selline indeks N; et iga k � N korral

xk = m: �Oeldakse, et l~opmatute k�umnendmurdude jada (�k)k2N= (ak0; ak1a

k2 : : : a

kn : : : )k2Nstabiliseerub arvuks

� = a0; a1a2 : : :an : : : ; kui l~opmatu maatriksi (a(k)

i ) (i on siin veerunumber, k reanumber) i: veerg stabiliseerub

arvuks ai iga i 2 N[ f0g korral. Kui � > 0 ja � > 0; siis k�umnendmurdudest �k + �k; �k � �k; (�k�k)k ja�

�k

�k

�k

moodustatud jadad stabiliseeruvad arvudeks, mida nimetatakse vastavalt reaalarvude � ja � summaks �+�; vaheks�� �; korrutiseks �� ning jagatiseks �

�: Neid de�nitsioone saab laiendada ka suvalise m�argiga reaalarvude jaoks.

N�aiteks, kui � � 0 ja � � 0; siis �+ � = �(j�j+ j�j); kui � ja � on erinevate m�arkidega, siis �+ � = ����j�j� j�j

���;kus m�argiks v~oetakse liidetavaist absoluutv�a�artuselt suurema m�ark. Mistahes �; � korral loetakse ��� = �+(��)jne. Saab n�aidata, et l~opmatute k�umnendmurdude hulk koos temal de�neeritud tehetega + ja � ning j�arjestusega

� rahuldab aksioome R1.{R3.

10.3.2. Dedekindi meetod

De�nitsioon 10.9. Dedekindi l~oige on j�arjestatud paar (�; �); mis koosneb kahest hulgast, � � Q (\vasakpoolne"

ehk \alumine" hulk) ja � � Q (\parempoolne" ehk \�ulemine" hulk), mis rahuldavad j�argmisi tingimusi:

D1. iga ratsionaalarv kuulub �uhte hulkadest � ja �;

D2. � 6= ; ja � 6= ;;

D3. � iga element on v�aiksem � igast elemendist;

D4. hulgas � pole v�ahimat elementi.

Kumbki hulkadest � ja � m�a�arab �uheselt �ara teise ja seega ka kogu l~oike. Seega edaspidises v~oime Dedekindi

l~oike samastada tema parempoolse hulgaga �, millel on j�argmised omadused:

D10. � 6= ; ja tema t�aiend � = Qn � 6= ;;

45

Page 46: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

D20. kui b 2 �; b0 2 Q ja b < b0; siis b0 2 �;

D30. hulgas � pole v�ahimat elementi.

Edasises t�ahistame kreeka t�ahtedega �; �; : : : parempoolseid hulki ja nimetame Dedekindi l~oikeid reaalarvudeks.K~oigi Dedekindi l~oigete hulga t�ahistame R:

Iga ratsionaalarv am�a�arab �ara l~oike a = fb 2 Q j a < bg ;mida nimetame ratsionaalseks. L~oige � on ratsionaalne

siis ja ainult siis, kui hulga � t�aiendil � on olemas suurim element. Hulga Q saab sisestada hulka R kujutuse

f : Q �! R, f(a) = a, abil. Mitte k~oik l~oiked ei ole ratsionaalsed. N�aiteks saab n�aidata, etp2; ehk t�apsemalt

�oeldes l~oige � =�a 2 Q j a > 0; a2 > 2

ei ole ratsionaalne.

L~oigete (parempoolsete hulkade) j�arjestuse de�neerime j�argmiselt:

� � � () � � �:

Lihtne on veenduda, et � on osalise j�arjestuse seos hulgal R: Veelgi enam, see seos on ka lineaarne j�arjestusseos ja

rahuldab aksioomi R3.

Mistahes kahe l~oike �; � 2 R summa ja vahe de�neerime v~ordusega

�� � = fa� b j a 2 �; b 2 �g :

Kui �; � � 0 (= 0), siis de�neerime nende l~oigete korrutise v~ordusega

� � � = fab j a 2 �; b 2 �g :

Mistahes l~oike saab esitada kahe mittenegatiivse l~oike � � 0 ja � � 0 vahena: = � � �: L~oigete = �� � ja

0 = �0 � �0; kus ka �0; �0 � 0; korrutise de�neerime v~ordusega

� 0 = (�� �) � (�0 � �0) = � ��0 + � � �0 � � � �0 � � ��0:

Saab n�aidata, et de�neeritud tehete suhtes osutub hulk R korpuseks ja et j�arjestus � on koosk~olas liitmise ja

korrutamisega.

10.3.3. Cantori meetod

De�nitsioon 10.10. Ratsionaalarvujada (ai) nimetatakse fundamentaaljadaks ehk Cauchy jadaks, kui iga ratsio-naalarvu " > 0 korral leidub selline indeks N , et iga i; j � N korral jai � ajj < ":

�Oeldakse, et ratsionaalarvujada (ai) on ratsionaalselt koonduv, kui leidub selline ratsionaalarv a, et iga ratsio-

naalarvu " > 0 korral leidub selline indeks N; et iga i � N korral jai � aj < ": Sellisel juhul on a �uheselt m�a�aratud

ja kirjutatakse a = limai:

Iga ratsionaalselt koonduv jada on Cauchy jada. Samas leidub Cauchy jadasid, mis ei koondu ratsionaalselt,

nt.p2 l�ahismurdude jada a0 = 1; a1 = 1; 4; a2 = 1; 41; a3 = 1; 414; a4 = 1; 4142; : : : .

De�nitsioon 10.11. Ratsionaalselt nulliks koonduvat jada, s.t. sellist jada (ai) ; et iga " > 0 korral leidub N nii,

et iga i � N korral jaij < "; nimetatakse nulljadaks.

Olgu F (Q) k~oigi ratsionaalarvuliste Cauchy jadade hulk. De�neerime hulgal F (Q) seose � j�argmiselt:

(ai) � (bi)() (ai � bi) on nulljada.

Saab n�aidata, et � on ekvivalentsusseos. T�ahistame faktorhulga selle seose j�argi

R= F (Q)=�= f(ai) =� j (ai) 2 F (Q)g

ning nimetame selle hulga elemente reaalarvudeks. De�neerime sellel hulgal liitmise ja korrutamise v~ordustega

(ai) =� +(bi) =� = (ai + bi) =�; (28)

(ai) =� � (bi) =� = (ai � bi) =� : (29)

Saab n�aidata, et ka summa ja korrutis on Cauchy jadad ning et (F (Q)=�;+; �) on korpus. Nullelemendiks selles

korpuses on ekvivalentsiklass, mis koosneb k~oigist nulljadadest.

Q saab sisestada alamkorpusena korpusse F (Q)=� kujutuse f : Q�! F (Q)=�; f(a) = (a; a; a; : : :) =� abil.

Ratsionaalsete elementidega Cauchy jada nimetatakse positiivseks (negatiivseks), kui leidub selline ratsionaalarv" > 0 (" < 0); et alates mingist kohast on k~oik selle jada elemendid suuremad (v�aiksemad) kui ": Iga ratsionaalsete

elementidega Cauchy jada on kas positiivne, negatiivne v~oi nulljada. Kui jada on positiivne (negatiivne), siis ka

46

Page 47: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

mistahes temaga ekvivalentne jada on positiivne (negatiivne). Reaalarvu (ai) =� nimetame positiivseks (negatiiv-seks) kui (ai) on positiivne (negatiivne). Iga reaalarv on kas positiivne, negatiivne v~oi null. De�neerime hulgal

F (Q)=� seose � j�argmiselt:

� � � () � = � v~oi � � � on positiivne.

Seos � osutub lineaarseks j�arjestusseoseks ning saab n�aidata, et kehtivad aksioomid R2 ja R3.

Osutub, et aksioomid R1.{R3. kirjeldavad �uheselt �ara reaalarvude hulga.

Teoreem 10.12 ([9). , lk 50{51] Iga j�arjestatud korpus K, mis rahuldab aksioome R1.{R3., on isomorfne korpu-sega F (Q)=� :

10.3.4. p-aadilised arvud

De�nitsioon 10.13. Norm korpusel (K;+; �) on kujutus k k, mis igale elemendile x 2 K s�aeb vastavusse mitte-

negatiivse reaalarvu kxk nii, et

N1. kxk = 0 siis ja ainult siis, kui x = 0;

N2. kxyk = kxk kyk ;

N3. kx+ yk � kxk+ kyk :

N�aiteks on normiks ratsionaalarvude korpusel absoluutv�a�artus. Osutub, et ratsionaalarvude korpusel saab de-

�neerida ka teisi p~onevaid norme.

Olgu p algarv. Iga t�aisarvu a 6= 0 korral olgu ordp a algarvu p k~orgeim aste, mis jagab arvu a:N�aiteks ord5 35 = 1,

ord5(�250) = 3, ord2 96 = 5, ord2 97 = 0: Loeme, et ordp 0 =1: Paneme t�ahele, et ordp(a1a2) = ordp a1+ordp a2:

Mistahes ratsionaalarvu x = abjaoks, kus a; b 2Z; (a; b) = 1; de�neerime ordp x = ordp a� ordp b: See de�nitsioon

s~oltub vaid ratsionaalarvust x; mitte sellest, milliste t�aisarvude jagatisena x on esitatud, sest kui x = acbc; c 2 Z;

siis ordp(ac)� ordp(bc) = ordp a� ordp b:

De�neerime kujutuse j jp : Q�! Q j�argmiselt:

jxjp =� 1

pordp x ; kui x 6= 0;

0; kui x = 0:

Ehk teisiti: kui esitame ratsionaalarvu x 6= 0 kujul x = pm ab; kus m 2Zja (ab; p) = 1; siis jxjp = 1

pm:

Lause 10.14. Kujutus j jp on norm korpusel Q:

T~oestus. Omaduste N1 ja N2 kontroll on lihtne. N�aitame, et kehtib tingimus N3. Kui x = 0 v~oi y = 0 v~oi

x+ y = 0; siis on t~oestus triviaalne. Seega v~oime eeldada, et x; y ja x+ y on nullist erinevad. Olgu x = abja y = c

d:

Siis x + y = ad+bcbd

ja ordp(x+ y) = ordp(ad+ bc) � ordp b� ordp d: Algarvu p k~orgeim aste, mis jagab kahe arvu

summat ei ole v�aiksem kui v�ahim algarvu p k~orgemaist astmeist, mis jagavad liidetavaid. Seega

ordp(x+ y) = ordp(ad+ bc)� ordp(b)� ordp(d) � min(ordp ad; ordp bc)� ordp b� ordp d

= min(ordp a+ ordp d; ordp b+ ordp c)� ordp b� ordp d

= min(ordp a� ordp b; ordp c� ordp d) = min(ordp x; ordp y):

J�arelikult jx+ yjp = p� ordp(x+y) � max(p� ordp x; p�ordp y) = max(jxjp ; jyjp) ning viimane on � jxjp + jyjp : 2

De�nitsioon 10.15. Normi j jp nimetatakse p-aadiliseks normiks.

Tegelikult t~oestasime me tugevama v~orratuse, kui oli n~outud normi de�nitsiooni tingimuses N3. See v~orratus

v~oetakse j�argmise de�nitsiooni aluseks.

De�nitsioon 10.16. Normi k k korpusel K nimetatakse mittearhimeediliseks, kui iga x; y 2 K korral

kx+ yk � max(kxk ; kyk): (30)

Normi, mis ei ole mittearhimeediline, nimetatakse arhimeediliseks.

47

Page 48: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Seega p-aadiline norm j jp on mittearhimeediline ja absoluutv�a�artus j j on arhimeediline norm korpusel Q:

Asendades de�nitsioonides 10.10 ja 10.11 absoluutv�a�artuse normiga j jp ; saab de�neerida Cauchy jadad, koon-

duvuse ja nulljadad normi j jp suhtes.

Normil j jp on mitmeid huvitavaid omadusi. N�aiteks jada 1; p; p2; p3; : : : koondub nulliks selle normi j�argi.

T~oepoolest, iga " > 0 korral leidub selline N; et iga i > N korral��pi��

p= 1

pi< ": V~oi siis n�aiteks kui vaatleme kera

keskpunktiga a 2 Q ja raadiusega r 2 Q+; D(a; r) =nx 2 Q j jx� ajp � r

o; siis osutub, et mistahes b 2 D(a; r)

korral D(a; r) = D(b; r); s.t. selle kera iga punkt on keskpunkt! T~oepoolest, kui x 2 D(a; r); s.t. jx� ajp � r; siis

jx� bjp = j(x� a) + (a� b)jp � max(jx� ajp ; ja� bjp) � r;

j�arelikult x 2 D(b; r): Vastupidise sisalduvuse saab t~oestada analoogiliselt.

Norme k k ja k k0 nimetatakse ekvivalentseteks, kui jada on Cauchy jada normi k k suhtes parajasti siis, kui

ta on Cauchy jada normi k k0 suhtes.N�aiteks, kui normi j jp de�nitsioonis kirjutada

�1p

�ordp xasemel �ordp x; kus 0 < � < 1; siis saaksime normi,

mis on ekvivalentne normiga j jp : Samuti normid j j� ; 0 < � < 1; on ekvivalentsed absoluutv�a�artusega.

Triviaalse normi all korpusel K peame silmas sellist normi k k ; mille korral k0k = 0 ning iga x 6= 0 korral

kxk = 1:

Kehtib j�argmine teoreem ([10], lk. 3{5).

Teoreem 10.17 (Ostrowski). Iga mittetriviaalne norm korpusel Q on ekvivalentne kas absoluutv�a�artusega v~oimingi p-aadilise normiga j jp ; kus p on algarv.

Edasises olgu p �kseeritud algarv.

Teeme l�abi samasuguse konstruktsiooni nagu Cantori meetodi korral, ainult selle vahega, et absoluutv�a�artuse

asemel kasutame p-aadilist normi.

Olgu Fp(Q) k~oigi selliste ratsionaalarvujadade (ai) hulk, et iga " > 0 korral leidub selline N 2 N; et jai � ajjp <"; kui i; j > N (s.t. Fp(Q) on Cauchy jadade hulk normi j jp suhtes). De�neerime hulgal Fp(Q) seose � j�argmiselt:

(ai)� (bi)() (ai � bi) on nulljada normi j jp suhtes.

J�allegi � on ekvivalentsusseos. T�ahistame faktorhulga selle seose j�argi

Qp = Fp(Q)=�=n(ai) =� j (ai) on Cauchy jada normi j jp suhtes

o:

HulgalQp de�neerime liitmise ja korrutamise j�alle v~ordustega (28) ja (29) ning hulk Qp osutub nende tehete suhtes

korpuseks. Selle korpuse elemente nimetame p-aadilisteks arvudeks.Iga x 2 Q korral t�ahistagu (x) Cauchy jada, mille k~oik komponendid on v~ordsed arvuga x: On ilmne, et

(x) � (x0) siis ja ainult siis, kui x = x0: Jada (0) ekvivalentsiklassi t�ahistame lihtsalt 0: Korpus Q on isomorfne

korpuse Qp alamkorpusega, mis koosneb k~oigist ekvivalentsiklassidest (x) =�; x 2 Q:Ekvivalentsiklassi a = (ai) =� normiks jajp loeme limi!1 jaijp : Saab n�aidata, et see piirv�a�artus eksisteerib.

Osutub, et nii de�neerides saame t~oepoolest normi korpusel Qp; s.t. on rahuldatud aksioomid N1.{N3.

Teoreem 10.18 ([10). , lk. 11{12] Igal ekvivalentsiklassil a 2 Qp; mille korral jajp � 1; on t�apselt �uks esindaja(ai) ; kus ai 2Z; mis rahuldab tingimusi

1. 0 � ai < pi iga i 2 N korral;

2. ai � ai+1 (mod pi) iga i 2 N korral.

Oletame, et p-aadiline arv a ei rahulda v~orratust jajp � 1: Olgu jajp = pm; m 2 N. Korrutades arvu a arvuga

pm; saame p-aadilise arvu a0 = apm; mis rahuldab tingimust ja0jp � 1: T~oepoolest, ja0jp = japmjp = jajp jpmjp =

pm 1pm

= 1: Kui klassi a0 tingimusi 1. ja 2. rahuldavaks esindajaks on jada (a0i) ; siis klassi a = a0p�m esindajaks on

jada (ai) ; kus ai = a0ip�m:

Esitame n�u�ud iga a0i kui p-nds�usteemi arvu, s.t.

a0i = b0 + b1p+ b2p2 + : : :+ bi�1p

i�1;

kus bj 2 f0; 1; : : : ; p� 1g : Tingimus a0i � a0i+1 (mod pi) t�ahendab seda, et

a0i+1 = b0 + b1p+ b2p2 + : : :+ bi�1p

i�1 + bipi;

48

Page 49: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

kus bi 2Z: Kuna 0 � a0i+1 < pi+1; siis 0 � bi < p: J�arelikult iga i korral ai = a0ip�m = b0p

�m + : : :+ bi�1pi�1�m:

Jada (ai) ; mis esindab arvu a; v~oib seega esitada kujul

a =b0

pm+

b1

pm�1+ : : :+

bm�1

p+ bm + bm+1p+ bm+2p

2 + : : : : (31)

(Jada (ai) on selle v~orduse paremal poolel oleva l~opmatu summa osasummade jada.) Saadud p-aadilise arvu esitus

on teatud m�a�aral sarnane reaalarvu esitusega l~opmatu k�umnendmurruna: p-aadilisel arvul on ka l~opmata palju

numbreid b0; b1; b2; : : : ; kusjuures teatud kohast vasakul pool on neid l~oplik arv ja paremal pool l~opmata palju.

V~ordluseks: reaalarvu b0b1 : : : bm�1bm; bm+1bm+2 : : : v~oib esitada kujul

b0

(10�1)m +

b1

(10�1)m�1

+ : : :+bm�1

(10�1)1+ bm + bm+110

�1 + bm+2

�10�1

�2+ : : : :

p-aadiliste arvudega saab teha tehteid �usna analoogiliselt k�umnendmurdudega. Toome siin m~oned n�aited kor-

puses Q7 (erinevalt k�umnendmurdudest liigutakse laenamisel, korrutamisel jne. vasakult paremale):

3+6� 7+2� 72 + : : : 2� 7�1 + 0� 70 + 3� 71 + : : :

�4+5� 7+1� 72 + : : : �4� 7�1 + 6� 70 + 5� 71 + : : :

5+4� 7+4� 72 + : : : 5� 7�1 + 0� 70 + 4� 71 + : : :

1� 7+4� 72 + : : :

3� 72 + : : :

5+5� 5+4� 72 + : : :

1+2� 7+4� 72 + : : : j3 + 5� 7+1� 72 + : : :

1+6� 7+1� 72 + : : :j5 + 1� 7+6� 72 + : : :

3� 7+2� 72 + : : :

3� 7+5� 72 + : : :

4� 72 + : : :

4� 72 + : : :

Lemma 10.19. Olgu K korpus ja k k norm korpusel K: Kui q 2 K ja kqk < 1; siis

1 + q + q2 + : : : =1

1� q: (32)

Lisaks eespoolmainituile on p-aadilistel arvudel ja reaalarvudel teisigi sarnaseid omadusi.

Teoreem 10.20. p-aadiline arv a =P1

i=�m aipi 2 Qp on ratsionaalarv parajasti siis, kui tema numbrite jada (ai)

on mingist kohast alates perioodiline.

N�aide 10.21. Esitame 3-aadilise arvu

a = 1 + 2 � 3 + 2 � 32 + 33 + 2 � 34 + 35 + 2 � 36 + 37 + : : : = 1 + 2 � 3 + (2 � 32 + 33)

ratsionaalarvuna. Kasutades valemit (32) saame, et

a = 1 + 2 � 3 + 2 � 32 + 33

1� 32= 7 +

45

�8 =11

8:

P�u�uame ka, vastupidi, esitada ratsionaalarvu 118esitada 3-aadilisena. Selleks esitame 11 ja 8 3-aadilisel kujul:

11 = 2 + 0 � 3 + 1 � 32 ja 8 = 2 + 2 � 3: 118on siis nende jagatis:

2 + 0� 3 + 1� 32 2 + 2� 3

2 + 2� 3 1 + 2� 3 + 2� 32 + 1� 33 + � � �1� 3

1� 3 + 2� 32 + 1� 33

1� 32 + 1� 33 + 2� 34 + 2� 35 + � � �1� 32 + 1� 33 + 2� 34

2� 33 + 0� 34 + 2� 35 + � � �2� 33 + 2� 34

1� 34 + 1� 35 + � � �

49

Page 50: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

10.4. Reaalarvude valla laiendamine

�Uleminekul naturaalarvude hulgalt t�aisarvude hulgale me t�aiendasime hulka N nii, et osutuks v~oimalikuks

v~orrandite a + x = b lahendamine. Minnes t�aisarvudelt �ule ratsionaalarvudele konstrueerisime sellised objektid,

mille abil saab lahendada t�aisarvuliste kordajatega v~orrandeid ax = b. Kui vaatleme reaalarvude hulka, siis paneme

t�ahele, et ka �ule selle hulga leidub algebralisi v~orrandeid (s.t. v~orrandeid kujul f(x) = 0; kus f(x) on reaalarvuliste

kordajatega pol�unoom), mis pole lahenduvad. �Uheks lihtsamaks selliseks v~orrandiks on v~orrand x2 + 1 = 0. Nagu

algebra p~ohikursuses n�aidatud, saab konstrueerida kompleksarvude korpuse C , mis sisaldab reaalarvude korpust

ja �ule mille see v~orrand on lahenduv (lahendiks on imaginaar�uhik i). Seejuures \C ei sisalda midagi liigset", s.t.

korpusel C ei ole reaalarvude korpust alamkorpusena sisaldavaid p�arisalamkorpusi, �ule mille v~orrand x2 + 1 = 0

oleks lahenduv. Veelgi enam, kehtib j�argmine teoreem.

Teoreem 10.22. Kompleksarvude korpus C on isomor�smi t�apsuseni ainus minimaalne korpus, mis sisaldab alam-korpusena reaalarvude korpust ja �ule mille v~orrand x2 + 1 = 0 on lahenduv.

Tuleb aga v�alja, et �ule kompleksarvude korpuse ei ole mitte ainult v~orrand x2+ 1 = 0 lahenduv, vaid tegelikult

on lahenduvad juba k~oik algebralised v~orrandid (selle kohta �oeldakse ka, et korpus C on algebraliselt kinnine).

Teoreem 10.23 (Algebra p~ohiteoreem.). Igal mittekonstantsel pol�unoomil �ule korpuse C on olemas juur selleskorpuses.

50

Page 51: New AR - utmath.ut.ee/kursused/arvuteooria/kon.pdf · 2002. 2. 12. · uhisk ordne) ja u 2 U (R), siis k du ja b suurim uhistegur (v ahim uhisk ordne). T eiste s ~ onadega, suurim

Indeks

algarv, 8

Mersenne'i, 19

algarvukaksikud, 9

algjuur, 26

algtegureiks lahutus, 6

assotsieeritud elemendid, 3

Cauchy jada, 46

Dedekindi l~oige, 45

Eratosthenese s~oel, 8

Eukleidese algoritm, 4

Euleri funktsioon, 16

Euleri kriteerium, 37

faktorring, 32

Gaussi ruutvastavuss�a�adus, 39

Goldbachi probleem, 10

j�a�agiklass, 12

j�a�agiklassikorpus, 14

j�a�agiklassiring, 14

Jacobi s�umbol, 41

jagaja, 3

jagajate arv, 19

jagajate summa, 19

jagamine, 3

jagatiste korpus, 44

kaaselemendid, 31

kongruents

lineaar-, 20

ruut-, 20, 37

tundmatut sisaldav, 20

kongruentsi lahend, 20

kongruentsus, 12

kordne, 3

korpuse

elemendi juur, 35

karakteristika, 30

laiend, 30

multiplikatiivne r�uhm, 27

primitiivne element, 31

l~oplik korpus, 30

Legendre'i s�umbol, 37

M�obiuse funktsioon, 18

mitteruutj�a�ak, 37

moodul, 12

naturaalarvu standardkuju, 7

norm, 47

p-aadiline, 47

arhimeediline, 47

mittearhimeediline, 47

nulljada, 46

p-aadiline arv, 48

p�o�oratavate elementide r�uhm, 3

pol�unoomi lahutuskorpus, 32

reaalarvude hulk, 45

ruutj�a�ak, 37, 41

suurim �uhistegur, 3

t�aisosa

alumine, 10

t�aiuslik arv, 19

taandamisega poolr�uhm, 43

taandumatu element, 3

tegur, 3

teoreem

algebra p~ohi-, 50

aritmeetika p~ohi-, 6

Dirichlet', 9

Euleri, 17

Fermat' suur, 11

Fermat' v�aike, 18

Gaussi, 17

Hiina j�a�agi-, 21

T�seb~o�sevi, 9

vahede r�uhm, 44

vahim �uhiskordne, 3

�uhejuur, 35

primitiivne, 35

51