7.3 Primtall og primtallsfaktorisering

Tallenes byggesteiner

Tenk på LEGO. Med bare noen grunnklosser kan du bygge nesten hva som helst -- hus, biler, romskip. I matematikken har vi noe lignende: primtall. De er de grunnleggende byggesteinene som alle andre tall er satt sammen av.

Tallet $12$ kan for eksempel deles opp i $2 \times 2 \times 3$. Verken $2$ eller $3$ kan deles videre -- de er «udelelige». Nettopp dette er det som gjør dem til primtall.

Hva er et primtall?

Et primtall er et naturlig tall større enn $1$ som bare er delelig med $1$ og seg selv. De første primtallene er:

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots$$

Et tall større enn $1$ som ikke er et primtall, kalles et sammensatt tall -- det betyr at det har flere enn to faktorer. For eksempel er $12$ sammensatt fordi det har faktorene $1, 2, 3, 4, 6, 12$.

Noen viktige spesialtilfeller: Tallet $1$ er verken primtall eller sammensatt -- det er en egen kategori. Og $2$ er det eneste partalls-primtallet. Alle andre partall er delelige med $2$ og dermed sammensatte.

Hvordan sjekker du om et tall er primtall? Du trenger bare å teste deling med primtall opp til kvadratroten av tallet. For å sjekke $67$, beregner vi $\sqrt{67} \approx 8{,}2$ og sjekker deling med $2, 3, 5$ og $7$. Ingen av dem går opp, så $67$ er et primtall. Men for $51$ finner vi at $51 \div 3 = 17$, så $51 = 3 \times 17$ er sammensatt.

Det finnes uendelig mange primtall -- dette beviste den greske matematikeren Euklid for over $2300$ ar siden!

Eratosthenes' sil og primtallsfaktorisering

Den greske matematikeren Eratosthenes (276--194 f.Kr.) fant en elegant metode for å finne alle primtall opp til et gitt tall. Skriv opp alle tall fra $2$ og oppover. Begynn med $2$ (det første primtallet) og stryk alle multipler av $2$: $4, 6, 8, 10, \ldots$ Neste tall som ikke er streket ut er $3$ -- stryk alle multipler av $3$. Fortsett med $5$, $7$, og så videre. Når du har kommet til $\sqrt{n}$ (der $n$ er det største tallet på listen), er alle tall som ikke er streket ut, primtall. For tall opp til $50$ gir dette $15$ primtall: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$.

Nå til det virkelig kraftige verktyet: primtallsfaktorisering. Aritmetikkens fundamentalteorem sier at hvert naturlig tall større enn $1$ kan skrives som et produkt av primtall på nøyaktig en måte (bortsett fra rekkefølgen). For å finne faktoriseringen bruker vi et faktortre: del på det minste primtallet som går opp, del kvotienten på nytt, og fortsett til du står igjen med $1$.

For eksempel: $180 \div 2 = 90$, $90 \div 2 = 45$, $45 \div 3 = 15$, $15 \div 3 = 5$, $5 \div 5 = 1$. Altså er $180 = 2^2 \times 3^2 \times 5$.

SFF og MFF -- nyttige verktøy

Primtallsfaktorisering gir oss to kraftige verktøy: Største felles faktor (SFF) og Minste felles multiplum (MFF).

SFF er det største tallet som går opp i både $a$ og $b$. For å finne den: velg den laveste potensen av hvert felles primtall. MFF er det minste tallet som både $a$ og $b$ går opp i. For å finne det: velg den høyeste potensen av alle primtall som forekommer.

La oss finne SFF og MFF av $60$ og $84$:
- $60 = 2^2 \times 3 \times 5$
- $84 = 2^2 \times 3 \times 7$

SFF: Felles primtall er $2$ og $3$, med laveste potenser: $2^2 \times 3 = 12$.
MFF: Alle primtall med høyeste potenser: $2^2 \times 3 \times 5 \times 7 = 420$.

En nyttig kontroll: $\text{SFF} \times \text{MFF} = 12 \times 420 = 5040 = 60 \times 84$.

Disse verktøyene er overraskende praktiske. Tenk deg at du har $24$ rode roser og $36$ hvite roser og vil lage buketter der alle har like mange av hver farge uten at noen roser blir til overs. Antall buketter er SFF av $24$ og $36$, altså $12$. Eller tenk på to busser som er på holdeplassen samtidig klokka $08{:}00$ -- buss A går hvert $12$. minutt og buss B hvert $18$. minutt. De er på holdeplassen samtidig igjen etter MFF av $12$ og $18$ minutter, altså $36$ minutter -- klokka $08{:}36$.

Oppsummering

Primtall er tallenes byggesteiner -- naturlige tall større enn $1$ som bare er delelige med $1$ og seg selv. $2$ er det minste (og eneste partalls-) primtallet, og $1$ er verken primtall eller sammensatt. Eratosthenes' sil lar oss finne alle primtall opp til et gitt tall.

Primtallsfaktorisering betyr å skrive et tall som et produkt av bare primtall, og dette kan gjores på nøyaktig en måte. Med primtallsfaktorisering finner vi enkelt SFF (velg laveste potens av felles primtall) og MFF (velg høyeste potens av alle primtall). En nyttig sjekk: $\text{SFF}(a,b) \times \text{MFF}(a,b) = a \times b$.