Primtall

Hva er primtall?

Alle heltall større enn 1 er delelige med minst to 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 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 mindre 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 likt på er at noen får alle bitene, eller at 13 personer får 1 bit hver.

Eratosthenes′ såld

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 neste 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 · b, der ab. 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 og med $\sqrt n$.

SkjermfilmSe 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

Teoremer om primtall

​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 · 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 = p1 · p2 · p3 · … · pr

Men et primtall kan naturligvis forekomme flere ganger, for eksempel er 12 = 2 · 2 · 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, noe vi uttrykker matematisk som $k \in \mathbb N$.

For eksempel er 40 = 23 · 51, her er k1 = 3, k2 = 1.

Det finnes uendelig mange primtall.

Beviset for dette er et såkalt reductio ad absurdum-bevis, der vi antar det motsatte av det vi vil bevise, og så påviser at antakelsen fører til en selvmotsigelse.

Det motsatte av at det finnes uendelig mange primtall er at det bare finnes et endelig antall primtall, la oss kalle dette antallet for r. Primtallene selv kaller vi p1, p2p3, … , pr. Her er p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, og så videre oppigjennom lista med primtall.

La oss kalle tallet vi får når vi multipliserer disse primtallene for A. Da vil A være delelig med samtlige av disse primtallene, for vi har jo at Ap1 · p2 · p3 · … · pr. Men A+1 vil ikke være delelig med noen av dem.

Ifølge fundamentalteoremet må likevel A+1, på linje med alle andre tall, være et unikt produkt av primtall. Og siden det ikke er noen av p1, p2p3, … , pr, må det finnes andre primtall enn disse. Påstanden om at det bare finnes et gitt antall, r, primtall kan derfor ikke være riktig. Utgangspunktet vårt, påstanden om at det finnes uendelig mange primtall, må derfor være riktig.

A+1 vil enten være et nytt primtall, eller tall satt sammen av andre primtallsfaktorer enn p1, p2p3, … , pr.

Eksempel 1:

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

​Eksempel 2:

Vi undersøker de seks første primtallene og får A+1 = 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031. Dette er et tall satt sammen av primtallsfaktorene 59 og 509.

Det vil finnes vilkårlig lange sekvenser med etterfølgende tall som ikke er primtall. Ta for eksempel tallet
4! = 4 · 3 · 2 · 1.
4! + 2 være delelig med 2.
4! + 3 vil være delelig med 3.
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, … n! + n

NB! Dette betyr ikke at vi alltid må helt opp til n! + 2 for å finne en sekvens med n−1 sammensatte tall. Lar vi for eksempel n = 6, får vi 6! = 720, og den etterfølgende sekvensen med n−1 = 6−1 = 5 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 (First Fifty Million Primes) en liste over de første 50 000 000 primtallene.

Primtallsfunksjoner i GeoGebra

I GeoGebra kan vi bruke funksjonen erprimtall til å avgjøre om et tall er et primtall eller ikke. Skriver vi for eksempel erprimtall(12) i inntastingsfeltet, svarer GeoGebra med  false i algebrafeltet. Skriver vi erprimtall(13), svarer GeoGebra med true

Vi kan primtallsfaktorisere et tall ved hjelp av funksjonen faktorer. GeoGebra presenterer da tallets faktorer i en matrise i algebrafeltet. Første kolonne inneholder primtallsfaktorene, andre kolonne hvor mange ganger hver enkelt faktor forekommer. Skriver vi for eksempel faktorer(294) i inntastingsfeltet, presenterer GeoGebra matrisen

$\begin{bmatrix}2 & 1\\3 & 1\\7 & 2\end{bmatrix}$ i algebrafeltet fordi 294 = 21 · 31 · 72.

Vi kan finne første primtall som kommer etter et vilkårlig tall med funksjonen nesteprimtall. Skriver vi for eksempel nesteprimtall(20) i inntastingsfeltet, svarer GeoGebra 23 i algebrafeltet. 

Tilsvarende kan vi finne siste primtall før et vilkårlig tall med funksjonen forrigeprimtall.

Største primtall

Det finnes ingen formel for å finne primtall, og 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 (Top Ten Record Primes) er det største primtallet som er kjent per september 2023 lik 282 589 933 − 1. Dette tallet har 24 862 048 sifre, skrev vi det ut med ett siffer per centimeter, ville det bli over 248 kilometer langt. Tallet ble registret 21. desember 2018. Tidligere rekorder stammer fra mars 2018, januar 2016 og mai 2013. Så det går en stund mellom hver gang et nytt største primtall blir funnet.

Primtallstvillinger

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 (Ten Largest Known Twin Primes) er den største primtallstvillingen som er kjent per september 2023 lik 2 996 863 034 895 · 21 290 000 − 1. Tallet har 388 342 sifre og ble registrert i september 2016. En vet ikke om det finnes uendelig mange primtallstvillinger.

Hypoteser om primtall

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 differansen 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 n2 + 1. For eksempel 22 + 1 = 5 og 42 + 1 = 17.

Men bortsett fra tallet 3 finnes det ingen primtall som er 1 mindre enn et kvadrattall, altså på formen n2 − 1.

Å begrunne dette er neste oppgave.

Oppgave 3:

Begrunn at det for n > 2 ikke finnes primtall på formen n2 − 1. Hint: Tredje kvadratsetning baklengs.

Se løsningsforslag

Mersenne-primtall og perfekte tall

I gammel tid fantes det en hypotese om at alle tall på formen 2n − 1 var primtall når n var primtall, men sammensatte tall ellers. For eksempel, for primtallet 2 er 22 − 1 = 3 et primtall, for primtallet 3 er 23 − 1 = 7 et primtall, og for det sammensatte tallet 4 er 24 − 1 = 15 et sammensatt tall. 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 2n − 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 11, får vi 211 − 1 = 2047, som er et sammensatt tall, 2047 = 23 · 89.

Primtall på formen 2n − 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.

En vet ikke om det finnes uendelig mange Mersenne-primtall. Ifølge primes.utm.edu (Ten Largest Known Mersenne Primes) er det største Mersenne-primtallet som er kjent per september 2023 lik 282 589 933 − 1, og det er også det største kjente primtallet, som nevnt tidligere. Alle de største primtallene som er kjent per september 2023 er Mersenne-primtall. Dette skyldes antakelig at tall på denne formen er de enkleste for en datamaskin å verifisere at virkelig er primtall.

Et perfekt tall er et tall som er lik summen av sine egne ekte faktorer, det vil si alle hele, positive 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)(2n − 1).

For n = 2 får vi 2(2 − 1)(22 − 1) = 2 · 3 = 6

For n = 3 får vi 2(3 − 1)(23 − 1) = 4 · 7 = 28

For n = 5 får vi 2(5 − 1)(25 − 1) = 16 · 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, beregne 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 $ \frac{\displaystyle n}{\displaystyle \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) ≈ 176,56. Det kan vi regne ut i GeoGebra ved å skrive Integral(1 / ln(x), 2, 1000) i inntastingsfeltet.

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