Pääluvut

Pääluvut on epätyypillinen suomalainen termi prime numbersille. Yleisimmin käytetty vastine on alkuluvut. Tässä artikkelissa pääluvut tarkoittaa alkulukuja.

Alkuluku on luonnollinen luku suurempi kuin 1, jolla on täsmälleen kaksi positiivista jakajaa: 1 ja itsensä. Esimerkkejä ovat 2, 3, 5, 7 ja 11. Huomionarvoista on, että 2 on ainoa parillinen alkulukku.

Alkulukujen ominaisuuksiin kuuluu, että jokainen kokonaisluku suurempi kuin 1 voi purkautua yksinkertaisiin alkulukujen tekijöihin, ja purkautuminen on aina ainutlaatuista. Tämä on alkulukujen kertolaskun peruslause, eli lukuteorian keskeinen tulos.

Alkuluvut ovat äärettömän monia. Euclides osoitti tämän todistuksessaan: jos otetaan luvun kaikkia tuntemia alkulukuja ja kerrotaan ne yhteen sekä lisätään 1, syntyy luku, joka ei ole mikään näistä alkulukujen tekijä, jolloin uusia alkulukuvia on oltava.

Käytännössä pääluvut ovat keskeisiä lukuteoriassa. Niitä etsitään esimerkiksi Eratostheneen seulan avulla tai primality-testeillä kuten Miller–Rabinin testit sekä deterministiset testit suurille luvuille. Suurten alkulukujen löytäminen on tärkeää kryptografiassa, erityisesti RSA-tyyppisissä järjestelmissä.

Historia: alkulukujen tutkimus ulottuu antiikin Kreikkaan; Euclides osoitti äärettömyyden ja peruslauseiden kaltaisia tuloksia, joita on jälkipolville laajennettu ja kehitetty modernein algoritmein.