Movatterモバイル変換

[0]ホーム
URL:

Siirry sisältöön
Wikipedia
Haku

Alkuluku

Wikipediasta
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.

Alkuluku on lukua 1 suurempiluonnollinen luku, joka ei olejaollinen muilla positiivisillakokonaisluvuilla kuin yhdellä ja itsellään.[1] Alkulukujen joukkoa merkitään kirjaimellaP. Pienimmät kymmenen alkulukua ovat 2, 3, 5, 7, 11, 13, 17, 19, 23 ja 29.[2] Alkulukuja onnumeroituvasti ääretön määrä. Lukua 1 suurempaa kokonaislukua, joka ei ole alkuluku, sanotaanyhdistetyksi luvuksi. Lukua 1 ei lueta alkuluvuksi, vaikka se onkin jaoton luku, jotta alkulukuja koskevien matemaattisten lauseiden muotoilu olisi yksinkertaisempaa.

Alkulukujen laskemiseksi on olemassa useitaalgoritmeja. Yksi yksinkertaisimmista algoritmeista onEratostheneen seula, joskin se on työläs ja hidas suurten alkulukujen etsimiseen.

Kaksi lukua ovatalkulukuja toistensa suhteen eli keskenään jaottomia, jos niillä ei ole ykköstä suurempia yhteisiä tekijöitä.

Historiaa

[muokkaa |muokkaa wikitekstiä]

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

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

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

Luonnolliset luvut tulona

[muokkaa |muokkaa wikitekstiä]

Jokainen luonnollinen luku paitsi1{\displaystyle 1} voidaan jakaaalkulukutekijö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

23244=22⋅3⋅13⋅149{\displaystyle 23\,244=2^{2}\cdot 3\cdot 13\cdot 149}.

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

Ominaisuuksia

[muokkaa |muokkaa wikitekstiä]

Määrän äärettömyys

[muokkaa |muokkaa wikitekstiä]

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 |muokkaa wikitekstiä]

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

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

OlkoonP{\displaystyle {\mathcal {P}}} kaikki alkuluvut sisältävä joukko siten, ettäP={p1,p2,…,pn}{\displaystyle {\mathcal {P}}=\{p_{1},p_{2},\dots ,p_{n}\}}, missän∈N{\displaystyle n\in \mathbb {N} } jap1<p2<…<pn{\displaystyle p_{1}<p_{2}<\ldots <p_{n}}. Tällöin alkulukuja onn{\displaystyle n} kappaletta. Olkoon

q=p1⋅p2⋅…⋅pn+1.{\displaystyle q=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n}+1.}

