theorem]Acknowledgement theorem]Algorithm theorem]Axiom theorem]Case theorem]Claim theorem]Conclusion theorem]Condition theorem]Conjecture theorem]Corollary theorem]Criterion theorem]Definition theorem]Example theorem]Exercise theorem]Lemma theorem]Notation theorem]Problem theorem]Proposition theorem]Remark theorem]Solution theorem]Summary

1  Lukuteoriaa

1.1  Jaollisuus

Tässä luvussa liikutaan lähinnä kokonaislukujen joukossa \mathbbZ = {...,-5,-4,-3,-2,-1,0,1,2,3,4...}.

Jokaisessa epätyhjässä ei-negatiivisten kokonaislukujen osajoukossa on pienin luku.

Tämä aksiooma kuulostaa intuitiivisesti selvältä. Se ei kuitenkaan ole voimassa esimerkiksi rationaaliluvuille: esimerkiksi joukossa {1/n|  n Î \mathbbN} ei ole pienintä alkiota.

Ala-asteella tehdään paljon jakolaskuja. Esimerkiksi [4509/ 31] = 145  [14/ 31], tai jakolaskun tuloksena on 145 ja jakojäännöksenä 14. Äskeinen lasku voidaan ilmoittaa myös muodossa

4509 = 31·145+14.

Tämä idea voidaan ilmoittaa myös muodollisesti:

[Jakoyhtälö]Olkoot a,b Î \mathbbZ, b > 0. Tällöin on olemassa yksikäsitteiset luvut q,r Î \mathbbZ siten, että

a = bq+r\text ja 0 £ r < b.

Olkoot a,b Î \mathbbZ, b > 0. Tarkastellaan kaikkia muotoa a-bx olevia kokonaislukuja, missä x on kokonaisluku. Osoitetaan ensin, että jotkin näistä kokonaisluvuista ovat ei-negatiivisia.

1. Jos a ³ 0, niin silloin a-b·0 = a on ei-negatiivinen. Siis a-bx on ei-negatiivinen, kun x = 0.

2. Jos a < 0, niin silloin a-b·a = a(1-b) on ei-negatiivinen, koska sekä a ja 1-b ovat negatiivisia. Siis a-bx on ei-negatiivinen luvulle x = a.

Siten joukko S = {a-bx  |  x Î \mathbbZ ja a-bx ³ 0} on epätyhjä.

Aksiooman mukaan joukossa S on pienin alkio. Olkoon r tämä pienin alkio. Koska r Î S, niin r on muotoa r = a-bx jollekin x Î \mathbbZ, ja merkitään x = q. Siis

r = a-bq\text tai a = bq+r.

Koska r Î S, niin r ³ 0. Todistetaan nyt, että r < b.

Oletetaan, että r ³ b. Silloin r-b ³ 0, joten

0 £ r-b = (a-bq)-b = a-b(q+1).
Koska a-b(q+1) on ei-negatiivinen, se kuuluu joukkoon S. Mutta koska b on positiivinen, r-b > r. Siispä
a-b(q+1) = r-b < r,
mikä osoittaisi, että a-b(q+1) olisi pienempi kuin r. Mutta r on joukon S pienin alkio, ja näin on saatu ristiriita. Siispä on oltava r < b.

Lopuksi meidän täytyy osoittaa, että q ja r ovat ainoat tällaiset luvut (eli joille a = bq+r), eli että q ja r ovat yksikäsitteisiä. Tämän todistamiseksi oletetaan, että olisi olemassa toiset luvut q1 ja r1, joille myös pätisi a = bq1+r1, 0 £ r1 < b.

Joko r ³ r1 tai r < r1. Oletetaan, että r ³ r1. Vähentämällä kaksi yhtälöä toisistaan saamme

\hline0 = bq-bq1+r-r1