Tehtävä 3.4. Jaa luvut 2000, 2001, 2002 ja 2003 alkutekijöihinsä.
Ratkaisu
Ratkaisua alkutekijäjakoon voidaan lähteä hakemaan yksinkertaisesti kokeilemalla millä alkuluvuilla annetun luvun voi jakaa niin, että jako menee tasan ja kuinka monta kertaa kullakin alkuluvulla voidaan jakaa.
Aloitetaan kakkosesta, joka on alkuluku, ja jaetaan annettu luku sillä. Jos jako menee tasan (eli jakojäännös on 0), jakaa luku 2 annetun luvun. Kokeillaan jakotuloksen jakamista kakkosella niin kauan kuin jako menee tasan. Kun jako ei enää mene tasan, yritetään jakaa luvulla 3. Jatketaan samalla idealla kunnes alkutekijäesitys on löydetty.
Katso satasta pienemmät alkuluvut tehtävästä 3.2.
Edellisessä tehtävässä 3.3 osoitettiin, että jos positiivinen kokonaisluku 
ei ole alkuluku, niin on olemassa alkuluku
p
siten, että 
ja 
.
Kurssin alussa käsiteltyjen logiikan säännön 
mukaan tämä on yhtäpitävää sen kanssa, että jos tällaista alkulukua
p
ei ole olemassa, on luvun
n
oltava alkuluku. Tästä seuraa, että jaettaessa lukua
n
alkutekijöihin, ei sitä tarvitse yrittää jakaa lukua 
suuremmilla alkuluvuilla. Esimerkiksi, jos jaetaan lukua 132 alkutekijöihin, ei eri alkuluvuilla jakamista tarvitse yrittää lukua 
eli lukua 11 suuremmilla alkuluvuilla.
Siirrytään nyt itse tehtävän ratkaisemiseen. Ensinnäkin
Luku 2001 ei parittomana selvästikään ole jaollinen luvulla 2, mutta kolmosella kylläkin, sillä luvun numeroiden summa 
on jaollinen kolmosella (tämä on yleisesti tunnettu kolmosella jaollisuuden testi). Laskemalla jakolasku saadaan 
.
Mikäli tekijä 667 on yhdistetty luku, on sillä oltava alkutekijä, joka on korkeintaan 
.
Riittää siten etsiä alkutekijätekijää, joka on pienempi 25. Jos tällaista ei löydy, on 667 alkuluku ja silloin luvun 2001 alkutekijäesitys on 
.
Kokeilemalla havaitaan kuitenkin, että luku 667 on jaollinen luvulla 23 ja että 
.
Näin ollen 
.
Edellä esitettyjä ideoita toistamalla saadaan, että 
.
Tutkitaan sitten lukua 2003. Koska 
,
riittää yrittää jakaa luku 2003 lukua 45 pienemmillä alkuluvuilla. Kokeilemalla jakamista kaikilla tällaisilla alkuluvuilla huomataan, ettei jako mene milloinkaan tasan. Siispä 2003 on alkuluku.
Tutkitaan vielä ylimääräisenä tehtävänä lukua 2006. Koska luku 2006 on parillinen, se on jaollinen ainakin kakkosella: 
.
Nyt täytyy edelleen yrittää jakaa luku 1003 alkutekijöihin eli yrittää jakaa lukua 32 (
) pienemmillä alkuluvuilla. Havaitaan, että 17 jakaa luvun 1003, ja siis 
.
Näin ollen 
.
Lisätietoja.
Korkeintaan yksi luvun
n
alkutekijä
q
voi olla suurempi kuin 
.
Tästä seuraa, että kyseinen luku
q
saadaan tulokseksi kun
n
jaetaan kaikilla sen lukua 
pienemmillä alkutekijöillä. Mieti miksi edellinen pätee.
Lisätehtävä.
Jos olet kiinnostunut ohjelmoinnista, kokeile kirjoittaa ohjelma, joka jakaa annetun positiivisen kokonaisluvun alkutekijöihinsä. Keksi erilaisia toteutuksia alkutekijöiden etsimiselle ja kokeile mikä toteutuksista näyttäisi olevan nopein. Kokeile kirjoittaa ohjelma vaikkapa graafiselle laskimellesi tai tee siitä nettiversio. Nettiversiosta voit tehdä joko selaimessa suoritettavan käyttämällä JavaScriptiä tai palvelimella suoritettavan hyödyntämällä jotain palvelinpuolen ohjelmointikieleltä, kuten PHP, JSP, Perl, Python tai ASP.
• Alkutekijöihin jako: http://en.wikipedia.org/wiki/Integer_factorization
• Mathematica: http://mathworld.wolfram.com/PrimeFactorization.html
[Opiskelutehtäviä 3]