Arvude ühistegurid Arvude ühiskordsed Alg- ja kordarvud Jagaja arv, millega antud arv jagub Arvudel on erinev arv jagajaid: Arv 1 jagub ainult iseendaga; Arvud 2, 3, 5 ja 7 jaguvad arvuga 1 ja iseendaga; Arvudel 6, 8 ja 10 on jagajaid neli; Arvul 24 on palju rohkem jagajaid: 1, 2, 3, 4, 6, 8, 12 ja 24; Alg- ja kordarvud Algarv naturaalarv, mis jagub ainult kahe arvuga (arv 1 ja arv ise) Kordarv naturaalarv, millel on rohkem kui kaks jagajat Algarvude tabel koostatatud selleks, sest suuremate arvude korral on raske otsustada, kas arv on alg või kordarv; Arvu tegurid ja kordsed Arvu tegur kõik arvud, millega antud arv jagub; Nt. Number 6 jaguneb arvudega 1, 2, 3 ja 6, st need on arvu 6 jagajad. Kuna 6=16 ja 6=23, siis on arvud 1, 2, 3 ja 6 ka arvu 6 tegurid Arvu tegurid ja kordsed Arvu kordsed kõik need arvud, mis antud arvuga jagunevad; Korrutades omavahel antud arvu
2) - hulk on kinnine liitmise ja korrutamise suhtes. 4. Algarvud. 1) Algarvuks nimetatakse 1-st suuremat naturaalarvu, mis jagub ainult iseenda ja 1-ga. 2) Eratosthenese sõel. a) Nimekiri arvudest 2..N. b) Nimekirjast tõmmatakse maha need arvud, mis on mingi algarvu kordsed. 5. Algarvud. 1) Eukleidese teoreem. a) Teoreem : algarvude hulk on lõpmatu. b) Tõestus : Tähistame p1=2, p2=3, p3=5, ... Oletame vastuväiteliselt, et leidub suurim algarv pn. Vaatleme naturaalarvu a=p1 p2 ... pn + 1. Et a on suurem 1-st, siis peab leiduma algarv millega a jagub. Kuna oletasime, et p1 ... p2 on ainsad algarvud, siis pead leiduma selline i, 1 i n, nii et a jagub pi-ga.
Kuupäev: Tallinn 2011 2 Sisukord 1. Sissejuhatus.......................................................................................................3 2. Uurimustöös esinevate mõistete definitsioonid..................................................4 3. Algarvud ja kordarvud........................................................................................5 3.2. Algarvude tabel...............................................................................................6 4. Arvu tegurid ja kordsed......................................................................................7 5. Jaguvuse tunnused.............................................................................................. 5.1. Jaguvus 2, 5 ja 10-ga.................................................................................. 5.2. Jaguvus 3 ja 9-ga...........................
49 10 a b9a 9 10 37 a4 b b9a 9 1 37 a4 b 5 b46 a //Eukleides // d =1/49 mod 451= 45146 mod 451 = 405 mod 451 Ül2.1 RSA krüptosüsteemis kasutatakse algarvudena p = 101 ja q = 37. Avalik astendaja e = 17. Leia salajane astendaja d. Kas samade algarvude korral oleks e = 5 sobilik avalik astendaja? Põhjenda! Phi(101 * 37) = 3600 = n 17 3600 a b 17 13 a b211a 4 13 212ab b211a 4 1 212ab 4 b847 a d =1/17 mod 3600 = 3600847 mod 3600 = 2753 mod 3600 . gcd(5,3600) = 5
Algarvude tabel 2 131 307 491 691 911 1117 1361 1579 1811 3 137 311 499 701 919 1123 1367 1583 1823 5 139 313 503 709 929 1129 1373 1597 1831 7 149 317 509 719 937 1151 1381 1601 1847 11 151 331 521 727 941 1153 1399 1607 1861 13 157 337 523 733 947 1163 1409 1609 1867 17 163 347 541 739 953 1171 1423 1613 1871 19 167 349 547 743 967 1181 1427 1619 1873 23 173 353 557 751 971 1187 1429 1621 1877 29 179 359 563 757 977 1193 1433 1627 1879 31 181 367 569 761 983 1201 1439 1637 1889 37 191 373 571 769 991 1213 1447 1657 1901 41 193 379 577 773 997 1217 1451 1663 1907 43 197 383 587 787 1009 1223 1453 1667 1913 47 199 389 593 797 1013 1229 1459 1...
[15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil. [16]. Fibonacci arvud. Üldliikme valem ja rakendused. [17]. Lucas` arvud. [18]. Catalani arvud. [19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus. [20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis. [21]. Täistõenäosuse valem. Bayesi reegel. [22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral). [23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid
(t) rangest monotoonsusest järeldub pöördfunktsiooni t=-1(x) olemasolu E * Muutujate vahetus. Kui f x=(t) on rangelt monotoonne hulgal T, kus (T)=X ja (t)D(T), siis f(x)dx=f((t))'(t)dt * Diferentsiaali märgi alla viimine. f(x)dx=F(x)+C f((x))d(x)=F((x))+C * Ositi integreerimine. Kui u(x) ja v(x) on diferentseeruvad f'id hulgal X ja eksisteerib määramata integraal uv'dx, siis eksisteerib ka määramata integraal udv=uv-vdu * Iga nullist erinev täisarv n on esitatav algarvude p astmete korrutisena n=(-1) (n)p1v1pkvk * Iga kahe täisarvu a ja b>0 korral leiduvad täisarvud q ja r, et a=qb+r, kus 0<=r
Ülesanne 1 Aksioom (kreeka keeles axima 'see, mis on vääriline') tähendab üldkeeles väidet, mille tõesuses pole kahtlust. Algarvuks nimetatakse ühest suuremat naturaalarvu, mis jagub vaid arvuga 1 ja iseendaga. Algarvude hulk on lõpmatu. Sajast väiksemad algarvud ((100) = 25) on 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ja 97. Kaksikuteks nimetatakse selliseid algarve, mille vahe on 2, näiteks 101 ja 103 või 1 000 000 007 ja 1 000 000 009. Ei ole teada, kas kaksikuid on lõpmata palju. Aritmeetiliseks keskmiseks nimetatakse arvu, mis saadakse antud arvude summa jagamisel liidetavate arvuga. Näide 1. On antud arvud 3, 4, 5 ja 6.
· Olemegi näidanud, et = ja = . Definitsioon 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. Teoreem (Aritmeerika põhiteoreem) p1 Iga naturaalarvu n > 1 saab esitada algarvude korrutisena (st leiduvad r ja ,..., pr p1 pr nii, et n = ,..., ) ning see esitus on ühene tegurite järjekorra täpsuseni. Teoreem Algarvude hulk on lõpmatu. TÕESTUS p1 p2 p3 p4 · Olgu algarvud tähistatud = 2, = 3, = 5, = 7, . . .
5. Elementaarne arvuteooria ja matemaatilised tõestused Ena mus ees poollahendatud üles andeid kuubuv arvuteooria valdkonda, lis a me veel mõned näited j a mõis ted. D efinits ioon: öeldaks e, et täis arv b jagub täis arvuga a ( a 0 ) kui b= k*a, kus k on täis arv j a tähis tataks e a|b. A ritmeet ika fundamenta alteor eem ehk ühene faktoris eerimis e teoreem: Iga pos itiivne mitt ealgarv n (compos it e) on es itatav algarvude korrutis ena. Tões tus : Et n pole algarv s iis s aame s elle es itada korrutis ena n= a*b, nii et a< n ja b< n. J uhul kui a ja b on algarvud, s iis on teoree m tões tatud, kui aga a või b pole algarv, s iis s aab s elle omakord a es itada kahe täis arvu korrutis ena j ne, kuni tule mus ena s aame algarvud. P rots ess on lõplik kuna igal s aamu l korrutis es olevad tegurid vähenevad. Teoree m
5. Elementaarne arvuteooria ja matemaatilised tõestused Ena mus ees poollahendatud üles andeid kuubuv arvuteooria valdkonda, lis a me veel mõned näited j a mõis ted. D efinits ioon: öeldaks e, et täis arv b jagub täis arvuga a ( a 0 ) kui b= k*a, kus k on täis arv j a tähis tataks e a|b. A ritmeet ika fundamenta alteor eem ehk ühene faktoris eerimis e teoreem: Iga pos itiivne mitt ealgarv n (compos it e) on es itatav algarvude korrutis ena. Tões tus : Et n pole algarv s iis s aame s elle es itada korrutis ena n= a*b, nii et a< n j a b< n. J uhul kui a j a b on algarvud, s iis on teoree m tões tatud, kui aga a või b pole algarv, s iis s aab s elle omakord a es itada kahe täis arvu korrutis ena j ne, kuni tule mus ena s aame algarvud. P rots ess on lõplik kuna igal s aamu l korrutis es olevad tegurid vähenevad. Teoree m
Näitame, et probleeme on vähemalt sama palju, kui reaalarve (veidi keerulisem) Näitame, et reaalarve on lõpmatult rohkem kui täisarve (Cantori üks teoreeme) Cantori teoreem ütleb üldisemalt, et mingi hulga H kõigi alamhulkade hulk on suurema võimsusega kui see hulk H. Poollahenduvus Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. Mõne H jaoks on ülesanne lahenduv: näiteks, kui H on paarisarvude hulk, kui H on algarvude hulk jne, Mõne H jaoks ülesanne ei ole lahenduv: näiteks, kui H on arvude hulk, millele vastavad programmid peatuvad. Poollahenduvus tähendab, et kui X juhuslikult kuulub hulka H, siis me saame seda algoritmiga alati näidata. Kui ei kuulu H-i, siis ei saa alati. Strong AI: "if a machine approaches or supersedes human intelligence, if it can do typically human tasks, if it can apply a wide range of background knowledge and has some degree of self-consciousness" Weak AI:
Sulgudes seisev „Eukleides” tähistab tõestuse autorit ja tihti nimetataksegi seda teoreemi Eukleidese teoreemiks. Meenutame, et algarvud on naturaalarvud, mis jaguvad ainult enda ja ühega – nagu näiteks 2, 3 ja 5. Arvud 4 ja 6 aga pole algarvud, sest ja . Algarvud on mingis mõttes kõikide teiste arvude baasiks. Neid ennast ei saa tegurdada, aga kõik teised arvud võime esitada algarvude korrutisena. Näiteks võime algarvude korrutisena kirjutada ja Üritame lugejat selles teoreemis järgnevalt ka veenda. Meenutame, et arutlust, mis veenaks ka kõige skeptilisemat matemaatikut, nimetatakse tõestuseks ning sisuliselt annamegi siin tõestuse. Tõestus: Alustuseks märgime, et algarve kindlasti leidub – näiteks 2, 3 ja 5 on algarvud ja nii mõnigi veel. Oletame, et oleme leidnud juba erinevat algarvu . Kas leidub mõni veel? Kuidas teda leida?
Jüri oli läbinud 9641 meetrit 3456 detsimeetrit ja 12340 millimeetrit, siis ta peatus ja katkestas jooksu. Mitu sentimeetrit jäi tal 10 kilomeetrist puudu? Vastus: 106 cm 128. raamat on 4 korda kallim kui pastakas, aga pastakas 30 krooni võrra odavam kui raamat. Kui palju maksab raamat ja kui palju pastakas? Vastus: raamat 40 krooni ja pastakas 10 krooni 129. Leia 5 esimese algarvu ja 5 esimese kordarvu summa. Vastus: 2 + 3 + 5 + 7 + 11 = 28 algarvude summa (1 pole algarv ja 2 ainuke paarisarvuline algarv) 4 + 6 + 8 + 9 + 10 = 37 kordarvude summa 130. Ostja arve on 37 krooni. Kuidas saab ta oma ostu eest tasuda ainult 2- kroonistega, kui müüjal pole münte, Vastus: 21 x 2 = 42 krooni ( annab 21 2- kroonist) 42 5 = 37 krooni ( müüja annab 5- kroonise tagasi) 131. Üks kõrvunurk on teisest 480 võrra suurem. Kui suured on need nurgad? Vastus: 1140 ja 660
on vaja võimsamat formaalset käsitlusviisi ja sellele pani aluse G. Frege (1848-1925). Sellist üldistatud lausearvutust nimetatakse tänapäeval predikaatloogikaks või predikaatarvutuseks (predicate calculus). Vaatleme nt sarnaste lausete hulka: 2 on algarv, 3 on algarv, 4 on algarv jne. Traditsioonilise loogika põhjal saab öelda, et kõigis neis lausetes on subjektideks mingi konkreetne naturaalarv n naturaalarvude hulgast N (n∈ N), ning subjektile preditseeritakse kuuluvus algarvude hulka P, või teisiti öeldes, subjektile preditseeritakse algarvuks olemise omadus. Predikaatloogikas saab kõik äsjases näites toodud laused kirja panna ühel üldistatud kujul: n on algarv, kus n∈ N. See üldistatud kujul esitatud objekt ei ole lause, sest sellele ei anna interpretatsioon tõeväärtust enne, kui fikseeritakse muutuja n väärtus. Vastavalt igale konkreetsele naturaalarvule saame objektist „n on algarv” lause, millel on tõeväärtus, nt n = 2
vaja võimsamat formaalset käsitlusviisi ja sellele pani aluse G. Frege (1848-1925). Sellist üldistatud lausearvutust nimetatakse tänapäeval predikaatloogikaks või predikaatarvutuseks (predicate calculus). Vaatleme nt sarnaste lausete hulka: 2 on algarv, 3 on algarv, 4 on algarv jne. Traditsioonilise loogika põhjal saab öelda, et kõigis neis lausetes on subjektideks mingi konkreetne naturaalarv n naturaalarvude hulgast N (n N), ning subjektile preditseeritakse kuuluvus algarvude hulka P, või teisiti öeldes, subjektile preditseeritakse algarvuks olemise omadus. Predikaatloogikas saab kõik äsjases näites toodud laused kirja panna ühel üldistatud kujul: n on algarv, kus n N. See üldistatud kujul esitatud objekt ei ole lause, sest sellele ei anna interpretatsioon tõeväärtust enne, kui fikseeritakse muutuja n väärtus. Vastavalt igale konkreetsele naturaalarvule saame objektist ,,n on algarv" lause, millel on tõeväärtus, nt n = 2
•Iga täisarv loomulikult ei presenteeri üht algoritmi, küll aga vastupidi •Saab näidata, et probleemide hulk on samas suurusjärgus reaalarvude hulgaga •Cantori teoreem matemaatikas näitab, et reaalarve on rohkem kui täisarve. ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 27 Poollahenduvus •Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. .Mõne H jaoks on ülesanne lahenduv: näiteks, kui H on paarisarvude hulk, kui H on algarvude hulk jne, .Mõne H jaoks ülesanne ei ole lahenduv: näiteks, kui H on arvude hulk, millele vastavad programmid peatuvad. •Poollahenduvus tähendab, et kui X juhuslikult kuulub hulka H, siis me saame seda algoritmiga alati näidata. Kui ei kuulu H-i, siis ei saa alati. •Peatumisprobleemi puhul: paneme X-le vastava programmi käima ja kui ta peatub, siis loomulikult teame, et ta kuulub hulka H .Kui ta aga ei peatu, siis meil ei ole kindlat viisi aru saada, et ta ei kuulu hulka H.
annaabi.ee 
