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 ää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
ja päätteli virheellisesti, että kaikki näin saadut luvut eli Fermat’n luvut (3, 5, 17, 257, 65537, …) olisivat alkulukuja.
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.
Eukleides antoi vanhimman tunnetun todistuksen alkulukujen määrän äärettömyydelle. Todistus on lyhyesti seuraava:
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.
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.
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
Sija | Alkuluku | Numeroita | Löydetty | Muuta |
---|---|---|---|---|
1. | 24 862 048 | 7. joulukuuta 2018 | 51. tunnettu Mersennen alkuluku. | |
2. | 23 249 425 | 26. joulukuuta 2017 | 50. tunnettu Mersennen alkuluku. | |
3. | 22 338 618 | 7. tammikuuta 2016 | 49. tunnettu Mersennen alkuluku. 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. | |
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.
Matematiikassa on monia alkulukuja koskevia avoimia kysymyksiä, joista varmastikin tunnetuin on Riemannin hypoteesi. Alla on lueteltu muita tunnettuja avoimia kysymyksiä.
This article uses material from the Wikipedia Suomi article Alkuluku, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Sisältö on käytettävissä lisenssillä CC BY-SA 4.0, ellei toisin mainita. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Suomi (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.