Alkuluku
Alkuluvut \[\big\{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dotsc \big\}\] ovat lukua \(1\) suurempia luonnollisia lukuja, jotka eivät ole jaollisia millään muulla luvulla kuin yhdellä ja itsellään. Ainoa parillinen, ja samalla pienin, alkuluku on \(2\). Kaikki muut alkuluvut ovat parittomia, sillä jos ne olisivat parillisia, ne olisivat jaollisia kahdella. Luonnollisia lukuja, jotka ovat suurempia kuin yksi, mutta eivät ole alkulukuja, kutsutaan yhdistetyiksi luvuiksi. Jokainen yhdistetty luku voidaan esittää alkulukujen tulona, missä alkuluvut kirjotetaan kasvavassa järjestyksessä.
| Alkulukuja | Yhdistettyjä lukuja |
|---|---|
| \(2=1\cdot 2\) | \( 6 = 2 \cdot 3\) |
| \(3=1\cdot 3\) | \( 8 = 2 \cdot 2 \cdot 2 = 2^3\) |
| \(5=1\cdot 5\) | \( 24 = 2 \cdot 2 \cdot 2 \cdot 3 = 2^3 \cdot 3\) |
| \(7=1\cdot 7\) | \( 2013 = 3 \cdot 11 \cdot 61\) |
Geometrisesti alkuluvut voidaan ajatella pinoina, joita ei voida jakaa tasaisesti. Esimerkiksi \(12\) asiaa voidaan jakaa esimerkiksi kolmeen yhtä korkeaan pinoon, mutta \(11\) asiaa on mahdotonta jakaa tasakokoisiin pinoihin. Niinpä luku 11 on alkuluku.
Alkulukujen historia ulottuu antiikin Kreikkaan noin vuoteen 300 eaa., jolloin matemaatikko Eukleides todisti alkulukuja olevan äärettömän monta. Eukleideen todistus on yksinkertainen ja nerokas. Oletetaan, että alkulukuja \(p_1,\dotsc,p_n\) on vain äärellisen monta. Koska yksikään niistä ei jaa kokonaislukua \[p = 1+p_1 \cdot p_2 \dotsb p_n,\] on luvulla \(p\) oltava alkutekijä, joka ei ole mikään alkuluvuista \(p_1,\dotsc,p_n\). Tämä on ristiriita, joten alkulukujen määrän oltava ääretön.
Sivun alussa on kirjoitettuna 10 ensimmäistä alkulukua. Alkulukujen esiintymistiheyttä voidaan arvioida alkulukulauseella \[\pi(n) \sim \frac{n}{\ln(n)},\quad n\to\infty,\] missä merkintä \(\pi(n)\) tarkoittaa lukua \(n\) pienempien tai yhtäsuurten alkulukujen määrää. Esimerkiksi lukua \(10\) pienempiä alkulukuja on neljä kappaletta ja nämä alkuluvut ovat \(2,3,5,7\). Mitä suuremmista luvuista on kyse, sitä harvemmassa alkulukuja on.
| \(n\) | \(\pi(n)\) | \(\frac{n}{\ln(n)} \,\,\, {\text{(likiarvo)}} \) |
|---|---|---|
| \(10\) (= kymmenen) | \(4\) | \(4.34\) |
| \(10^2 = 100\) (= sata) | \(25\) | \(21.71\) |
| \(10^3 = 1 \, 000\) (= tuhat) | \(168\) | \(144.76\) |
| \(10^4 = 10 \, 000\) | \(1 \, 229\) | \(1 \, 085.74\) |
| \(10^5 = 100 \, 000\) | \(9 \, 592\) | \(8\, 685.89\) |
| \(10^6 = 1 \, 000 \, 000\) (= miljoona) | \(78 \, 498\) | \(72\, 382.41\) |
| \(10^7 = 10 \, 000 \, 000\) | \(664 \, 579\) | \(620\, 420.69\) |
| \(10^8 = 100 \, 000 \, 000\) | \(5 \, 761 \, 455\) | \(5 \, 428 \, 681. 02\) |
| \(10^9 = 1 \, 000 \, 000 \, 000\) (= miljardi) | \(50 \, 847 \, 534\) | \(48 \, 254 \, 842.43\) |
Alkulukujen etsintä
Alkulukuja voidaan etsiä useilla erilaisilla algoritmeilla (joukko toimenpiteitä, joilla saadaan tehtävä tehtyä). Eräs algoritmeista on Eratostheneen seula, jolla voidaan etsiä suhteellisen helposti pieniä alkulukuja. Seulan toimintaperiaate on seuraava:
- Kirjoita lista kaikista luonnollisista luvuilta alkaen luvusta \(2\) ja päättyen luonnolliseen lukuun \(n\), johon etsintä lopetetaan.
- Poista listasta kaikki luvun \(2\) monikerrat. Luvun \(2\) kertotaulu: \(2, 4, 6, 8, 10, 12, 14, 16, \dotsc\)
- Listan seuraava jäljellä oleva luku on alkuluku.
- Poista listasta kaikki edeltävässä vaiheessa löydettyä alkulukua suuremmat luvut, jotka ovat sen monikertoja.
- Toista vaiheita 3. ja 4. niin kauan, että listan seuraava jäljellä oleva luku on suurempi kuin listan suurimman luvun \(n\) neliöjuuri \(\sqrt{n}\).
- Kaikki jäljelle jääneet luvut ovat alkulukuja.
Etsitään malliksi kaikki alkuluvut, jotka pienempiä tai yhtä suuria kuin \(20\). Kirjoitetaan lista kaikista luonnollisista luvuista \(2,\dotsc, 20\).
Poistetaan listasta kaikki luvun kakkosen moninkerrat.
Jäljelle jäävän listan
ensimmäinen alkio \(3\) on alkuluku. Poistetaan listasta kaikki kolmosen moninkerrat poislukien luku \(3\).
Jäljelle jäävän listan
seuraava alkio \(5\) on alkuluku. Koska \(5 > \sqrt{20} \approx 4.5\), niin algoritmi päättyy. Näin ollen kaikki jäljelle jääneet luvut
ovat alkulukuja!
Suurin tunnettu alkuluku tämän sivun kirjoitushetkellä (lokakuu 2020) on \(2^{82 589 933}-1\), joka löydettiin 2018. Tässä luvussa on \( 24 862 048\) numeroa. Tämä luku on 51. tunnettu Mersennen alkuluku, joka tarkoittaa sen olevan muotoa \(2^n-1\), missä \(n\) on alkuluku. Mersennen luvun testaaminen alkuluvuksi tietokoneella on nopeaa Lucasin-Lehmerin testin avulla, ja siksi suurimmat löydetyt alkuluvut ovatkin usein Mersennen alkulukuja.
Avoimia ongelmia
Ehkä tunnetuin alkulukuihin liittyvä avoin kysymys on Riemannin hypoteesi, jonka todistamisesta on amerikkalainen Clay Mathematics Institute luvannut miljoonan Yhdysvaltain dollarin palkinnon. Riemannin hypoteesi liittyy läheisesti alkulukujen esiintymistiheyteen tavalla, joka ei kuitenkaan ole ilmeinen Riemannin hypoteesin väitteestä.
Riemannin hypoteesi. Riemannin zeeta-funktion \(\zeta\) kaikki aidosti kompleksiset (eli ei-reaaliset) nollakohdat ovat kompleksitason suoralla \({\rm Re}(z)=\frac{1}{2}\).
Kun \({\rm Re}(z)> 1\), niin Riemannin zeeta-funktio voidaan esittää summana \[
\zeta(z) = 1 + 2^{-z} + 3^{-z} + \dotsb = \sum_{n=1}^\infty \frac{1}{n^z},
\] joka puolestaan voidaan analyyttisesti jatkaa kaikille kompleksiarvoille \(z\neq 1\). Pisteessä \(z=1\) on yksinkertainen napa, joten Riemannin zeeta-funktio on meromorfinen koko kompleksitasossa.
Esimerkkejä muista hyvin tunnetuista alkulukuja koskevista avoimista ongelmista
| Voidaanko jokainen lukua 2 suurempi parillinen luku esittää kahden alkuluvun summana? | Goldbachin konjektuuri |
| Onko Fibonaccin lukujonossa ääretön määrä alkulukuja? | Fibonaccin alkuluvut |
| Onko olemassa äärettömän monta sellaista alkulukua, joiden etäisyys lähimpään alkulukuun on 2? Toisin sanoen, onko alkulukupareja äärettömän monta? | Alkulukuparit |