Primtall

Alle heltall større enn $1$ er delelige med minst to andre positive heltall, nemlig $1$ og tallet selv. Finnes det ikke flere positive heltall det er delelig med, er tallet et primtall. I motsatt fall er det et sammensatt tall. Det er vanlig å bruke symbolet $p$ for å representere et primtall.

Studerer vi de første naturlige tallene, ser vi at:

  • $1$ ikke er et primtall fordi det ikke er større enn $1$.
     
  • $2$ er et primtall fordi det bare er delelig med $1$ og seg selv.
     
  • $3$ er et primtall fordi det bare er delelig med $1$ og seg selv.
     
  • $4$ ikke er et primtall fordi det, i tillegg til å være delelig med $1$ og seg selv, også er delelig med $2$. Vi har at ${\large \frac{4}{2}} = 2$.
     
  • Alle partall er delelige med $2$, derfor er $2$ det eneste partallet som er et primtall.

På ei tallinje vil det bare være linjestykker med lengde $1$ eller lengde lik primtallet selv som treffer i primtallet hvis vi legger dem etter seg selv, slik det er vist under for $p = 7$.

Illustrasjon av at ingen tall går opp i 7

Og det er umulig å å dele et primtall opp i blokker med like mange elementer i hver. Derfor litt ironisk at sjokoladen Smil ifølge reklamen er "skapt for å deles", når den inneholder 13 biter, og 13 er et primtall. Den eneste måten å dele en Smil på er at noen får alle bitene, eller at 13 personer får 1 bit hver.

For å lage ei liste med alle primtall opp til et gitt tall, $n$, kan vi bruke en metode som heter Eratosthenes' såld, der vi i gjentatte operasjoner stryker multipler av primtall, inntil vi står igjen med bare primtallene. Metoden kan beskrives algoritmisk slik:

  1. Lag ei liste av påfølgende heltall fra $2$ til $n$.
     
  2. La $p$ til å begynne med være lik $2$, det første primtallet.
     
  3. Stryk alle multipler av $p$ fra lista.
     
  4. Finn det første tallet større enn $p$ som står igjen på lista. Dette tallet er det neste primtallet. Sett $p$ lik dette tallet.
     
  5. Gjenta trinn 3 og 4 inntil $p$ er større enn $\sqrt n$.
     
  6. Alle gjenværende tall på lista er nå primtall.

Grunnen til at vi ikke trenger å sjekke høyere tall enn $\sqrt n$, er at hvis et tall, $n$, ikke er et primtall, kan det faktoriseres som $a \cdot b$, der $a \le b$. Hvis tallet er et kvadrattall, vil $a = b = \sqrt n$. I motsatt fall vil $a < \sqrt n$ og $b > \sqrt n$. I begge tilfeller ser vi at vi vil ha funnet $a$ når vi har sjekket alle tall opp til $\sqrt n$.

ScreencastSe film der Eratosthenes' såld brukes på tallene opp til 60
 

Oppgave 1:

Bruk metoden med Eratosthenes' såld til å finne alle primtall opp til $120$. Hvilket primtall er det største du trenger å stryke multipler av?

​Se løsningsforslag

​Dersom et primtall går opp i et tall som er et produkt av to faktorer, vil det gå opp i minst én av faktorene. I motsatt fall måtte vi jo funnet litt av primtallet i den ene faktoren og litt i den andre, noe som er umulig siden primtall ikke kan deles opp. Kaller vi primtallet $p$ og faktorene $a$ og $b$, kan vi formulere dette som et teorem slik:

$\fbox{$\text{Hvis } p \mid ab \text{, vil } p \mid a \text{ eller }p \mid b$}$

Oppgave 2:

$900$ kan skrives som $20 \cdot 45$. Bruk teoremet over til å avgjøre om følgende er riktig. Begrunn svaret.

  1. $3$ går opp i $900$. Da går $3$ opp i $45$.
     
  2. $5$ går opp i $900$. Da kan ikke $5$ gå opp i både $20$ og $45$.

Se løsningsforslag

