Alkuluvut
Alkuluvut ovat lukuja, jotka ovat jaollisia vain ykkösellä ja itsellään. Alkulukujen ominaisuuksia hyödynnetään usein esimerkiksi kryptografiassa.
Määritelmä ja esimerkkejä
Alkuluku on positiivinen kokonaisluku, joka on jaollinen ilman jakojäännöstä vain ykkösellä ja itsellään. Luku 1 ei itse ole alkuluku. Pienin alkuluku on kaksi – se on jaollinen ilman jakojäännöstä ykkösellä ja kakkosella. Se on myös ainoa alkuluku, joka on parillinen. Kaikki muut alkuluvut ovat parittomia, koska jokainen muu parillinen luku on jaollinen ykkösen ja itsensä lisäksi myös kakkosella.
Muutamia ensimmäisiä alkulukuja: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…
Alkulukuihin liittyy aritmetiikan peruslause, jonka mukaan jokainen ykköstä suurempi kokonaisluku voidaan jakaa alkutekijöiden tuloksi.
Testaa, onko luku alkuluku
Alkulukujen ominaisuuksia
- Alkulukuja on äärettömän monta. Todistus löytyy artikkelista ristiriitatodistus.
- Jokaiselle kokonaisluvulle z>1 pätee, että välillä ]z, 2z[ on ainakin yksi alkuluku. Esimerkki: kun z = 2, välinä on ]2, 4[. Ainoa kokonaisluku tällä välillä on kolme, ja se on alkuluku. Kun z = 5, saadaan väli ]5, 10[ eli luvut 6, 7, 8, 9. Luku 7 on alkuluku. Samoin korkeammilla z:n arvoilla.
- Mersennen alkuluku on alkuluku, joka on yhtä pienempi kuin jokin kakkosen kokonaislukupotenssi. Mersennen alkuluvulla M on siis muoto M = 2z − 1, missä z on jokin positiivinen kokonaisluku. Esimerkkinä alkuluku 3, koska 22 − 1 = 3, tai 7, koska 23 − 1 = 7.
- Suurimmat tunnetut alkuluvut ovat yleensä juuri Mersennen alkulukuja. Esimerkiksi 23. elokuuta 2008 löydettiin Mersennen alkuluku M43112609, jossa alaindeksi kertoo eksponentin z. Kyseessä on siis alkuluku 243112609 − 1, jossa on 12 978 189 numeroa ja joka oli tuolloin suurin tunnettu alkuluku.
Jono ilman alkulukuja
Voidaan löytää mielivaltaisen pitkä äärellinen jono peräkkäisiä positiivisia kokonaislukuja, joiden joukossa ei ole yhtään alkulukua. Tällaisella jonolla voi olla muoto k!+2, k!+3, …, k!+k, ja siinä on k − 1 peräkkäistä yhdistettyä lukua (huutomerkki tarkoittaa kertomaa).
Esimerkiksi kun k = 6, saamme viisi peräkkäistä yhdistettyä lukua: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Nämä luvut ovat jaollisia järjestyksessä kahdella, kolmella, neljällä, viidellä ja kuudella, koska luku 6! = 720 on varmasti jaollinen kaikilla näillä luvuilla, sillä se on syntynyt niiden tulona: 6! = 6 · 5 · 4 · 3 · 2. Jos luku 720 on jaollinen kolmella, myös luvun 720 + 3 täytyy olla jaollinen kolmella. Samoin muilla luvuilla.
Fermat’n pieni lause
Jokaiselle alkuluvulle p ja jokaiselle kokonaisluvulle z pätee, että luku zp − z on jaollinen alkuluvulla p.
Esimerkki: otetaan alkuluku p = 3 ja kokonaisluku z = 4. Lasketaan luvun 43 − 4 arvo. Se on 60. Toisaalta 60/3 = 20, joten kolme jakaa luvun 60 ilman jakojäännöstä, mikä on Fermat’n lauseen mukaista. Toinen esimerkki: p = 7, z = 10. Lasketaan välitulos 107 − 10 = 9999990 ja jaetaan se seitsemällä: 9999990/7 = 1428570. Jako meni taas tasan.
Ratkaisemattomia kysymyksiä
Alkulukuihin liittyy monia tunnettuja otaksumia, joita ei ole (vuonna 2011) vielä onnistuttu todistamaan eikä kumoamaan. Kaksi tunnetuinta ovat:
- Alkulukukaksosia on äärettömän monta: alkulukukaksoset ovat lukupari (z, z + 2), jossa molemmat luvut ovat alkulukuja. Esimerkiksi (3, 5) tai (29, 31). Kysymys kuuluu, onko tällaisia alkulukukaksosia äärettömän monta. Oletetaan, että on, mutta todistusta ei ole.
- Riemannin hypoteesi: Riemannin zeta-funktion kaikkien epätriviaalien nollakohtien reaaliosa on
