Alkuluku

Alkuluku on lukua 1 suurempi luonnollinen luku, joka ei ole jaollinen muilla positiivisilla kokonaisluvuilla kuin yhdellä ja itsellään.^[1] Alkulukujen joukkoa merkitään kirjaimella P. Pienimmät kymmenen alkulukua ovat 2, 3, 5, 7, 11, 13, 17, 19, 23 ja 29.^[2] 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ä.

1600-luvulla elänyt ranskalainen matemaatikko Pierre de Fermat tarkasteli ensimmäisiä lukuja epänegatiivisten kokonaislukujen n (0, 1, 2, 3, …) funktiossa

${\displaystyle 2^{2^{n}}+1}$

ja päätteli virheellisesti, että kaikki näin saadut luvut eli Fermat’n luvut (3, 5, 17, 257, 65537, …) olisivat alkulukuja.^[3]

Jokainen luonnollinen luku paitsi ${\displaystyle 1}$ 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

${\displaystyle 23\,244=2^{2}\cdot 3\cdot 13\cdot 149}$.

Tekijöihinjakoa, jossa alkulukutekijät ovat suuruusjärjestyksessä, kutsutaan kanoniseksi alkulukuhajotelmaksi.

• Jos p on alkuluku, niin ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ (Wilsonin lause).
• Mikäli ${\displaystyle a}$ ja ${\displaystyle d}$ ovat keskenään jaottomia, niin on olemassa äärettömän monta alkulukua muotoa ${\displaystyle a+nd}$, missä ${\displaystyle n}$ on luonnollinen luku.
• Mikäli ${\displaystyle p}$ on alkuluku ja ${\displaystyle a}$ on kokonaisluku, niin ${\displaystyle a^{p}-a}$ on jaollinen luvulla ${\displaystyle p}$ (Fermat’n pieni lause).
• Jokaiselle alkuluvulle ${\displaystyle p>2}$ on olemassa luonnollinen luku ${\displaystyle n}$ siten että ${\displaystyle p=4n\pm 1}$.
• Jokaiselle alkuluvulle ${\displaystyle p>3}$ on olemassa luonnollinen luku ${\displaystyle n}$ siten että ${\displaystyle p=6n\pm 1}$.
• Ainoa parillinen alkuluku on 2, ja ainoat peräkkäiset alkuluvut 2 ja 3 (seuraa alkuluvun määritelmästä).

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.

Väite: alkulukuja on äärettömän monta.

Tehdään vastaoletus: alkulukujen joukko on äärellinen.

Olkoon ${\displaystyle {\mathcal {P}}}$ kaikki alkuluvut sisältävä joukko siten, että ${\displaystyle {\mathcal {P}}=\{p_{1},p_{2},\dots ,p_{n}\}}$, missä ${\displaystyle n\in \mathbb {N} }$ ja ${\displaystyle p_{1}<p_{2}<\ldots <p_{n}}$. Tällöin alkulukuja on ${\displaystyle n}$ kappaletta. Olkoon

${\displaystyle q=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n}+1.}$

Ilmiselvästi ${\displaystyle p_{n}<q}$. Nyt ${\displaystyle q\equiv 1{\pmod {r}}}$ kaikilla ${\displaystyle r\in {\mathcal {P}}}$, joten ${\displaystyle q\not \equiv 0{\pmod {r}}}$ kaikilla ${\displaystyle r\in {\mathcal {P}}}$. Täten ${\displaystyle q}$ on alkuluku tai on olemassa alkuluku ${\displaystyle s}$ siten, että ${\displaystyle s\not \in {\mathcal {P}}}$ ja ${\displaystyle q\equiv 0{\pmod {s}}}$, joten ${\displaystyle s>p_{n}}$. Joka tapauksessa on löydetty alkulukua ${\displaystyle p_{n}}$ suurempi alkuluku. Tällöin alkulukuja onkin vähintään ${\displaystyle n+1}$ 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.

Alkuluvuille on olemassa laskufunktio. Merkintä ${\displaystyle \pi (n)}$ tarkoittaa lukua n pienempien alkulukujen määrää. Alkulukujen tiheys on laskeva. Ohessa ${\displaystyle \pi (n)}$ laskettuna joillekin n:n arvoille kasvavan suuruusluokan mukaan.^[4]

n	${\displaystyle \pi (n)}$
${\displaystyle 10}$	4
${\displaystyle 10^{2}}$	25
${\displaystyle 10^{3}}$	168
${\displaystyle 10^{4}}$	1 229
${\displaystyle 10^{5}}$	9 592
${\displaystyle 10^{6}}$	78 498
${\displaystyle 10^{7}}$	664 579
${\displaystyle 10^{8}}$	5 761 455
${\displaystyle 10^{9}}$	50 847 534

Alkulukulause antaa asymptoottisen arvion ${\displaystyle \pi (n)}$-funktion käyttäytymiselle. Sen nojalla

${\displaystyle \pi (x)\sim {\frac {x}{\ln x}}}$

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.

Seuraava funktio tuottaa luonnollisen luvun ${\displaystyle n}$ eri arvoilla kaikki alkuluvut ja vain ne:

${\displaystyle f(n)=2+(2(n!){\bmod {(}}n+1))}$.

Tämän lausekkeen arvo on ${\displaystyle n+1}$, jos tämä on alkuluku, muussa tapauksessa 2. Luvun ${\displaystyle n}$ 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 ${\displaystyle f(23)}$ varten täytyy laskea luvun ${\displaystyle 22}$ kertoma, joka on ${\displaystyle 1\,124\,000\,727\,777\,607\,680\,000}$.

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

Sija	Alkuluku	Numeroita	Löydetty	Muuta
1.	${\displaystyle 2^{136\,279\,841}-1}$	41 024 320	21. lokakuuta 2024	52. tunnettu Mersennen alkuluku.[5] Alkuluvun löysi GIMPS-projektissa mukana ollut Luke Durant.
2.	${\displaystyle 2^{82\,589\,933}-1}$	24 862 048	7. joulukuuta 2018	51. tunnettu Mersennen alkuluku.[6]
3.	${\displaystyle 2^{77\,232\,917}-1}$	23 249 425	26. joulukuuta 2017	50. tunnettu Mersennen alkuluku.[7]
4.	${\displaystyle 2^{74\,207\,281}-1}$	22 338 618	7. tammikuuta 2016	49. tunnettu Mersennen alkuluku.[8] Alkuluvun löysi GIMPS-projektissa mukana ollut tietokone.
5.	${\displaystyle 2^{57\,885\,161}-1}$	17 425 170	25. tammikuuta 2013	48. tunnettu Mersennen alkuluku. Alkuluvun löysi Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.[9]
6.	${\displaystyle 2^{43\,112\,609}-1}$	12 978 189	23. elokuuta 2008	45. tunnettu Mersennen alkuluku. Alkuluvun löysi University of California, Los Angelesin matematiikan osaston tietokone, joka osallistui GIMPS-projektiin.
7.	${\displaystyle 2^{42\ 643\ 801}-1}$	12 837 064	12. kesäkuuta 2009	47. tunnettu Mersennen alkuluku. Alkuluvun löysi Odd Magnar Strindmo, joka osallistui GIMPS-projektiin.
8.	${\displaystyle 2^{37\ 156\ 667}-1}$	11 185 272	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 ${\displaystyle 10\ 223\times 2^{31\ 172\ 165}+1}$. Tässä luvussa on 9 383 761 numeroa. Se löydettiin Seventeen or Bust -projektin avulla 31. lokakuuta 2016.

Katso myös: Landaun ongelmat

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?

• Jaksollinen funktio, Esimerkki 3.
• Yhdistetty luku

• Derbyshire, John: Alkulukujen lumoissa. Terra Cognita, 2006. ISBN 952-5202-75-5

Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Alkuluku.

• 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).