Primtal

Eit primtal er eit heiltal som er større enn 1 og som ikkje er deleleg med andre naturlege tal enn 1 og seg sjølv. Primtala som er mindre enn hundre er:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 og 97.

Eit naturleg tal som er større enn 1, og som ikkje er eit primtall, kallast eit samansett tal.

Kvart naturleg tal kan skrivast som eit produkt av primtal på ein eintydig måte (viss me ser bort frå permutasjonar av primtalsfaktorane). Dette vert kalla aritmetikkens fundamentalsats.

Euklid viste omkring år 300 før vår tidsrekning at det finst uendeleg mange primtal. Provet er som følgjer. Anta at det berre finst eit endeleg antal primtal og kall dette talet for $n$. Kall primtala for $p_{1},\ldots ,p_{n}$ og sjå på talet $x=p_{1}p_{2}..p_{n}+1$. Det er klart at ingen av primtala $p_{1},\ldots ,p_{n}$ deler $x$. Altså er $x$ eit anna primtal. Men dette er ein sjølvmotseiing og det me gjekk ut frå—at det berre er eit endeleg tal primtal—kan ikkje vera sant. Derfor må det vera eit uendeleg tal primtal.

Sjå òg

• Liste over primtal