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

Det finnes uendelig mange primtall.

Bevis:

Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <tex>k</tex> stykker. Da har vi primtallene <tex>p_1, p_2, ..., p_k</tex>. Så ser vi på følgende tall:

<tex>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</tex>,

altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <tex>a</tex> er større enn alle primtallene, må <tex>a</tex> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <tex>a</tex> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <tex>p_1, p_2, p_3, ..., p_k</tex> er faktorer i <tex>a</tex>. Men vi har at

<tex>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</tex>

Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <tex>p_i</tex> (der <tex>i</tex> er et tall mellom 1 og <tex>k</tex>) er en faktor i <tex>a</tex> og dette tallet også er en faktor i tallet <tex>p_1 \cdot p_2 \cdot p_3 \dots p_k</tex> så kan vi faktorisere ut tallet <tex>p_i</tex> på venstre side. Men hvis <tex>p_i</tex> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <tex>k</tex> forskjellige primtall er gal -- altså finne det uendelig mange primtall!

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 <tex>n</tex> er sammensatt må minst én primfaktor være mindre eller lik <tex>\sqrt n</tex>.

Bevis

Dette beviser vi ved å se på hva som skjer dersom alle primfaktorene var større enn <tex>\sqrt n</tex>. Vi kan skrive <tex>n = ap</tex>, der <tex>p</tex> er en av primfaktorene og <tex>a</tex> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <tex>p \geq \sqrt n</tex> og <tex>a \geq \sqrt n</tex>. Da er

<tex>ap \geq \sqrt n \cdot \sqrt n = n</tex>

altså blir også produktet av faktorene i <tex>n</tex> større enn <tex>n</tex> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <tex>\sqrt n</tex>.

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 <tex>n</tex> kalles Eratostenes' sil (kalles også Eratostenes' såld.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.

Eratostenes' sil

Skriv opp alle tall i fra 2 til <tex>n</tex>. Utfør så følgende steg, start med tallet <tex>k=2</tex>.

• Stryk ut alle tall som går opp i <tex>k</tex> utenom <tex>k</tex> selv.
• Se på neste tall etter <tex>k</tex> som ikke er strøket ut. Dersom dette er større enn <tex>\sqrt n</tex> 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 <tex>n</tex>.