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



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  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
.
Tekijöihinjakoa, jossa alkulukutekijät ovat suuruusjärjestyksessä, kutsutaan kanoniseksi alkulukuhajotelmaksi.

 Ominaisuuksia  
Jos p on alkuluku, niin  (Wilsonin lause).
Mikäli  ja  ovat keskenään jaottomia, niin on olemassa äärettömän monta alkulukua muotoa , missä  on luonnollinen luku.
Mikäli  on alkuluku ja  on kokonaisluku, niin  on jaollinen luvulla  (Fermat’n pieni lause).
Jokaiselle alkuluvulle  on olemassa luonnollinen luku  siten että .
Jokaiselle alkuluvulle  on olemassa luonnollinen luku  siten että .
Ainoa parillinen alkuluku on 2, ja ainoat peräkkäiset alkuluvut 2 ja 3 (seuraa alkuluvun määritelmästä).
Alkulukujen neliöjuuret ovat irrationaalilukuja. (Itse asiassa kaikkien positiivisten kokonaislukujen, jotka eivät ole neliölukuja, neliöjuuret ovat irrationaalisia, kts. kokonaisluvun neliöjuuri).|

 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  kaikki alkuluvut sisältävä joukko siten, että , missä  ja . Tällöin alkulukuja on  kappaletta. Olkoon 

Ilmiselvästi . Nyt  kaikilla , joten  kaikilla . Täten  on alkuluku tai on olemassa alkuluku  siten, että  ja , joten . Joka tapauksessa on löydetty alkulukua  suurempi alkuluku. Tällöin alkulukuja onkin vähintään  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ä  tarkoittaa lukua n pienempien alkulukujen määrää. Alkulukujen tiheys on laskeva.
Ohessa  laskettuna joillekin n:n arvoille kasvavan suuruusluokan mukaan.

n4251681 2299 59278 498664 5795 761 45550 847 534

Alkulukulause antaa asymptoottisen arvion -funktion käyttäytymiselle. Sen nojalla

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  eri arvoilla kaikki alkuluvut ja vain ne: 
 .

Tämän lausekkeen arvo on , jos tämä on alkuluku, muussa tapauksessa 2.  Luvun  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  varten täytyy laskea luvun  kertoma, joka on .

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 

 Sija  Alkuluku  Numeroita  Löydetty  Muuta 1.   21. lokakuuta 2024 52. tunnettu Mersennen alkuluku.http://www.mersenne.org Alkuluvun löysi GIMPS-projektissa mukana ollut Luke Durant. 2.   7. joulukuuta 2018 51. tunnettu Mersennen alkuluku.http://www.mersenne.org  3.   26. joulukuuta 2017 50. tunnettu Mersennen alkuluku. 4.   7. tammikuuta 2016 49. tunnettu Mersennen alkuluku. Alkuluvun löysi GIMPS-projektissa mukana ollut tietokone. 5.   25. tammikuuta 2013 48. tunnettu Mersennen alkuluku. Alkuluvun löysi Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.http://www.digitoday.fi/tiede-ja-teknologia/2013/02/06/uusi-suurin-alkuluku-tayttaisi-28-romaania/20132017/66 6.   23. elokuuta 2008 45. tunnettu Mersennen alkuluku. Alkuluvun löysi University of California, Los Angelesin matematiikan osaston tietokone, joka osallistui GIMPS-projektiin. 7.   12. kesäkuuta 2009 47. tunnettu Mersennen alkuluku. Alkuluvun löysi Odd Magnar Strindmo, joka osallistui GIMPS-projektiin. 8.   6. syyskuuta 2008 46. tunnettu Mersennen alkuluku. Alkuluvun löysi Hans-Michael Elvenich Saksan Langenfeldistä, joka osallistui GIMPS-projektiin. Tämä oli ensimmäinen epäjärjestyksessä löytynyt Mersennen alkuluku sitten vuoden 1988.

Suurin tunnettu alkuluku, joka ei ole Mersennen alkuluku, on . 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ä.
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ähimmästä alkuluvusta on 2, toisin sanoen, onko alkulukupareja äärettömän monta?

 Katso myös 
Jaksollinen funktio, Esimerkki 3.
Yhdistetty luku

 Lähteet 

 Kirjallisuutta 


 Aiheesta muualla 

 Seventeen or Bust -projekti, jonka tarkoituksena on löytää suuria alkulukuja ja määrittää pienin Sierpinskin luku.
 GIMPS-projekti, jonka tarkoituksena on etsiä suuria Mersennen alkulukuja
 Topics in Multiplicative Number Theory (väitös).

Luokka:Lukujonot
Luokka:Seulonnan keskeiset artikkelit
Luokka:Alkuluvut