Sanna Ranto, LUKUTEORIA JA ALGEBRA
Versio 1, 1.11.2003
LUKUTEORIA
 

Jaollisuus ja alkuluvut

Kokonaislukujen joukko on Z = {0,1,2,...}.

Jos kokonaisluku a on jaollinen kokonaisluvulla b, toisin sanoen on olemassa sellainen kokonaisluku c, että a = bc, merkitään b | a. Tällöin sanotaan, että b jakaa luvun a, b on luvun a tekijä tai a on luvun b monikerta. Jos a ei ole luvun b monikerta merkitään b /| a.

Esimerkki. 2 | 10, (-3) | 9, 5 /| 11.

Jaollisuudella on seuraavat yksinkertaiset ominaisuudet:

     (a)   1 | a  A a  (- Z
     (b)   a | a  A a  (- Z
     (c)   jos a | b ja b | a, niin a = b
     (d)   jos a | b ja b | c, niin a | c
     (e)   jos a | b ja a | c, niin a | (ub + vc) kaikilla u,v  (- Z

Todistetaan kohta (e) ja jätetään muiden kohtien miettiminen harjoitukseksi. Oletetaan, että a | b ja a | c, silloin on olemassa sellaiset luvut r ja s, että ub + vc = u(ar) + v(as) = a(ur + vs), joten a | (ub + vc).

Määritelmä. Kokonaislukua p > 1, jonka ainoat tekijät ovat 1 ja p, sanotaan alkuluvuksi. Muita kokonaislukuja sanotaan yhdistetyiksi luvuiksi.

Alkulukujen joukosta käytetään merkintää P, siis

P =  {2,3,5,7,11, 13,17,19,23, 29,31,37,...}.

Lause. Alkulukuja on äärettömän monta.

Todistus. Tehdään vastaoletus, että p1,...,pk ovat kaikki alkuluvut. Muodostetaan luku n = p1 p2 ... pk + 1. Koska alkulukuja ylipäänsä on olemassa, on n > 1 ja täten se voidaan hajottaa tekijöihin. On siis olemassa sellainen alkuluku q, että q | n. Koska p1 , ... , pk ovat kaikki alkuluvut, niin voidaan olettaa, että q = pi. On olemassa sellainen kokonaisluku c, että p1...pk + 1 = cpi, siis 1 = pi(c - p1...pi-1pi+1...pk). Koska c - p1 ... pi-1 pi+1...pk  (- Z niin pi | 1, mikä on mahdotonta, sillä pi on alkuluku. []


Linkit:
Jakoalgoritmi