Alkuluku

Alkuluku on lukua 1 suurempi luonnollinen luku, joka ei ole jaollinen muilla positiivisilla kokonaisluvuilla kuin yhdellä ja itsellään. Alkulukujen joukkoa merkitään kirjaimella P. Pienimmät kymmenen alkulukua ovat 2, 3, 5, 7, 11, 13, 17, 19, 23 ja 29. Alkulukuja on numeroituvasti ääretön määrä. Lukua 1 suurempaa kokonaislukua, joka ei ole alkuluku, sanotaan yhdistetyksi luvuksi. Lukua 1 ei lueta alkuluvuksi, vaikka se onkin jaoton luku, jotta alkulukuja koskevien matemaattisten lauseiden muotoilu olisi yksinkertaisempaa.
Alkulukujen laskemiseksi on olemassa useita algoritmeja. Yksi yksinkertaisimmista algoritmeista on Eratostheneen seula, joskin se on työläs ja hidas suurten alkulukujen etsimiseen.
Kaksi lukua ovat alkulukuja toistensa suhteen eli keskenään jaottomia, jos niillä ei ole ykköstä suurempia yhteisiä tekijöitä.
Historiaa.
1600-luvulla elänyt ranskalainen matemaatikko Pierre de Fermat tarkasteli ensimmäisiä lukuja epänegatiivisten kokonaislukujen "n" funktiossa
 formula_1
ja päätteli virheellisesti, että kaikki näin saadut luvut eli Fermat’n luvut (3, 5, 17, 257, 65537, …) olisivat alkulukuja.
Luonnolliset luvut tulona.
Jokainen luonnollinen luku paitsi formula_2 voidaan jakaa alkulukutekijöihin eli kirjoittaa alkulukujen tulona. Voidaan osoittaa, että tämä tekijöihin jako on yksikäsitteinen lukuun ottamatta tekijöiden järjestystä (aritmetiikan peruslause). Voidaan esimerkiksi kirjoittaa
formula_3.
Tekijöihinjakoa, jossa alkulukutekijät ovat suuruusjärjestyksessä, kutsutaan kanoniseksi alkulukuhajotelmaksi.
Ominaisuuksia.
Määrän äärettömyys.
Eukleides antoi vanhimman tunnetun todistuksen alkulukujen määrän äärettömyydelle. Todistus on lyhyesti seuraava:
Ota äärellinen joukko perättäisiä alkulukuja. Kerro ne kaikki keskenään ja lisää yksi. Tulos ei ole jaollinen valitun joukon alkuluvuilla, koska jakojäännökseksi jää tällöin yksi. Niinpä sen täytyy olla joko uusi alkuluku tai jaollinen alkuluvulla, joka ei kuulunut valittuun joukkoon.
Todistus formaalisti.
Väite: alkulukuja on äärettömän monta. 
Tehdään vastaoletus: alkulukujen joukko on äärellinen. 
Olkoon formula_19 kaikki alkuluvut sisältävä joukko siten, että formula_20, missä formula_21 ja formula_22. Tällöin alkulukuja on formula_8 kappaletta. Olkoon 
formula_24
Ilmiselvästi formula_25. Nyt formula_26 kaikilla formula_27, joten formula_28 kaikilla formula_27. Täten formula_30 on alkuluku tai on olemassa alkuluku formula_31 siten, että formula_32 ja formula_33, joten formula_34. Joka tapauksessa on löydetty alkulukua formula_35 suurempi alkuluku. Tällöin alkulukuja onkin vähintään formula_36 kappaletta. Ollaan päädytty ristiritaan. Täten alkuperäinen väite on tosi. 
Itsestään selvästi alkulukujen joukko on luonnollisten lukujen joukon osajoukko, joten alkulukujen joukon on oltava myös numeroituva. 
Tiheys.
Alkuluvuille on olemassa laskufunktio. Merkintä formula_37 tarkoittaa lukua "n" pienempien alkulukujen määrää. Alkulukujen tiheys on laskeva.
Ohessa formula_37 laskettuna joillekin "n":n arvoille kasvavan suuruusluokan mukaan.
Alkulukulause antaa asymptoottisen arvion formula_37-funktion käyttäytymiselle. Sen nojalla
formula_40
Tämä merkintä ei tarkoita sitä, että näiden funktioiden arvojen erotus lähestyy nollaa, kun "x" lähestyy ääretöntä, vaan sitä, että niiden arvojen osamäärä lähestyy yhtä, kun "x" lähestyy ääretöntä. Arvion antama virhe voi siis olla suurikin, mutta suhteutettuna "x":ään se on tarpeeksi pieni, jotta arvio on hyödyllinen.
Alkulukuteoreeman esitti ensimmäisen kerran Gauss konjektuurina 1800-luvulla. Sen todistivat toisistaan riippumatta Hadamard ja de la Vallée Poussin vuonna 1896.
Eräs alkulukukaava.
Seuraava funktio tuottaa luonnollisen luvun formula_8 eri arvoilla kaikki alkuluvut ja vain ne: 
 formula_42.
Tämän lausekkeen arvo on formula_43, jos tämä on alkuluku, muussa tapauksessa 2. Luvun formula_8 arvoilla 1 – 12 lauseke saa arvot 2, 3, 2, 5, 2, 7, 2, 2, 2, 11, 2 ja 13. 
Kaavan hyöty on kuitenkin lähinnä teoreettinen, koska kertoman laskeminen on erittäin työlästä tietokoneillekin.
Esimerkiksi alkulukua formula_45 varten täytyy laskea luvun formula_46 kertoma, joka on formula_47.
Ohjelman pseudokoodi:
 define factorial("n"):
 if "n" == 0 or "n" == 1:
 return 1
 else:
 return "n" * factorial("n" - 1)
 "k" = read_integer()
 for "n" in 1 to "k":
 "c" = factorial("n")
 "prime" = 2 + (2 * "c" mod ("n" + 1))
 if "prime" not in "seen_primes":
 "seen_primes".insert("prime")
 print "prime"
Suurimmat tunnetut alkuluvut.
Suurin tunnettu alkuluku, joka "ei ole" Mersennen alkuluku, on formula_48. Tässä luvussa on numeroa. Se löydettiin Seventeen or Bust -projektin avulla 31. lokakuuta 2016.
Avoimia kysymyksiä.
Matematiikassa on monia alkulukuja koskevia avoimia kysymyksiä, joista varmastikin tunnetuin on Riemannin hypoteesi. Alla on lueteltu muita tunnettuja avoimia kysymyksiä.