Primaluku on luonnollinen luku, joka on suurempi kuin 1 ja jonka ainoat positiiviset tekijät ovat 1 ja luku itse. Toisin sanoen luku p > 1 on alkuluku, jos sitä ei voi kirjoittaa kahden suuremman luonnollisen luvun m ja n tulona. Jos luku voidaan esittää siten, sitä kutsutaan yhdistelmäluvuksi eli komposiittiluvuksi. Pienin yhdistelty luku on 4, koska 2 × 2 = 4. Luku 1 ei ole yhdistelty eikä alkuluku, vaan sillä on oma erityisasemansa. Pienin alkuluku on 2, ja sitä seuraavat alkuluvut ovat 3, 5, 7, 11 ja 13. Suurinta alkulukua ei ole: alkulukuja on äärettömän monta. Primalukujen joukkoa merkitään joskus muodossa {\displaystyle \mathbb {P} }.

Määritelmä ja keskeisiä ominaisuuksia

  • Alkuluku on kokonaisluku p > 1, jolla ei ole muita positiivisia tekijöitä kuin 1 ja p itse.
  • 2 on ainoa parillinen alkuluku; kaikki muut alkuluvut ovat parittomia.
  • Alkulukuja on äärettömästi — tästä antoi ensimmäisen tunnetun todistuksen antiikin matemaatikko Eukleideus.
  • Kun luku kasvaa, sen alkulukuisuuden varmistaminen voi olla laskennallisesti vaikeampaa; samaan aikaan alkulukujen esiintymisen tarkka ennustaminen on yksi matematiikan kiinnostavista osa-alueista.

Alkulukujen esimerkkejä

Ensimmäisiä alkulukuja ovat

  • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Pienimmät yhdistelmäluvut ovat 4, 6, 8, 9, 10, ...

Peruslause aritmetiikassa

Aritmetiikan perusteoriassa todetaan, että jokainen positiivinen kokonaisluku > 1 voidaan esittää alkulukujen tulona tavalla, joka on yksikäsitteinen järjestyksestä riippumatta. Tämä on niin sanottu peruslause aritmetiikassa (Fundamental Theorem of Arithmetic). Käytännössä tämä tarkoittaa, että jokaisella kokonaisluvulla on yksikäsitteinen alkutekijäjako.

Tämä periaate on keskeinen monilla aloilla, mm. lukuteoriassa, koodauksessa ja salauksessa (esim. RSA), koska suurten lukujen tekijöihin jakaminen on usein paljon vaikeampaa kuin alkuluvun testaaminen.

Alkulukujen etsiminen ja testaaminen

Alkulukujen löytämiseen ja testaamiseen on kehitetty monia menetelmiä:

  • Jaollisuustestit ja koejaotus (trial division) pienillä tekijöillä — yksinkertainen mutta hidas suurilla luvuilla.
  • Seulamenetelmät, kuten Eratostheneen seula, jotka löytävät kaikki alkuluvut tiettyyn rajaan asti tehokkaasti.
  • Probabilistiset primalisuustestit, kuten Miller–Rabin, jotka kertovat todennäköisesti, onko luku alkuluku (nopeat ja käytännössä luotettavat parametrien valinnalla).
  • Deterministiset algoritmit, kuten AKS-primalisuustesti, jotka pystyvät kertomaan varmasti, onko luku alkuluku, ilman todennäköisyyskomponenttia (vaikka käytännössä usein hitaampia kuin heuristiset testit suurilla luvuilla).

Jakautuminen ja tilastolliset tulokset

Alkulukujen jakautumista suurten lukujen joukossa kuvaa muun muassa alkulukujen jakautumislause (Prime Number Theorem), jonka mukaan alkulukujen tiheys lähellä suurta lukua n on suunnilleen 1 / log n. Tämä antaa käsityksen siitä, kuinka harvinaisia alkuluvut ovat kasvaessa.

Suuria avoimia ongelmia ja tutkimus

  • Goldbachin arvelu — esittää, että jokaista parillista lukua suurempaa kuin 2 voidaan esittää kahden alkuluvun summana; tämä on vielä ratkaisematon.
  • Kaksosalkuluvut (twin primes) — arvaus on, että äärettömän monta paria p ja p+2 on alkulukuja, mutta tämäkin on ratkaisematta.
  • Alkulukujen esiintymiseen liittyy monia muita syviä kysymyksiä, ja uusinta tutkimusta tehdään sekä teoreettisesti että laskennallisesti.

Suurimmat löydetyt alkuluvut

Suuret alkuluvut löydetään usein Mersennen-lukujen muotoisina (2^p − 1, kun p on alkuluku) ja monet maailman suurimmat tunnetut alkuluvut löytyvät GIMPS-projektin (Great Internet Mersenne Prime Search) kaltaisissa hajautetuissa laskentaprojekteissa. Monet tutkijat ja harrastajat osallistuvat tähän työhön etsiäkseen yhä suurempia alkulukuja.

Käytännön huomioita ja esimerkkejä tehtäviä varten

Perustehtäviä:

  • Tarkista, onko luku 97 alkuluku käyttämällä koejaotusta tekijöillä 2, 3, 5, 7 (riittää, kun tarkistat kaikki tekijät ≤ √97).
  • Kirjoita luku 360 alkutekijämuodossa: 360 = 2^3 × 3^2 × 5.

Alkuluvut ovat yksi lukuteorian keskeisistä aiheista ja niihin liittyy sekä yksinkertaisia perusominaisuuksia että hyvin syvällisiä ja vaikeita ongelmia. Lisätietoa ja syventäviä teemoja voi löytää muun muassa alkulukuteoriasta ja aritmetiikan perusteoriasta (Aritmetiikan perusteoriassa).

Huom. Se, että jokin luku ei ole ilmeisesti jaollinen pienillä tekijöillä, ei aina todista lopullisesti sen alkulukuisuutta ilman luotettavaa primalisuustestiä tai täydellistä tekijöintiä.