Alkulukuja

Alkuluvut ovat kokonaislukuja suurempia kuin 1, joilla on vain kaksi positiivista jakajaa: 1 ja itsensä. Esimerkkejä ovat 2, 3, 5, 7, 11 sekä 13 ja 17. 2 on ainoa parillinen alkuluku.

Fundamentaalinen lause alkulukujen tulosta: Jokainen luku suurempi kuin 1 voidaan esittää yksikäsitteisesti alkulukujen tulona, ja tämä esitys on ainutlaatuinen riippumatta siitä, millä tavalla alkulukujen kertolasku esiintyy.

Jakautuminen ja tiheys: Alkulukujen tiheys pienenee suurten lukujen kasvaessa. Pienempien kuin x olevien alkulukujen määrä kasvaa pi(x)-funktiolla, ja primien lukumäärä noudattaa likimääräistä kaavaa pi(x) ~ x/log x (primien lukumääräennuste).

Eratostheneen siivilä on perinteinen keino löytää kaikki alkuluvut enintään N. Siivilän ideana on merkitä luvut kaksista eteenpäin ja poistaa kunkin alkuluvun monikertoja suuremmista luvuista, jolloin jäljelle jäävät luvut ovat alkulukuja.

Käyttö ja merkitys: Suuret alkulukuvia tarvitaan erityisesti modernissa kryptografiassa, kuten RSA-salauksen avaimissa. Kristallisoituneita testejä primaliteetin varmistamiseen ovat esimerkikiksi Miller–Rabinin epävarmuustesti ja AKS:n deterministinen primaliteettitesti, joiden avulla suuria alkulukujen joukkoja voidaan luotettavasti todeta. Alkulukujen tutkimus yhdistää teoreettisen kiehtovuuden ja käytännön sovellukset lukuteoriassa.