Praštevilo
Praštevilo je naravno število določene vrste. Vsako naravno število je enako 1 krat samo sebi. Če je število enako množenju s katerim koli drugim številom, potem se to število imenuje "sestavljeno število". Najmanjše sestavljeno število je 4, ker je 2 x 2 = 4. 1 ni sestavljeno število. Vsako drugo število je praštevilo. Praštevilska števila so števila, razen 1, ki niso enaka m x n (razen 1 x samo sebe). Najmanjše praštevilo je 2. Naslednja praštevila so 3, 5, 7, 11 in 13. Največjega praštevilskega števila ni.
Način nastanka praštevil je za matematike težaven problem. Kadar je število večje, je težje ugotoviti, ali je praštevilo. Eden od odgovorov je teorem o praštevilskih številih. Eden od nerešenih problemov je Goldbachova domneva.
O praštevilskih številih lahko razmišljamo še na drug način. Število 12 ni praštevilo, ker lahko iz njega naredimo pravokotnik s stranicama dolžine 4 in 3. Ta pravokotnik ima površino 12, ker je uporabljenih vseh 12 blokov. Tega ni mogoče narediti z 11. Ne glede na to, kako je pravokotnik urejen, bodo vedno ostali bloki, razen za pravokotnik s stranicama dolžin 11 in 1. 11 mora biti torej praštevilo.
Kako najti majhna praštevilska števila
Obstaja preprosta metoda za iskanje seznama praštevil. Ustvaril jo je Eratosten. Imenuje se Eratostenovo sito. V njem se ujamejo števila, ki niso praštevilska (kot v situ), praštevilska števila pa gredo skozi.
Metoda deluje s seznamom števil in posebnim številom, imenovanim b, ki se med izvajanjem metode spreminja. Med izvajanjem metode nekatera števila na seznamu obkrožite, druga pa prečrtate. Vsako obkroženo število je praštevilo in vsako prečrtano število je sestavljeno. Na začetku so vsa števila navadna: niso obkrožena in niso prečrtana.
Metoda je vedno enaka:
- Na list papirja napišite vsa cela števila od 2 do preverjanega števila. Ne zapišite števila 1. Preidite na naslednji korak.
- Začnite z b, ki je enako 2. Pojdite na naslednji korak.
- Na seznamu obkrožite b. Pojdite na naslednji korak.
- Začni z b, preštej še b na seznamu in to številko prečrtaj. Ponavljajte štetje še za b številk in prečrtavanje številk do konca seznama. Preidite na naslednji korak.
- (Na primer: Če je b 2, obkrožite 2 in prečrtajte 4, 6, 8 itd. Če je b 3, boste obkrožili 3 in prečrtali 6, 9, 12 itd. Število 6 in 12 je že prečrtano. Ponovno ju prečrtajte.)
- Povečajte b za 1. Pojdite na naslednji korak.
- Če je bil b prečrtan, se vrnite na prejšnji korak. Če je b številka s seznama, ki ni bila prečrtana, pojdite na 3. korak. Če b ni na seznamu, pojdite na zadnji korak.
- (To je zadnji korak.) Končali ste. Vsa praštevilska števila so obkrožena, vsa sestavljena števila pa prečrtana.
Na primer, to metodo lahko uporabite za seznam števil od 2 do 10. Na koncu bodo obkrožena števila 2, 3, 5 in 7. To so praštevila. Številke 4, 6, 8, 9 in 10 bodo prečrtane. To so sestavljena števila.
Ta metoda ali algoritem traja predolgo za iskanje zelo velikih praštevil. Vendar je manj zapleten kot metode, ki se uporabljajo za zelo velika praštevilska števila, na primer Fermatov test primarnosti (test, s katerim ugotovimo, ali je število praštevilo ali ne) ali Miller-Rabinov test primarnosti.
Za kaj se uporabljajo praštevila
Prva števila so zelo pomembna v matematiki in računalništvu. V nadaljevanju je navedenih nekaj primerov uporabe v resničnem svetu. Zelo dolga števila je težko rešiti. Težko je najti njihove prafaktorje, zato se za šifriranje in tajne kode največkrat uporabljajo števila, ki so verjetno praštevila.
- Večina ljudi ima bančno kartico, s katero lahko na bankomatu dvignejo denar s svojega računa. Ta kartica je zaščitena s tajno kodo za dostop. Ker mora biti koda tajna, je na kartici ni mogoče shraniti v odprtem besedilu. Za tajno shranjevanje kode se uporablja šifriranje. Pri šifriranju se uporabljajo množenje, deljenje in iskanje ostankov velikih praštevil. V praksi se pogosto uporablja algoritem, imenovan RSA. Uporablja kitajski teorem o preostanku.
- Če ima nekdo digitalni podpis za svoje e-poštno sporočilo, se uporablja šifriranje. S tem je zagotovljeno, da nihče ne more ponarediti njegovega e-poštnega sporočila. Pred podpisovanjem se ustvari hash vrednost sporočila. Ta se nato združi z digitalnim podpisom, da nastane podpisano sporočilo. Uporabljene metode so bolj ali manj enake kot v prvem primeru zgoraj.
- Iskanje največjega doslej znanega prime je postalo svojevrsten šport. Če je število veliko, je preverjanje, ali je praštevilo praštevilo, lahko težavno. Največja kadar koli znana praštevilska števila so običajno Mersennova števila, saj je najhitrejši znani test za preverjanje prvobitnosti Lucas-Lehmerjev test, ki temelji na posebni obliki Mersennovih števil. Skupina, ki išče Mersennova praštevilska števila, je tukaj[1].
Vprašanja in odgovori
V: Kaj je praštevilo?
O: Praštevilo je naravno število, ki ga ni mogoče deliti z nobenim drugim naravnim številom, razen z 1 in samim seboj.
V: Kaj je najmanjše sestavljeno število?
O: Najmanjše sestavljeno število je 4, ker je 2 x 2 = 4.
V: Katera so naslednja praštevilska števila za 2?
O: Naslednja praštevilska števila za 2 so 3, 5, 7, 11 in 13.
V: Ali obstaja največje praštevilo?
O: Ne, največje praštevilo ne obstaja. Množica praštevil je neskončna.
V: Kaj pravi temeljni stavek aritmetike?
O: Temeljni stavek aritmetike pravi, da lahko vsako pozitivno celo število zapišemo kot zmnožek praštevil na edinstven način.
V: Kaj je Goldbachova domneva?
O: Goldbachova domneva je nerešen problem v matematiki, ki pravi, da lahko vsako celo število, večje od dva, izrazimo kot vsoto dveh praštevil.
V: Kdo je zapisal dokaz, da ni največjega praštevilskega števila?
O: Evklid je zapisal dokaz, da ni največjega praštevilskega števila.