Så kommer vi til det som kalles tallteoriens fundamentalteorem. Det slår fast at ethvert heltall, $n > 1$, kan skrives som et produkt av primtall på en entydig måte.

Hvis dette hadde vært unike primtall, ville vi kunne skrevet det slik: $n = p_1 \cdot p_2 \cdot p_3 \cdot \, \dots \, \cdot p_r$.

Men et primtall kan naturligvis forekomme flere ganger, for eksempel er $12 = 2 \cdot 2 \cdot 3$. Tar vi høyde for dette, får vi:

$\fbox{$n = p_1^{\large k_{\Large 1}} \cdot p_2^{\large k_{\Large 2}} \cdot p_3^{\large k_{\Large 3}} \cdot \, \dots \, \cdot p_r^{\large k_{\Large r}}$}$

Her er $k$ et naturlig tall, $k \in \mathbb N$.

For eksempel er $40 = 2^3 \cdot 5^1$, her er $k_1 = 3, k_2 = 1$.

Det finnes uendelig mange primtall. Beviset for dette er et såkalt reductio ad absurdum-bevis. I et slikt bevis antar vi det motsatte av det vi vil bevise, og konkluderer med at antakelsen fører til et umulig resultat. Vi skal ikke gjengi beviset her, bare enkelt forklare hva det går ut på. Vi starter altså med å anta det motsatte av det vi vil bevise, nemlig at det faktisk bare finnes et endelig antall primtall. Vi kaller disse primtallene $p_1, p_2, p_3, \dots, p_r$. Når vi multipliserer dem, får vi et nytt tall som er delelig med alle disse primtallene. Men adderer vi $1$ til dette tallet, får vi et tall som ikke er delelig med noen av dem. Vi kaller det $P = p_1 \cdot p_2 \cdot p_3 \cdot \, \dots \, \cdot p_r + 1$. Men fundamentalteoremet sier at $P$ enten må være et primtall eller et unikt produkt av primtall. Er det et primtall, så har vi funnet et nytt primtall som ikke var med i vår begrensede mengde. Er det ikke et primtall, så må det bestå av et antall primtallsfaktorer som heller ikke var med i vår mengde, for ingen av disse var jo faktorer i $P$.

Eksempel 1:

Vi undersøker de tre første primtallene og får $P = 2 \cdot 3 \cdot 5 + 1 = 31$. Dette er et nytt primtall, men det er ikke første primtall etter $5$, vi har hoppet over primtallene $7, 11, 13, 17, 19, 23, 29$.

Hvis vi systematisk tar for oss de første primtallene, kan det se ut som vi har funnet en oppskrift på å generere nye primtall. For $2 + 1 = 3$ er et primtall. $2 \cdot 3 + 1 = 7$ er et primtall. $2 \cdot 3 \cdot 5 + 1 = 31$ er et primtall. $2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211$ er et primtall. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311$ er et primtall. Men går vi ett skritt videre og tar med $13$, får vi ikke et primtall, som vi skal se i eksempel 2. Dette illustrerer hvor feil det kan være å trekke generelle konklusjoner på grunnlag av enkelteksempler.

​Eksempel 2:

Vi undersøker de seks første primtallene og får $P = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$. Dette er ikke et primtall, for det kan primtallsfaktoriseres som $30031 = 59 \cdot 509$.

I GeoGebra kan vi bruke funksjonen ErPrimtall til å avgjøre om et tall er et primtall eller ikke. Vi kan primtallsfaktorisere et tall ved hjelp av funksjonen Faktorer. Vi kan også finne første primtall som kommer etter et vilkårlig tall med funksjonen NestePrimtall, eller siste primtall før et vilkårlig tall med funksjonen ForrigePrimtall.

Det vil finnes vilkårlig lange følger med etterfølgende tall som ikke er primtall. Ta for eksempel tallet $4! = 4 \cdot 3 \cdot 2 \cdot 1$.  Da vil $4! + 2$ være delelig med $2$. $4! + 3$ vil være delelig med $3$, og $4! + 4$ vil være delelig med $4$. Vi får altså en følge av minst tre tall som ikke er primtall. Bak et vilkårlig tall, $n!$, vil det alltid følge $n – 1$ tall som ikke er primtall, nemlig $n! + 2, n! + 3, \dots, n! + n$.

