2.1 Primtall og delelighetsregler

Tallenes atomer

I kjemien er alt bygget opp av atomer. Vann er hydrogen pluss oksygen. Salt er natrium pluss klor. Atomene er de minste byggesteinene -- de kan ikke brytes ned videre.

I matematikken har vi noe lignende: primtall. De er tallenes atomer. Alle heltall større enn $1$ kan bygges opp ved å gange primtall sammen, og primtallene selv kan ikke deles videre (uten å få $1$ eller seg selv).

Hva mener vi med det? Ta tallet $12$. Vi kan skrive $12 = 2 \cdot 6 = 2 \cdot 2 \cdot 3$. Her er $2$ og $3$ primtall -- de kan ikke deles opp i mindre faktorer. Tallet $12$ er altså «bygget» av to toere og én treer. Men hva med $7$? Den eneste måten å skrive $7$ som et produkt er $1 \cdot 7$. Det finnes ingen andre hele tall som ganger sammen og gir $7$. Derfor er $7$ et primtall.

Definisjon: Et primtall er et naturlig tall større enn $1$ som bare er delelig med $1$ og seg selv. Tall som ikke er primtall (og er større enn $1$) kalles sammensatte tall.

De første primtallene

La oss se på de minste naturlige tallene og sortere dem:

Delelighetsregler -- snarveier for å sjekke deling

Å avgjøre om et tall er et primtall krever at vi sjekker om det er delelig med mindre tall. Men å dele store tall kan ta tid. Heldigvis finnes det delelighetsregler -- snarveier som lar deg avgjøre delelighet ved å se på sifrene:

Delelig med $2$: Siste siffer er partall ($0, 2, 4, 6, 8$).
- $374$: siste siffer er $4$ -- delelig med $2$ ✓
- $891$: siste siffer er $1$ -- ikke delelig med $2$ ✗

Delelig med $3$: Tverrsummen (summen av sifrene) er delelig med $3$.
- $726$: tverrsum $= 7 + 2 + 6 = 15$. Er $15$ delelig med $3$? Ja, $15 = 3 \cdot 5$ ✓
- $340$: tverrsum $= 3 + 4 + 0 = 7$. Er $7$ delelig med $3$? Nei ✗

Delelig med $5$: Siste siffer er $0$ eller $5$.
- $235$: siste siffer er $5$ ✓
- $748$: siste siffer er $8$ ✗

Delelig med $9$: Tverrsummen er delelig med $9$.
- $738$: tverrsum $= 7 + 3 + 8 = 18 = 9 \cdot 2$ ✓
- $214$: tverrsum $= 2 + 1 + 4 = 7$ ✗

Delelig med $10$: Siste siffer er $0$.
- $530$ ✓, $531$ ✗

Merk at regelen for $3$ og $9$ begge bruker tverrsummen. Siden $9 = 3 \cdot 3$, er ethvert tall som er delelig med $9$ automatisk delelig med $3$ -- men ikke omvendt.

Eratosthenes' sil -- å finne alle primtall

For over 2200 år siden oppfant den greske matematikeren Eratosthenes en genial metode for å finne alle primtall opp til et gitt tall. Metoden kalles Eratosthenes' sil (eller «sieve of Eratosthenes»), og den fungerer som et filter:

Slik gjør du for å finne alle primtall opp til $50$:

1. Skriv opp alle tall fra $2$ til $50$.
2. Start med det minste tallet ($2$). Det er et primtall. Stryk alle multipler av $2$: $4, 6, 8, 10, 12, \ldots$
3. Neste ustrykte tall er $3$. Det er et primtall. Stryk alle multipler av $3$: $6, 9, 12, 15, \ldots$ (noen er allerede strøket).
4. Neste ustrykte tall er $5$ (fordi $4$ ble strøket i steg 2). Det er et primtall. Stryk alle multipler av $5$: $10, 15, 20, 25, \ldots$
5. Neste ustrykte tall er $7$. Det er et primtall. Stryk alle multipler av $7$: $14, 21, 28, 35, 42, 49$.
6. Neste ustrykte tall er $11$. Men $11^2 = 121 > 50$, så vi er ferdige!

Alle ustrykte tall er primtall: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$.

Hvorfor stopper vi ved $\sqrt{50} \approx 7$? Fordi hvis et sammensatt tall $n$ har en faktor større enn $\sqrt{n}$, må det også ha en faktor som er mindre enn $\sqrt{n}$. Denne lille faktoren er allerede fanget opp av silingen.

Praktisk tips: For å sjekke om et tall $n$ er primtall, trenger du bare å teste om det er delelig med primtall opp til $\sqrt{n}$. For $n = 97$: $\sqrt{97} \approx 9{,}8$, så vi sjekker primtallene $2, 3, 5, 7$. Ingen av dem deler $97$, altså er $97$ et primtall.

Oppsummering

Primtall er tall større enn $1$ som bare er delelig med $1$ og seg selv. De er byggesteinene som alle andre tall er satt sammen av.

De første primtallene: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$

Delelighetsregler: