Alkuluku

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}$.

Tiheys

Alkuluvuille on olemassa laskufunktio ${\displaystyle \pi (n)}$. Merkintä ${\displaystyle \pi (n)}$ tarkoittaa lukua n pienempien alkulukujen määrää. Alkulukujen tiheys on laskeva.

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

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.

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

Kaavio suurimman tunnetun alkuluvun numeroiden lukumäärän kasvusta logaritmisella asteikoilla

Suurin tunnettu alkuluku on ${\displaystyle 2^{82\,589\,933}-1}$. Tässä luvussa on 24 862 048 numeroa. Se on 51. tunnettu Mersennen alkuluku.[4]

Toiseksi suurin tunnettu alkuluku on ${\displaystyle 2^{77\,232\,917}-1}$. Tässä luvussa on 23 249 425 numeroa. Se on 50. tunnettu Mersennen alkuluku.[5]

Kolmanneksi suurin tunnettu alkuluku on ${\displaystyle 2^{74\,207\,281}-1}$. Tässä luvussa on 22 338 618 numeroa. Se on 49. tunnettu Mersennen alkuluku.[6] Alkuluvun löysi 7. tammikuuta 2016 GIMPS-projektissa mukana ollut tietokone.

Neljänneksi suurin tunnettu alkuluku on ${\displaystyle 2^{57\,885\,161}-1}$. Tässä luvussa on noin 17 miljoonaa numeroa. Se on 48. tunnettu Mersennen alkuluku. Alkuluvun löysi 25. tammikuuta 2013 Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.[7]

Viidenneksi suurin tunnettu alkuluku on ${\displaystyle 2^{43\,112\,609}-1}$. Tässä luvussa on 12 978 189 numeroa. Se on 45. tunnettu Mersennen alkuluku. Alkuluvun löysi 23. elokuuta 2008 University of California, Los Angelesin matematiikan osaston tietokone, joka osallistui GIMPS-projektiin.

Kuudenneksi suurin tunnettu alkuluku on ${\displaystyle 2^{42\,643\,801}-1}$. Tässä luvussa on 12 837 064 numeroa. Se on 47. tunnettu Mersennen alkuluku. Alkuluvun löysi 12. kesäkuuta 2009 Odd Magnar Strindmo, joka osallistui GIMPS-projektiin.

Seitsemänneksi suurin tunnettu alkuluku on ${\displaystyle 2^{37\,156\,667}-1}$. Tässä luvussa on 11 185 272 numeroa. Se on 46. tunnettu Mersennen alkuluku. Alkuluvun löysi 6. syyskuuta 2008 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 10223\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.

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