NB! Dette betyr ikke at vi må helt opp til $n! + 2$ for å finne en følge med $n – 1$ sammensatte tall. Lar vi for eksempel $n = 6$, får vi $6! = 720$, og følgen med fem sammensatte tall blir $722, 723, 724, 725, 726$. Men allerede etter tallet $23$ følger fem sammensatte tall, $24, 25, 26, 27, 28$.

På Internett kan vi finne lister over primtall, for eksempel har primes.utm.edu en liste over de første 50 000 000 primtallene.

Spesielle primtall

Det finnes ingen formel for å finne primtall, en må basere seg på omstendelige utregninger for å vise at et tall virkelig er et primtall. Med moderne datateknologi kan imidlertid beregninger gjøres svært fort, og en har derfor funnet fram til svært høye primtall. Ifølge primes.utm.edu (largest primes) er det største primtallet som er kjent per januar 2018 lik $2^{\large 77\,232\,917} – 1$. Dette tallet har 23 249 425 sifre, skrev vi det ut med ett siffer per centimeter, ville det bli over 232 kilometer langt. Tallet ble funnet i januar 2018. Tidligere rekorder stammer fra januar 2016, februar 2013 og juni 2009. Så det går en stund mellom hver gang et nytt største primtall blir funnet.

Dersom to tall, $p$ og $p + 2$, begge er primtall, kalles de primtallstvillinger. Eksempel på primtallstvillinger er $\{5, 7\}$, $\{11, 13\}$, og $\{17, 19\}$. Primtallstvillingene blir sjeldnere når $p$ blir større. Ifølge primes.utm.edu (twin primes) er den største primtallstvillingen som er kjent per august 2017 lik $2\,996\,863\,034\,895 \cdot 2^{\large 1\,290\,000} – 1$. Tallet har 388 342 sifre og ble funnet i september 2016. En vet ikke om det finnes uendelig mange primtallstvillinger.

To hypoteser om primtall er at ethvert partall større enn $2$ kan skrives som en sum av to primtall, og at ethvert partall kan skrives som differensen mellom to primtall på uendelig mange måter. Dette er altså påstander som en tror er riktige, men som ikke er bevist. Ingen har heller klart å komme opp med eksempler som motbeviser påstandene. Så her er en sjanse til å bli historisk!

En annen hypotese er at det finnes uendelig mange primtall som er $1$ større enn et kvadrattall, altså på formen $n^2 + 1$. For eksempel $2^2 + 1 = 5$ og $4^2 + 1 = 17$. Men bortsett fra tallet $3$ finnes det ingen primtall som er $1$ mindre enn et kvadrattall, altså på formen $n^2 – 1$. Å begrunne dette er neste oppgave.

Oppgave 3:

Begrunn at det for $n > 2$ ikke finnes primtall på formen $n^2 – 1$. Hint: Tredje kvadratsetning.

Se løsningsforslag

I gammel tid fantes det en hypotese om at alle tall på formen $2^n – 1$ var primtall når $n$ var primtall, men sammensatte tall ellers. For eksempel, for primtallene $n = 2$ og $n =3$, er $2^2 – 1 = 3$ og $2^3 – 1 = 7$ primtall. Mens for $n = 4$, som ikke er primtall, er $2^4 – 1 = 15$ ikke et primtall. Men bare halvparten av påstanden er riktig:

$\fbox{$\text{Hvis } n \text{ er et sammensatt tall, er } 2^n – 1 \text{ et sammensatt tall}$}$

Av dette følger at hvis $2^n -1$ ikke er et sammensatt tall, er $n$ ikke et sammensatt tall. Med andre ord:

$\fbox{$\text{Hvis } 2^n – 1 \text{ er et primtall, er } n \text{ et primtall}$}$

Men det motsatte er ikke alltid riktig. Bruker vi for eksempel primtallet $n = 11$, får vi $2^{11} – 1 = 2047$, som er et sammensatt tall, $2047 = 23 \cdot 89$.

