Frumtala
náttúruleg tala, sem er stærri en 1 og er ekki margfeldi tveggja smærri náttúrulegra talna
(Endurbeint frá Frumtala (stærðfræði))
Frumtala (eða prímtala) er náttúruleg tala, sem er stærri en 1 og er ekki margfeldi tveggja smærri náttúrulegra talna. Talan 1 er ekki skilgreind sem frumtala þar sem hún er eining og gengur því upp í sérhverja náttúrulega tölu. Samsettar tölur (eða þáttanlegar tölur) eru andstæður frumtalna en það eru tölur sem hafa jákvæðan deili annan en 1 og sjálfa sig.
Nokkrar staðreyndir um frumtölur
- Þær frumtölur sem eru lægri en 100 eru: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
- Til eru óendanlega margar frumtölur. Ef svo væri ekki getum við látið
tákna mengi með endanlegan fjölda staka sem innihéldi allar frumtölurnar. Skoðum töluna
. Sérhver frumtala í
skilar þá 1 í leif þegar henni er deilt í
. En þá er
annað hvort frumtala sjálf sem er stærri en þær sem eru í
, eða þá að hún er margfeldi frumtalna sem eru ekki meðal þeirra í
. Hvoru tveggja er mótsögn, svo það fær ekki staðist að
sé mengi allra frumtalna. Þessi sönnun er kennd við Evklíð og byggir á annarri sönnun, undirstöðusetningu reikningslistarinnar, um að allar náttúrlegar tölur stærri en 2 megi rita sem margfeldi frumtalna.
- Það hefur ekki fundist lokuð formúla fyrir frumtölur. Stærsta frumtala sem fundist hefur er Mersenne frumtalan
, sem fannst árið 2013. (Upplýsingar frá nóvember 2015, en.W).
- Frumtölur sem eru samliggjandi oddatölur, eins og til dæmis 17 og 19, 71 og 73 o.s.frv., eru nefndar tvíburafrumtölur (enska: twin primes).
- Tala í tugakerfinu sem endar á 5 eða sléttri tölu getur ekki verið frumtala (nema hún sé 2 og 5). Ef þversumma tölunnar er deilanleg með 3 þá er talan sjálf deilanleg með 3. (T.d. er talan 5217 deilanleg með 3 því 5+2+1+7=15 er deilanleg með 3).
- Sé deilt með 6 í frumtölu, sem er stærri en 5, verður afgangurinn alltaf annað hvort 1 eða 5. Því ef leifin er slétt er talan sjálf slétt, og ef afgangurinn er 3 má deila tölunni sjálfri með 3.
- Litla setning Fermats segir að ef
er frumtala, og
er ósamþátta
, þá er
. Hún er gjarnan notuð til að sýna fram á að tala sé ekki frumtala. Almennari útgáfa hennar er notuð til að sýna fram á virkni RSA dulkóðunarkerfisins.
- Með frumþáttun má finna frumþætti náttúrlegra talna, en frumþættirnir eru einstakir fyrir hverja tölu.
Vöxtur frumtalna og umfang reikninga
- Ef við lítum á
sem óendanlega runu frumtalna, þá segir frumtalnasetningin okkur að frumtalan
sé u.þ.b.
, og að matið batnar eftir því sem
stækkar.
- Þær eru mikið notaðar í dulkóðun. Sem dæmi eru þær undirstaða öryggis RSA reikniritsins, þar sem það að þátta tölu er talið vera erfitt og núverandi aðferðir ganga út á að hreinlega prófa alla mögulega þætti (sjá hér að neðan).
- Hægt er að ganga úr skugga um hvort tala
sé frumtala með því að prófa að deila sérhverri frumtölu
í
og athuga hvort leifin sé 0. Það nægir að athuga frumtölur á þessu bili ef þær upplýsingar eru til staðar. Sem dæmi er hægt að athuga hvort talan 143 sé frumtala með því skoða hvort einhver frumtalnanna 2, 3, 5, 7 og 11 gangi upp í 143. Við skoðum ekki 13 þar sem
. Í ljós kemur að 11 gengur 13 sinnum upp í 143, svo talan er ekki frumtala. Ástæðan fyrir því að kvarðatrótin nægir er sú að ef einhver tala
gengur upp í
, þá er talan
svo leit okkar fram að kvarðatrótinni af
myndi finna þáttinn
.
- Reikniritið að ofan tekur
tíma sem er ekki margliða í stærð inntaksins (þ.e. fjöldi bita í
). Árið 2004 sýndu þrír nemendur við IIT Kanpur, þeir Agrawal, Kayal og Saxena, fram á að unnt er að athuga hvort tala sé frumtala eða ekki í tíma sem er margliða í fjölda bita í
.
Talið er að zetufall Riemanns geti gefið mikilvægar upplýsingar um dreifingu frumtalna.
Heimildir
- Manindra Agrawal, Neeraj Kayal og Nitin Saxena. „PRIMES is in P“, Annals of Mathematics, 160 (2) (2004): bls. 781-793.
Tenglar
🔥 Top keywords: ForsíðaXXX RottweilerhundarKerfissíða:Nýlegar breytingarKerfissíða:LeitBrúðkaupsafmæliBaskarBaskalandSniðaspjall:Lið í 1. deild karla í knattspyrnuFiann PaulListi yfir íslensk eiginnöfn karlmannaListi yfir íslensk mannanöfnListi yfir íslensk eiginnöfn kvenmannaVargsnigillHundadagarÓmar RagnarssonHúsafellssteininnBaskneskaListi yfir íslensk póstnúmerÓlympíuleikvangurinn í BerlínÓðinnSeinni heimsstyrjöldinWikipediaÍslandSpánnEvrópukeppni karla í knattspyrnuBaltasar KormákurListasafn Einars JónssonarKnattspyrnaWikipedia:Um verkefniðEvrópukeppnin í knattspyrnu 2024MynsturGylfi Þór SigurðssonReykjavíkEnska karlalandsliðið í knattspyrnuDonald TrumpFilippus 6. SpánarkonungurÞjóðvegur 1Evrópukeppnin í knattspyrnu 2021Wikipedia:Almennur fyrirvari