Primtall og Eratostenes' sil

Primtallsfaktorisering

Hvis man ser på noen heltall vil man raskt oppdage at noen tall har flere faktorer, mens andre ikke har noen andre enn seg selv og 1. Vi kaller førstnevnte type tall for sammensatte tall. Tallene som bare har seg selv og 1 som faktor kaller vi primtall. Et viktig resultat i tallteorien er at primtallene er byggesteinene for alle andre tall:

Aritmetikkens fundamentalsetning

Et hvert tall <tex>n > 1</tex> kan skrives entydig som et produkt av primtall, når vi ser bort i fra rekkefølgen til faktorene.

Bevis

Aritmetikkens fundamentalteorem sier altså at du alltid kan faktorisere et tall til et produkt av primtall. Det sier videre at du bare kan gjøre dette på én måte (når vi ser bort i fra rekkefølgen til faktorene.)

Eksempel:

Vi har at

<tex>21 = 3 \cdot 7</tex>

<tex>102 = 2 \cdot 51 = 2 \cdot 3 \cdot 17</tex>

<tex>999 = 9 \cdot 111 = 3 \cdot 3 \cdot 3 \cdot 37</tex>

De tre sammensatte tallene kan altså skrives som et produkt av primtall. Hvis man ser bort i fra rekkefølgen til faktorene så er faktoriseringene ovenfor entydige. Det vil si at det garantert ikke finnes noen andre måter å faktorisere tallene på som et produkt av primtall.

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. Vi har antatt at det bare er <tex>k</tex> primtall. Siden <tex>a</tex> er større enn alle primtallene, må <tex>a</tex> være et sammensatt tall. Hvis <tex>a</tex> er sammensatt så gir aritmetikkens fundamentalsetning (se ovenfor) at <tex>a</tex> har en unik primtallsfaktorisering. Det betyr at minst ett av primtallene <tex>p_1, p_2, p_3, ..., p_k</tex> er en faktor 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>, 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 som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!

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

Erastotenes' 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>.