Alkuluku

lukua 1 suurempi luonnollinen luku, joka ei ole jaollinen muilla positiivisilla kokonaisluvuilla kuin yhdellä ja itsellään

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.

12 esinettä voidaan asettaa kolmeen yhtä suureen pinoon, joten luku 12 ei ole alkuluku. 11 esineellä tämä ei ole mahdollista millään pinojen määrällä, joten luku 11 on alkuluku.

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

muokkaa

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

 

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

Luonnolliset luvut tulona

muokkaa

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

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

Määrän äärettömyys

muokkaa

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

muokkaa

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

muokkaa

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.[4]

n  
  4
  25
  168
  1 229
  9 592
  78 498
  664 579
  5 761 455
  50 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

muokkaa

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

muokkaa
 
Kaavio suurimman tunnetun alkuluvun numeroiden lukumäärän kasvusta logaritmisella asteikoilla
Sija Alkuluku Numeroita Löydetty Muuta
1.   24 862 048 7. joulukuuta 2018 51. tunnettu Mersennen alkuluku.[5]
2.   23 249 425 26. joulukuuta 2017 50. tunnettu Mersennen alkuluku.[6]
3.   22 338 618 7. tammikuuta 2016 49. tunnettu Mersennen alkuluku.[7] Alkuluvun löysi GIMPS-projektissa mukana ollut tietokone.
4.   17 425 170 25. tammikuuta 2013 48. tunnettu Mersennen alkuluku. Alkuluvun löysi Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.[8]
5.   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.
6.   12 837 064 12. kesäkuuta 2009 47. tunnettu Mersennen alkuluku. Alkuluvun löysi Odd Magnar Strindmo, joka osallistui GIMPS-projektiin.
7.   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  . Tässä luvussa on 9 383 761 numeroa. Se löydettiin Seventeen or Bust -projektin avulla 31. lokakuuta 2016.

Avoimia kysymyksiä

muokkaa
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ä.

Katso myös

muokkaa

Lähteet

muokkaa
  1. Häsä, Jokke & Rämö, Johanna: Johdatus abstraktiin algebraan, s. 84–86. Helsinki: Gaudeamus, 2015. ISBN 978-952-495-361-0.
  2. The First 10,000 Primes The University of Tennessee at Martin. (englanniksi)
  3. Gleick, James: Kiire. Miksi aika tahtoo loppua?. (Alkuteos: Faster. The Acceleration of Just About Everything, 1999.) Suomentanut Arto Schroderus. Helsinki: Tammi, 2001. ISBN 951-31-1993-9.
  4. Xavier Gourdon and Pascal Sebah: A table of values of pi(x) numbers.computation.free.fr. Viitattu 11.8.2023.
  5. http://www.mersenne.org
  6. Miina Rautiainen: Uusi maailman suurin alkuluku löytyi ja vielä yllättävän nopeasti – laskutoimitukseen kului tietokoneelta 6 päivää Tekniikka ja talous. 5.1.2018. Viitattu 6.1.2018.
  7. Saarinen, Juhani: Maailman suurin tunnettu alkuluku löytyi, mutta se on hyödytön – katso koko 22 338 618- numeroinen luku HS.fi. 20.1.2016. Viitattu 23.1.2016.
  8. http://www.digitoday.fi/tiede-ja-teknologia/2013/02/06/uusi-suurin-alkuluku-tayttaisi-28-romaania/20132017/66

Kirjallisuutta

muokkaa

Aiheesta muualla

muokkaa