Množica praštevil

Uvod v matematiko
Naravna in cela števila
Računanje z izrazi
Deljivost
Racionalna števila
Množice
Realna števila
Enačbe in neenačbe
Koordinatni sistem
Linearna funkcija
Statistika

Množica praštevil

$\cal{P}=\lbrace 2,3,5,7,11,13,\ldots \rbrace$

To trditev bomo dokazali s protislovjem. Recimo, da je praštevil končno mnogo in je zadnje, največje praštevilo enako $p$. Zmnožimo vsa praštevila in k temu dodajmo $1$, dobimo število

$m=2\cdot 3 \cdot 5\cdot \ldots \cdot p +1$.

To število je večje od vseh preostalih praštevil in je lahko sestavljeno ali pa je praštevilo. Zagotovo ni deljivo z $2$, saj zanj velja $m=2k+1$. Prav tako ni deljivo s $3$, saj je oblike $m=3k'+1$. Na podoben način se prepričamo, da to novo število ni deljivo z nobenim izmed praštevil. Torej $m$ ni sestavljeno število, zato je praštevilo in je element začetne množice $\cal{P'}$. To pa seveda ne more biti res, saj je število $m$ večje od vseh praštevil iz množice $\cal{P'}$. Kje smo naredili napako v sklepanju? Na začetku, ko smo predpostavili, da je praštevil le končno mnogo. Ta dokaz pripisujejo Evklidu (400 let pr. n. št.).

Praštevila so po definiciji tista števila, ki imajo natanko dva delitelja, izmed katerih je eden enak $1$, drugi pa je enak številu samemu.

Število $2$ je najmanjše praštevilo, očitno je sodo. Če bi obstajalo še kako sodo praštevilo $p \gt 2$, bi to imelo vsaj tri delitelje ($1$, $2$ in $p$), kar pa je v nasprotju z definicijo. Torej so druga praštevila liha.

Ena od preprostejših metod za iskanje praštevil je Eratostenovo rešeto ali sito, ki je prikazano spodaj.

Eratostenovo sito je pripomoček za iskanje praštevil do poljubne velikosti. Spodaj se prikazuje rešeto za števila do $100$, zato jih najprej zapišemo v preglednico. Izločimo $1$, ker ni praštevilo, in obkrožimo $2$, ker je. Odtod naprej ponavljamo naslednje korake:

izločimo vse večkratnike zadnje obkroženega praštevila, saj niso praštevila;
najmanjše neizločeno število je praštevilo, ker ni večkratnik nobenega manjšega.

Postopek gre najprej počasi, potem pa vedno hitreje.

Kot zanimivost si oglej eno od novejših odkritij matematike - geometrijsko rešeto za iskanje praštevil (Matiyasevich-Stechkinovo rešeto).

Kot zanimivost še en prikaz odnosov med števili (avtor je Jason Davies). Števila, pri katerih se sekata le dve krivulji, so praštevila.

Čas	Praštevilo	Št. števk v zapisu
avgust 2008	$2^{43112609}-1$	$12978189$
marec 2007	$19249\cdot2^{13018586}+1$	$3918990$

Množica praštevil

$\cal{P}=\lbrace 2,3,5,7,11,13,\ldots \rbrace$

Ena od preprostejših metod za iskanje praštevil je Eratostenovo rešeto ali sito, ki je prikazano spodaj.

Praštevila so med naravnimi posejana brez prepoznavnega reda. Kljub temu številni matematiki poskušajo prikazati praštevila na kak posebno zanimiv način, v katerem so vidni vzorci.

Na spletu lahko najdeš informacije o različnih podmnožicah praštevil, ki jih druži skupna formula, ki pa ne zagotavlja, da so vsa po njej izračunana števila zares praštevila.

Naštevanje praštevil gre sprva hitro, z večjimi števili pa že nastopijo težave. Danes računalniki na več koncih sveta še vedno iščejo in dopolnjujejo seznam praštevil, ki je zelo pomemben.