Primtall og Eratostenes' sil
Primtallsmysteriet
Primtallene har forbløffet matematikere i tusener av år. De dukker opp på nærmest tilfeldige steder på tallinjen. Det er steder på tallinjen hvor man har to naboprimtall nesten ved siden av hverandre, mens det andre steder kan være flere tusen sammensatte tall mellom to primtall. Primtallgåten er i stor grad uløst, men det er gjort flere fremskritt når det gjelder forståelsen av primtallene. Et veldig viktig resultat er blant annet at det finnes uendelig mange primtall. Dette ble bevist av den greske matematikeren Euklid for over 2000 år siden.
Uendelig mange primtall
Påstand: Det finnes uendelig mange primtall.
Bevis:
Strategi: Bevis ved motsigelse
Anta at det kun finnes et endelig antall primtall. Vi kan si at det er
Så ser vi på følgende tall:
Siden
Nå ser vi at siden i alle fall et av primtallene, la oss kalle det
Beviset ovenfor regnes av mange som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og om primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg utover på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!
Primtallstesting og Eratostenes' sil
Ovenfor har vi sett at det finnes uendelig mange primtall. Men vi vet ingenting om hvilke tall som er primtall og ikke.
For å teste om et tall er primtall kan vi benytte aritmetikkens fundamentalteorem. Det sier oss at dersom tallet ikke er et primtall, må det være et sammensatt tall med en unik primtallsfaktorisering, der hver primfaktor i alle fall er mindre enn tallet selv. Med andre ord kan vi teste om et tall er primtall ved å dele det på forskjellige primtall mellom 2 og tallet selv. Hvis vi får et helt tall når vi deler på et av primtallene, må dette primtallet være et faktor i tallet vårt, og da er ikke tallet vårt et primtall. Men dersom vi fortsetter å dele på primtall og vi ikke får et heltall noen av gangene, må tallet være et primtall. Men kan vi gjøre dette enda enklere?
Dersom et tall
er sammensatt må minst én primfaktor være mindre eller lik .
Bevis
Dette beviser vi ved å se på hva som skjer dersom alle primfaktorene var større enn. Vi kan skrive , der er en av primfaktorene og er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både og . Da er
altså blir også produktet av faktorene i
større enn selv. Dette er umulig, og minst en av faktorene må altså være mindre enn .
Dette gjør det betraktelig enklere å bestemme om et tall er primtall eller ikke. Det ovenfor sier jo at hvis et tall er sammensatt, så må det være delelig på et primtall som er mindre enn kvadratorten av tallet. Det vil si at hvis vi deler et tall på alle primtallene som er mindre eller lik kvadratroten av tallet og ingen av divisjonene går opp (gir et helt tall) så kan ikke tallet være sammensatt -- det må være et primtall.
Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss alle primtallene fra 2 og opp til et tall
Eratostenes' sil
Skriv opp alle tall i fra 2 til
. Utfør så følgende steg, start med tallet .
- Stryk ut alle tall som går opp i
utenom selv. - Se på neste tall etter
som ikke er strøket ut. Dersom dette er større enn er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet. Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn
.