Primtall på formen $2^n – 1$ kalles Mersenne-primtall, etter den franske munken Marin Mersenne. De første $n$ som gir Mersenne-primtall er $2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127$.

Ifølge primes.utm.edu (largest primes) er de 7 største primtallene som er kjent per januar 2018 Mersenne-primtall. Dette skyldes antakelig at tall på denne formen er den enkleste for en datamaskin å verifisere at virkelig er primtall. Det finnes per januar 2018 i alt 50 kjente Mersenne-primtall. En vet ikke om det finnes uendelig mange Mersenne-primtall.

Et perfekt tall er et tall som er lik summen av sine egne ekte faktorer, det vil si alle hele tall det kan deles med, som ikke er lik tallet selv. For eksempel er $6 = 1 + 2 + 3$ et perfekt tall, det samme er $28 = 1 + 2 + 4 + 7 + 14$.

Det viser seg at tallene, $n$, som gir Mersenne-primtall produserer perfekte tall etter formelen $2^{( n – 1)} (2^n – 1)$.

For $n = 2$ får vi $2^{( 2 – 1)}(2^2 – 1) = 2 \cdot 3 = 6$

For $n = 3$ får vi $2^{( 3 – 1)}(2^3 – 1) = 4 \cdot 7 = 28$

For $n = 5$ får vi $2^{( 5 – 1)}(2^5 – 1) = 16 \cdot 31 = 496$

Oppgave 4:

De tre første perfekte tallene er $6$, $28$ og $496$. Hva blir det fjerde perfekte tallet? Hint: Bruk formelen over og lista over $n$ som gir Mersenne-primtall.

Se løsningsforslag

Primtallsetningen

Kjenner vi et oddetall, $n$, og vil finne neste oddetall, vet vi at det må bli $n + 2$. Kjenner vi et tall, $m$, i fem-gangen og vil finne det neste, vet vi at det må bli $m + 5$. Noe slikt system finnes ikke for primtall. Vi kan ikke ut fra et primtall, $p$, si hva det neste primtallet er. Men primtallene blir færre og færre jo lenger ut på tallinja vi går. Dette er jo rimelig, for jo større tallene er, jo flere mulige primtallsfaktorer finnes.

En har funnet ut at uttrykket ${\large \frac{n}{\ln n}}$ gir et anslag over hvor mange primtall det finnes som ikke er høyere enn $n$.

Uttrykket er altså ikke helt nøyaktig, men gir kun et anslag. Det finnes for eksempel 168 primtall som ikke er høyere enn $n = 1000$, mens formelen gir ${\large \frac{1000}{\ln 1000}} \approx 144{,}7$.

Anslaget blir imidlertid mer og mer nøyaktig jo større $n$ blir. Det virkelige antall primtall og anslaget blir like når $n$ blir uendelig stor. Dette er primtallsetningen, som vi matematisk kan uttrykke slik, der $p(n)$ er det virkelige antall primtall lavere enn $n$:

$\fbox{Primtallsetningen: ${\displaystyle \lim_{n \to \infty}}\; \frac{\displaystyle \text{  }p(n)\text{  }}{\frac{\displaystyle n}{\displaystyle \ln n}} = 1$}$

Oppgave 5:

Gjør et anslag over hvor mange primtall det finnes som er lavere enn 5 000 000.

Se løsningsforslag

Primtallsetningen ble foreslått av matematikeren Carl Friedrich Gauss på slutten av syttenhundretallet og bevist på slutten av attenhundretallet. Siden har en imidlertid kommet fram til en funksjon som gir et mye bedre anslag over antall primtall:

$li(n) = \int \limits_2^n \frac{\displaystyle 1}{\displaystyle \ln x}dx$

For eksempel er $li(1000) \approx 176{,}56$.

Kilder

  • Breiteig, T. (2007). Bak tallene. Innføring i tallteori. Kompendium, Universitetet i Agder.
  • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
  • primes.utm.edu
  • Wikipedia