Alkuluku

Wikipedia

Alkuluku on yhtä suurempi luonnollinen luku, joka ei ole jaollinen muilla positiivisilla kokonaisluvuilla kuin yhdellä ja itsellään. Ensimmäiset alkuluvut ovat $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ ja $29$ . Alkulukuja on ääretön määrä.

Lukua $1$ suurempaa kokonaislukua, joka ei ole alkuluku, sanotaan yhdistetyksi luvuksi. Lukua $1$ ei yleensä lueta alkuluvuksi, vaikka se onkin jaoton luku, koska tällöin moni matemaattinen lause, joka koskee alkulukuja, on helpompi muotoilla.

Alkulukujen laskemiseksi on olemassa useita algoritmeja. Yksi yksinkertaisimmista algoritmeista on Eratostheneen seula.

Suuria alkulukuja käytetään kryptografiassa.

Sisällysluettelo

1 Luonnollisten lukujen esittäminen alkulukujen tulona
2 Alkulukujen ominaisuuksia
3 Alkulukujen määrän äärettömyys
4 Suurin tunnettu alkuluku
5 Alkulukuja tuottavia kaavoja
6 Avoimia kysymyksiä
7 Aiheeseen liittyvää kirjallisuutta
8 Aiheesta muualla
9 Katso myös

[muokkaa] Luonnollisten lukujen esittäminen alkulukujen tulona

Jokainen luonnollinen luku paitsi $1$ voidaan jakaa alkulukutekijöihin. Voidaan osoittaa, että tämä tekijöihinjako on yksikäsitteinen lukuun ottamatta tulon kertomisjärjestystä. Voidaan esimerkiksi kirjoittaa

$23 \, 244 = 2^2 \times 3 \times 13 \times 149$ .

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

[muokkaa] Alkulukujen ominaisuuksia

Jos p on alkuluku, niin $(p-1)!\equiv-1 \pmod{p}$ . (Wilsonin lause)
Mikäli $a$ ja $d$ ovat suhteellisia alkulukuja, niin on olemassa äärettömän monta alkulukua muotoa $a + n d$ , missä $n$ on luonnollinen luku.
Mikäli $p$ on alkuluku ja $a$ on kokonaisluku, niin $a p - a$ on jaollinen luvulla $p$ . (Fermat'n pieni lause)
Jokaiselle alkuluvulle $p > 2$ on olemassa luonnollinen luku $n$ siten että $p=4n \pm 1$
Jokaiselle alkuluvulle $p > 3$ on olemassa luonnollinen luku $n$ siten että $p=6n \pm 1$

[muokkaa] Alkulukujen määrän äärettömyys

Eukleides antoi vanhimman tunnetun todistuksen alkulukujen määrän äärettömyydelle. Todistus on lyhyesti seuraava:

Ota äärellinen joukko 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 jaollinen alkuluvulla, joka ei kuulunut valittuun joukkoon.

Alkuluvuille on olemassa laskufunktio $π(n)$ . Merkintä $π(n)$ tarkoittaa lukua n pienempien alkulukujen määrää. Alkulukujen tiheys on laskeva.

	$π(n)$
$10$	4
$102$	25
$103$	168
$104$	1 229
$105$	9 592
$106$	78 498
$107$	664 579
$108$	5 761 455

Alkulukuteoreema antaa asymptoottisen arvion $π(n)$ -funktion käyttäytymiselle. Sen nojalla

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

Huomaa, että 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.

[muokkaa] Suurin tunnettu alkuluku

Suurin tunnettu alkuluku on $2^{32\, 582\, 657} -1$ . Tässä luvussa on 9 808 358 numeroa. Se on 44. tunnettu Mersennen alkuluku. Alkuluvun löysi 4. syyskuuta 2006 Central Missouri State Universityn ryhmä, joka osallistui GIMPS-projektiin.

Toiseksi suurin tunnettu alkuluku on $2^{30\, 402\, 457} -1$ . Tässä luvussa on 9 152 052 numeroa. Se on 43. tunnettu Mersennen alkuluku, jonka löysivät professorit Curtis Cooper ja Steven Boone GIMPS-projektin avulla 15. joulukuuta 2005.

Kolmanneksi suurin tunnettu alkuluku on $2^{25\, 964\, 951} -1$ Siinä on 7 816 230 numeroa, ja se on 42. tunnettu Mersennen alkuluku. Sen löysi Martin Nowak 18.2.2005 GIMPS-projektin avulla.

Suurin tunnettu alkuluku joka ei ole Mersennen alkuluku on $27653 \times 2^{9\, 167\, 433} + 1$ . Siinä on 2 759 677 numeroa. Se löydettiin Seventeen or Bust-projektin avulla 8.6.2005.

[muokkaa] Alkulukuja tuottavia kaavoja

Seuraava yhtälö tuottaa kaikki ja vain alkuluvut luonnollisille luvuille $n$ :

$f(n) = 2 + (2(n!) \, \operatorname{mod} (n+1))$

Kaavan hyöty on kuitenkin lähinnä teoreettinen, koska kertoman laskeminen on erittäin työlästä tietokoneillekin. Esimerkiksi alkulukua $f (23)$ varten täytyy laskea luvun $22$ kertoma, joka on $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

[muokkaa] 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?
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?

[muokkaa] Aiheeseen liittyvää kirjallisuutta

John Derbyshire (2006): Alkulukujen lumoissa, Terra Cognita. ISBN 952-5202-175-5

[muokkaa] Aiheesta muualla

[1] - Osallistu Seventeen or Bust-projektiin ja auta löytämään suuria alkulukuja ja määrittämään pienin Sierpinskin luku.
[2] - Osallistu GIMPS-projektiin ja auta etsimään suuria Mersennen alkulukuja
[3] - Alkulukuja Paskova Karhu