Primtall
Fra Wikipedia, den frie encyklopedi
Et primtall er et naturlig tall større enn 1 som ikke kan deles på annet enn 1 og seg selv uten å etterlate en rest. De første 30 primtallene (følge A000040 i OEIS) 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, 97, 101, 103, 107, 109 og 113.
Et naturlig tall større enn 1 som ikke er et primtall, kalles et sammensatt- eller kompositt tall.
Primtall er et fundamentalt begrep innen tallteori. Ethvert positivt heltall større enn 1, kan skrives som et produkt av primtallsfaktorer på en entydig måte, såkalt primtallsfaktorisering. For eksempel er 60 = 2 × 2 × 3 × 5. Dette er kjent som aritmetikkens fundamentalteorem.
Euklid beviste at det finnes uendelig mange primtall. Beviset er et av de mest klassiske innen matematikken, og bruker bevismetoden reductio ad absurdum: Anta at det finnes et endelig antall primtall. La N være produktet av alle primtallene, og betrakt tallet N+1. Siden alle primtallene deler N, kan det ikke finnes noe primtall som N+1 er delelig med. Men siden N+1, ifølge antagelsen, er større enn alle primtall, kan det ikke selv være et primtall. Dette er en motsigelse. Konklusjonen må være at antagelsen vi gikk ut fra, nemlig at det bare finnes et endelig antall primtall, er gal. Altså finnes det et uendelig antall primtall.
Det største kjente primtallet er 232 582 657-1 og har 9 808 358 siffer. Det blir kalt «M32582657» fordi det er et såkalt Mersenne-primtall, disse følger mønsteret 2n-1. Electronic Frontier Foundation har lovt ut en premie på 100 000 $ til den første som finner et primtall med mer enn ti millioner siffer.