Ilmiselvästipn<q{\displaystyle p_{n}<q}. Nytq≡1(modr){\displaystyle q\equiv 1{\pmod {r}}} kaikillar∈P{\displaystyle r\in {\mathcal {P}}}, jotenq≢0(modr){\displaystyle q\not \equiv 0{\pmod {r}}} kaikillar∈P{\displaystyle r\in {\mathcal {P}}}. Tätenq{\displaystyle q} on alkuluku tai on olemassa alkulukus{\displaystyle s} siten, ettäs∉P{\displaystyle s\not \in {\mathcal {P}}} jaq≡0(mods){\displaystyle q\equiv 0{\pmod {s}}}, jotens>pn{\displaystyle s>p_{n}}. Joka tapauksessa on löydetty alkulukuapn{\displaystyle p_{n}} suurempi alkuluku. Tällöin alkulukuja onkin vähintäänn+1{\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.

Tiheys

[muokkaa |muokkaa wikitekstiä]

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

nπ(n){\displaystyle \pi (n)}
10{\displaystyle 10}4
102{\displaystyle 10^{2}}25
103{\displaystyle 10^{3}}168
104{\displaystyle 10^{4}}1 229
105{\displaystyle 10^{5}}9 592
106{\displaystyle 10^{6}}78 498
107{\displaystyle 10^{7}}664 579
108{\displaystyle 10^{8}}5 761 455
109{\displaystyle 10^{9}}50 847 534

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

π(x)∼xln⁡x{\displaystyle \pi (x)\sim {\frac {x}{\ln x}}}

Tämä merkintä ei tarkoita sitä, että näiden funktioiden arvojen erotus lähestyy nollaa, kunx lähestyy ääretöntä, vaan sitä, että niiden arvojen osamäärä lähestyy yhtä, kunx lähestyy ääretöntä. Arvion antama virhe voi siis olla suurikin, mutta suhteutettunax:ään se on tarpeeksi pieni, jotta arvio on hyödyllinen.

Alkulukuteoreeman esitti ensimmäisen kerranGauss konjektuurina 1800-luvulla. Sen todistivat toisistaan riippumattaHadamard jade la Vallée Poussin vuonna 1896.

Eräs alkulukukaava

[muokkaa |muokkaa wikitekstiä]

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

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

Tämän lausekkeen arvo onn+1{\displaystyle n+1}, jos tämä on alkuluku, muussa tapauksessa 2. Luvunn{\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, koskakertoman laskeminen on erittäin työlästä tietokoneillekin.Esimerkiksi alkulukuaf(23){\displaystyle f(23)} varten täytyy laskea luvun22{\displaystyle 22} kertoma, joka on1124000727777607680000{\displaystyle 1\,124\,000\,727\,777\,607\,680\,000}.

Ohjelman pseudokoodi:

define factorial(n):  ifn == 0 orn == 1:      return 1  else:      returnn * factorial(n - 1)k = read_integer() forn in 1 tok:c = factorial(n)prime = 2 + (2 *c mod (n + 1))  ifprime not inseen_primes:seen_primes.insert(prime)      printprime

Suurimmat tunnetut alkuluvut

[muokkaa |muokkaa wikitekstiä]
Kaavio suurimman tunnetun alkuluvun numeroiden lukumäärän kasvustalogaritmisella asteikoilla
SijaAlkulukuNumeroitaLöydettyMuuta
1.2136279841−1{\displaystyle 2^{136\,279\,841}-1}41 024 32021. lokakuuta 202452. tunnettuMersennen alkuluku.[5] Alkuluvun löysiGIMPS-projektissa mukana ollut Luke Durant.
2.282589933−1{\displaystyle 2^{82\,589\,933}-1}24 862 0487. joulukuuta 201851. tunnettuMersennen alkuluku.[6]
3.277232917−1{\displaystyle 2^{77\,232\,917}-1}23 249 42526. joulukuuta 201750. tunnettu Mersennen alkuluku.[7]
4.274207281−1{\displaystyle 2^{74\,207\,281}-1}22 338 6187. tammikuuta 201649. tunnettu Mersennen alkuluku.[8] Alkuluvun löysiGIMPS-projektissa mukana ollut tietokone.
5.257885161−1{\displaystyle 2^{57\,885\,161}-1}17 425 17025. tammikuuta 201348. tunnettu Mersennen alkuluku. Alkuluvun löysi Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.[9]
6.243112609−1{\displaystyle 2^{43\,112\,609}-1}12 978 18923. elokuuta 200845. tunnettu Mersennen alkuluku. Alkuluvun löysiUniversity of California, Los Angelesin matematiikan osaston tietokone, joka osallistui GIMPS-projektiin.
7.242 643 801−1{\displaystyle 2^{42\ 643\ 801}-1}12 837 06412. kesäkuuta 200947. tunnettu Mersennen alkuluku. Alkuluvun löysi Odd Magnar Strindmo, joka osallistui GIMPS-projektiin.
8.237 156 667−1{\displaystyle 2^{37\ 156\ 667}-1}11 185 2726. syyskuuta 200846. 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, jokaei ole Mersennen alkuluku, on10 223×231 172 165+1{\displaystyle 10\ 223\times 2^{31\ 172\ 165}+1}. Tässä luvussa on9 383 761 numeroa. Se löydettiinSeventeen or Bust -projektin avulla 31. lokakuuta 2016.

Avoimia kysymyksiä

[muokkaa |muokkaa wikitekstiä]
Katso myös:Landaun ongelmat

Matematiikassa on monia alkulukuja koskevia avoimia kysymyksiä, joista varmastikin tunnetuin onRiemannin hypoteesi. Alla on lueteltu muita tunnettuja avoimia kysymyksiä.

Katso myös

[muokkaa |muokkaa wikitekstiä]

Lähteet

[muokkaa |muokkaa wikitekstiä]
  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. ↑http://www.mersenne.org
  7. ↑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.
  8. ↑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.
  9. ↑http://www.digitoday.fi/tiede-ja-teknologia/2013/02/06/uusi-suurin-alkuluku-tayttaisi-28-romaania/20132017/66

Kirjallisuutta

[muokkaa |muokkaa wikitekstiä]

Aiheesta muualla

[muokkaa |muokkaa wikitekstiä]
Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheestaAlkuluku.

 

Noudettu kohteesta ”https://fi.wikipedia.org/w/index.php?title=Alkuluku&oldid=22724707”
Luokat:
Piilotettu luokka:
[8]ページ先頭
©2009-2025 Movatter.jp