Frumtala

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 breyta

Þæ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ð $P=\{p_{1},p_{2},\dots ,p_{n}\}$ tákna mengi með endanlegan fjölda staka sem innihéldi allar frumtölurnar. Skoðum töluna $t=p_{1}\cdot p_{2}\cdot \dots \cdot p_{n}+1$ . Sérhver frumtala í $P$ skilar þá 1 í leif þegar henni er deilt í $t$ . En þá er $t$ annað hvort frumtala sjálf sem er stærri en þær sem eru í $P$ , eða þá að hún er margfeldi frumtalna sem eru ekki meðal þeirra í $P$ . Hvoru tveggja er mótsögn, svo það fær ekki staðist að $P$ 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 $2^{57885161}-1$ , 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 $p$ er frumtala, og $a$ er ósamþátta $p$ , þá er $a^{p-1}\equiv 1({\text{mod }}p)$ . 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 breyta

Ef við lítum á $p_{1},p_{2},\dots$ sem óendanlega runu frumtalna, þá segir frumtalnasetningin okkur að frumtalan $p_{n}$ sé u.þ.b. $n\cdot \ln(n)$ , og að matið batnar eftir því sem $n$ 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 $t$ sé frumtala með því að prófa að deila sérhverri frumtölu $p\leq {\sqrt {t}}$ í $t$ 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 ${\sqrt {t}}<12$ . Í 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 $b>{\sqrt {t}}$ gengur upp í $t$ , þá er talan $a={\frac {t}{b}}<{\frac {t}{\sqrt {t}}}={\sqrt {t}}$ svo leit okkar fram að kvarðatrótinni af $t$ myndi finna þáttinn $a$ .
Reikniritið að ofan tekur $O({\sqrt {n}})$ tíma sem er ekki margliða í stærð inntaksins (þ.e. fjöldi bita í $n$ ). Á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 í $n$ .

Talið er að zetufall Riemanns geti gefið mikilvægar upplýsingar um dreifingu frumtalna.

Heimildir breyta

Manindra Agrawal, Neeraj Kayal og Nitin Saxena. „PRIMES is in P“, Annals of Mathematics, 160 (2) (2004): bls. 781-793.

Tenglar breyta

Fun With Prime Numbers