primtall

Et primtall er et naturlig tall som innrømmer nøyaktig to forskjellige positive og heltalsdelere . Disse to divisorene er 1 og tallet som betraktes, siden et hvilket som helst tall har som divisors 1 og seg selv (som vist av likheten n = 1 × n ), og primtallene er de som ikke har noen annen divisor. For eksempel er heltall 7 primtall fordi 1 og 7 er det eneste heltall og positive delere av 7.

I motsetning til dette kaller vi et sammensatt tall for et hvilket som helst heltall som er produktet av to heltall som er strengt større enn 1 og derfor har minst tre deler; består for eksempel 4 = 2 × 2 som har 3 (dvs. 1, 2 og 4), 9 = 3 × 3 som har 3 (dvs. 1, 3 og 9) og 12 = 2 × 2 × 3 som har 6 (nemlig 1, 2, 3, 4, 6 og 12).

I henhold til denne definisjonen er tallene 0 og 1 derfor verken primær eller sammensatt: 1 er ikke primær fordi den bare har ett positivt heltallsdeler og 0 enten fordi det er delbart med alle positive heltall. Tidligere betraktet noen matematikere, takket være en litt annen definisjon av et primtall, 1 som et primtall . Men på begynnelsen av XX th -tallet, har en konsensus ført til definisjonen gitt her, som utelukker en primtall.

De tjuefem primtallene under 100 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 .

Slike lister med primtall som er mindre enn en gitt grense, eller inkludert mellom to grenser, kan oppnås ved forskjellige beregningsmetoder. Men det kan ikke være en endelig uttømmende liste over primtall, fordi vi vet (siden antikken : se Euklids teorem om primtall ) at det er uendelig med dem. Vi kjenner ikke til noen enkle formler for å lage slike lister ; søket etter tilnærmet formler førte til den viktige primtallsetningen .

Begrepet primtall er et grunnleggende begrep innen elementær aritmetikk : den grunnleggende setningen til aritmetikk sørger for at et sammensatt tall kan faktoriseres til et produkt av primtall, og at denne faktoriseringen er unik for rekkefølgen av faktorene. Den innrømmer viktige, men delikate generaliseringer i mer avanserte grener av matematikk, som algebraisk tallteori , som igjen tar navnet aritmetikk. Dessuten er mange industrielle anvendelser av aritmetikk basert på den algoritmiske kunnskapen om primtall, og noen ganger mer presist på vanskeligheten med de algoritmiske problemene som er knyttet til dem; Dette er tilfelle med noen kryptografiske systemer og informasjon overføringsmetoder . Primtall brukes også til å bygge hasjtabeller og til å bygge pseudo-tilfeldige tallgeneratorer .

Oppdaget den 7. desember 2018, det største kjente primtallet er Mersennes primtall 2 82 589 933 - 1, som har mer enn 24 millioner sifre i desimal skrift.

Historiske elementer

Hakkene som ble funnet på Ishangos bein datert til mer enn 20 000 år f.Kr., gravd ut av arkeolog Jean de Heinzelin de Braucourt og før utseendet til skriving (før 3200 f.Kr.). AD ), ser ut til å isolere fire grupper av verdier: 11, 13, 17 og 19. Noen arkeologer tolker det som bevis på kunnskap om primtall. Imidlertid er det for få funn til å identifisere den virkelige kunnskapen om denne eldgamle perioden.

Av leire tabletter tørket tilskrives kulturer som har lyktes i Mesopotamia under II th tusen BC. AD vise løsningen på aritmetiske problemer og vitne om tidens første kunnskap. Beregningene krevde å kjenne tabeller over inverser av heltall ( gjensidige ), hvorav noen er funnet. I det seksagesimale systemet som brukes av den babyloniske sivilisasjonen for å skrive heltall, beregnes det gjensidige av maktskillerne på 60 ( vanlige tall ) enkelt: for eksempel å dele med 24 er å multiplisere med 2 × 60 + 30 (= 150) da forskyver desimaltegnet to rader mot høyre (dvs. del med 60 2 ), siden 1/24 = 150/60 2 . Kunnskapen deres krevde god forståelse av multiplikasjon, deling. I egyptisk matematikk krevde brøkregning også kunnskap om operasjoner og inndeling av heltall. Egyptiske matematiske tekster bemerket bare visse brøker, spesielt de som for tiden tilsvarer inversen av heltall (1/2, 1/3, 1/4, 1/5,…); skrivingen av brøker ble gjort ved å legge til disse "inversene av heltall", om mulig uten repetisjon (1/2 + 1/6 i stedet for 1/3 + 1/3). Men det er ingen spor av faktorisering av heltall eller primtall i disse tekstene.

Det første ubestridelige sporet av presentasjonen av primtall dateres tilbake til antikken (rundt 300 f.Kr. ), og finnes i Elements of Euclid (bøker VII til IX ). Euclid gir en definisjon av primtall, beviset på uendelig, definisjonen av den største felles divisor (gcd) og den minst vanlige multiple (ppcm), og algoritmene for å bestemme dem, i dag kalt Euclids algoritmer. Det er mulig at kunnskapen som presenteres er tidligere.

Symbolske milepæler

Den lekne ånden og emuleringen har fått matematikere til å definere terskler for gigantisme for primtall , uttrykt som et antall ti ti sifre . Blant disse rekordene, brutt eller skal knuses, bemerker vi spesielt:

den primære titanic ( titanic premier ) over tusen tall,
de gigantiske primtallene ( gigantiske bonuser ), utover ti tusen tall,
de første megatallene ( megaprimes ) utover en million sifre.

I januar 2016, 149 viktigste megantall var kjent. Den første som ble oppdaget var i 1999 Mersenne nummer 2 6 972 593 - 1 med sine 2098 960 sifre, takket være innsatsen fra det samarbeidende distribuerte databehandlingsprosjektet Great Internet Mersenne Prime Search (GIMPS).

The Electronic Frontier Foundation tilbyr samarbeidsdata premier å oppmuntre Internett-brukere til å bidra til å løse vitenskapelige problemer gjennom distribuert databehandling. GIMPS mottok dermed 100.000 dollar for oppdagelsen i 2008 av det første primtallet på minst ti millioner desimaler. EFF tilbyr fortsatt henholdsvis $ 150.000 og $ 250.000 for oppdagelsen av det første primtallet på hundre millioner og en milliard desimaltegn.

Historie av det største kjente primtallet

Rekorden for det største kjente primtallet ble nesten alltid funnet blant Mersenne-tallene , som den siste, M 82589933 = 2 82,589,933 - 1, som et tall med 24862,048 desimaltegn.

Historie med primtall, alle kjent eller talt under en terskel

Å finne ut et primtall som er større enn alle de som allerede er kjent, innebærer ikke å kjenne alle de mellomliggende primtallene.

Mer generelt er det å finne alle primtall mindre enn et gitt tall (primtall eller ikke) en spesifikk matematisk utfordring.

Datert	Terskel $s$	Mengde $π ( s )$ (*)	Revisorer	Metode
antikken	1000	168	Eratosthenes , Euclid	Tester etter divisjon
1746	100.000	9,592	?
1797	400.000	33 860
1811	1.000.000	78.498
1863	100.000.000	5 761 455	Jakob Philipp Kulik (fra)
2010	2 76 = 75 557 863725914 320.000.000	1 462 626 667 154 509 700 000	Jens Franke et al.	Direkte vurdering av $\ ft (s)$
	2 77 = 151 115 727 451 828 650 000 000	2 886 507 381056 868 000 000
	10 24 = 1.000.000.000.000.000.000.000.000	18.435.599.767.349.200.000.000

Merknader:
(*) $π ( s )$ er den totale mengden primtall som ligger under terskelen $s$ (dvs. i intervallet av heltall ). ${\ displaystyle [\! [0, s] \!]}$ Kunnskapen om $π ( s )$ ved en algoritmisk beregning innebærer ikke nødvendigvis at hvert av primtallene er umiddelbart identifiserbare. Faktoring, tvert imot, gjør det mulig å identifisere primtall individuelt.

Begrepet primtall er knyttet til studiet av multiplikasjonsstrukturen til ringen av relative heltall. Den grunnleggende teoremet for aritmetikk, basert på Euklids Lemma , belyser denne strukturen ved å sikre at noen strengt positive heltallfaktorer til et produkt av primtall, helt ned til rekkefølgen av faktorer. Denne setningen gjør det mulig å bestemme forestillinger om gcd , ppcm og primtall mellom dem , som er nyttige for oppløsningen av visse diofantiske ligninger , spesielt karakteriseringen av pythagorasiske tripler .

Andre naturlige problemer vurderes, for eksempel å bestemme andelen primtall til et fast heltall. Innføringen av mer avanserte algebraiske strukturer gjør at dette problemet kan løses raskt innenfor rammen av modulær aritmetikk . Mange klassiske teoremer av aritmetisk art kan oppgis, slik som Fermats lille teorem , eller Wilsons teorem ; eller teoremer av mer algebraisk art som den kinesiske restsetningen .

Den kinesiske restsatsen er et første resultat i studien av endelige abeliske grupper . Det viser at strukturen til disse gruppene delvis er knyttet til nedbrytningen til produktet av hovedfaktorene til kardinalene. Ting er mer kompliserte for ikke-abelske grupper, men studien er igjen basert på hovedfaktoriseringen av kardinalene, gjennom Sylows teori .

Primtall er også involvert i topologiske strukturer . Feltet med rasjonelle tall innrømmer en vanlig topologisk struktur, som gir fullføring feltet med reelle tall . For hvert primtall p , kan en annen topologisk struktur konstrueres, fra følgende norm: hvis er et ikke-null rasjonelt tall i irreduserbar form og det er og er de største kreftene for p som deler a og b , er normen p-adic av x er . Ved å fylle det rasjonelle feltet som følger denne standarden, for å gi kroppen til tallene p-adic introdusert av Kurt Hensel tidlig på XX - tallet . Den teorem av Ostrowski sikrer at disse p-ADIC normer og vanlig standard er de eneste på banen av rasjonale tall, til likeverdighet. $x = \ frac {a} {b}$ $p ^ \ alpha$ $p ^ \ beta$ $p ^ {\ beta- \ alpha}$

Spesielle primtall

Det er bemerkelsesverdige typer primtall, definert av spesielle begrensninger. De få tilfellene nedenfor er noen av de mest kjente.

Pythagoras primtall

Noen ganger kaller vi et " Pythagoras " primtall et hvilket som helst primtall av formen 4 n + 1, der n er et naturlig tall. Primtallet 5 er for eksempel fra Pythagoras. Et odde primtall er Pythagoras hvis og bare hvis det er summen av to firkanter .

Mersennes primtall

Primtall på skjemaet: $M_p = 2 ^ p - 1$ der p da nødvendigvis også er primær, kalles Mersenne primtall . Store primtall blir ofte slått opp i denne formen fordi det er en effektiv test, Lucas-Lehmer -primalitetstesten , for å avgjøre om et slikt tall er primtall eller ikke.

Mellom 2008 og 2012, den største kjente primtall var M 43 112 609 = 2 43 112 609 - 1 som har 12,978,189 sifre i desimal skriftlig. Disse er (kronologisk) av 45 th Mersenne-primtall kjent og oppdagelsen ble kunngjort23. august 2008av GIMPS . En 46 th prime av Mersenne, 2 37 156 667 - 1 lavere enn den foregående, ble oppdaget to uker senere; de12. april 2009ble oppdaget, av samme GIMPS prosjekt, en 47 th primtall av Mersenne, 2 42 643 801 - 1 også lavere enn den første sitert.

Denne rekorden ble slått (fremdeles av GIMPS) av beviset på primaliteten til M 57 885 161 = 2 57 885 161 - 1 (i januar 2013), så igjen,7. januar 2016, ved M 74 207 281 ,3. januar 2018, av M 77 232 917 , og til slutt,7. desember 2018, etter M 82 589 933 .

Fermat primtall

Tallene på skjemaet: $F_n = 2 ^ {2 ^ n} + 1$ kalles Fermat-tallene. Fermat hadde antatt at alle disse tallene var prime. Imidlertid er de eneste kjente primære Fermat-tallene

{\ displaystyle F_ {0} = 3}

, , , Og .

{\ displaystyle F_ {1} = 5}

{\ displaystyle F_ {2} = 17}

{\ displaystyle F_ {3} = 257}

{\ displaystyle F_ {4} = 65 \, 537}

Fermat-nummeret F 5 er bare semi-prime . Den kan deles med 641.

Dette er det første moteksemplet til denne Fermat-formodningen, oppdaget av Euler i 1732. Alle de andre Fermat-tallene som er beregnet siden er sammensatt, til det punktet at målet har blitt en hektisk søken etter et annet.

Tall første tvillinger

To primtall sies å være tvillinger hvis de bare skiller seg med 2. De tre minste parene med to primtall er (3, 5), (5, 7) og (11, 13). Den største kjente er 2.996.863.034.895 × 2 21.290.000 ± 1; begge tallene har 388 342 sifre (september 2016).

Det antas at det er uendelig med tvillingprimetall.

Primtall av Sophie Germain

Et primtall G er et Sophie Germain primtall hvis 2 G + 1 også er et primtall, kalt et sikkert primtall .

De ti første primtallene til Sophie Germain er 2 , 3 , 5 , 11 , 23 , 29 , 41 , 53 , 83 , 89 .

Det antas at det er en uendelig mengde Sophie Germain.

Brasilianske primtall

Et første tall BR p er et primtall som gjenforenes med et første oddetall på 1s i en base b ; det omvendte er usant som vist med 57 = 111 7 = 3 × 19 eller igjen 121 = 11111 3 = 11 x 11.

Det minste brasilianske primtalet er 7 = 111 2 ; 43 = 111 6 og 127 = 1111111 2 er andre eksempler.

Sekvensen av brasilianske primtall begynner med 7 , 13 , 31 , 43 , 73 , 127 , 157 , 211 , 241 , 307 , 421 , 463 , etc. (fortsettelse A085104 av OEIS ).

Bare to brasilianske primtall er kjent for å være brasilianske i to forskjellige baser, dette er de to tallene i Goormaghtigh-formodningen : 31 = 11111 2 = 111 5 og 8191 = 1111111111111 2 = 111 90 .

Vi antar at det er en uendelig brasiliansk primtall, men mens serien med inverser av primtall er divergerende , konvergerer serien av inverser av brasilianske primtall mot et tall, kalt "konstant av brasilianske primtall", litt større enn 0,33 og som studeres i sekvensen A306759 .

Ethvert Mersennes primtall som er større enn eller lik 7 er per definisjon brasiliansk. For eksempel . ${\ displaystyle M_ {5} = 2 ^ {5} -1 = 31 = 11111_ {2}}$

På den annen side er ethvert primært Fermat-nummer ikke-brasiliansk. $F_n = 2 ^ {2 ^ n} + 1$

Det minste antallet par tvillinger som er brasilianske er ganske sjeldne (de vises i sekvensen A306849 ), og mer generelt er brasilianske primer relativt sjeldne; således, på de første 10 12 naturlige tallene, er det 37 607 912 018 primtall, hvorav bare 88 285 er brasilianske primtall.

Algoritmisk: beregning av primtall og primalitetstester

Eratosthenes sil og algoritme ved delingstester

De første algoritmene som bestemmer om et tall er primtall (kalt primality tests ) består i å prøve å dele det med alle tallene som ikke overskrider kvadratroten: hvis det er delbart med en av dem, er det sammensatt, og hvis ikke, det er førsteklasses. Imidlertid kan algoritmen utledet fra denne formuleringen gjøres mer effektiv: den antyder mange unødvendige divisjoner, for eksempel hvis et tall ikke er delbart med 2, er det ubrukelig å teste om det er delbart med 4. Faktisk er det det er tilstrekkelig å teste delbarheten av alle primtall som ikke overskrider kvadratroten.

Eratosthenes sil er en metode, basert på denne ideen, som gir listen over primtall mindre enn en fast verdi n ( n = 120 i animasjonen motsatt):

vi danner listen over heltall fra 2 til n ;
vi beholder det første nummeret på listen som ikke er krysset av som "primtall" (det første i dette tilfellet er 2);
vi krysser av alle heltall som er flere av tallet som ble valgt i forrige trinn, og begynner med kvadratet (siden 2 × i , 3 × i ,…, ( i - 1) × i allerede har blitt krysset av som multipler av 2, 3, ...);
vi gjentar de to siste operasjonene (det vil si: vi beholder det neste tallet som ikke er krysset av og vi krysser av dets multipler);
så snart vi leter etter multiplum av tallene som overskrider kvadratroten til n , avslutter vi algoritmen.

Dermed er primtallene mindre enn n tallene som forblir ubegrensede på slutten av prosessen. Denne algoritmen har eksponentiell algoritmisk kompleksitet .

Sikten til Eratosthenes gir derfor mer informasjon enn den eneste primiteten til n . Hvis bare denne informasjonen er ønsket, består en noen ganger mer effektiv variant i å teste delbarheten av n bare med små primtall i en liste som er fast på forhånd (for eksempel 2, 3 og 5), deretter med alle heltallene mindre enn kvadratroten til n som ikke kan deles av noen av de valgte små primtallene; dette fører til å teste delbarheten med ikke-primtall (for eksempel 49 hvis små primtall er 2, 3 og 5 og at n overstiger 2500), men et valg av et tilstrekkelig antall små primtall må gjøre det mulig å kontrollere tallet unødvendige tester utført.

Sikten til Eratosthenes: primtall mindre enn 120.

Andre algoritmer

En variant av Eratosthenes sil er Sundaram sil som innebærer å danne produkter av oddetall. Tallene som ikke nås ved denne metoden er oddetallene, det vil si alle primtallene unntatt 2. Fra sikt av Eratosthenes kan faktoriseringen av heltallet n lett finnes. Andre mer generelle metoder som takler dette problemet vanskeligere enn å bare bestemme primaliteten kalles også silmetoder, den mest effektive for tiden er den generelle tallfeltsilen .

Algoritmene presentert ovenfor er for kompliserte til å bli utført, selv med de kraftigste datamaskinene, når n blir stor.

En annen klasse algoritme består i å teste heltallet n for en familie av egenskaper som er verifisert av primtallene: Hvis en eiendom av denne familien ikke er verifisert for n , så er den sammensatt; på den annen side er det faktum at en av egenskapene til familien er verifisert for n ikke tilstrekkelig for å sikre primaliteten. Imidlertid, hvis denne familien er slik at et sammensatt tall ikke tilfredsstiller minst halvparten av egenskapene som spilles, kan brukeren anslå at et tall n som tilfredsstiller k- egenskapene til familien, er primtall med en sannsynlighet større enn $1-2 - k$ : det er erklært trolig primtall fra en verdi av k som skal velges av brukeren et tall deklarert sannsynligvis primtall, men ikke primtall, kalles et pseudo-primtall . En test basert på dette prinsippet kalles en sannsynlighetsprimalitetstest. Slike tester er ofte basert på Fermats lille setning , noe som fører til Fermats primalitetstest , og dens forbedringer: Solovay-Strassen-test og Miller-Rabin-test , som er forbedringer, fordi de innrømmer mindre pseudo-primtall.

AKS- algoritmen utviklet i 2002 gjør det mulig å bestemme (med sikkerhet) om et gitt tall N er primtall ved hjelp av en polynomberegningstid.

Formler på primtall

Mange formler er undersøkt for å generere primtall. Det høyeste nivået av krav ville være å finne en formel som til et helt tall $n$ forbinder n- primtallet. I en litt mer fleksibel måte, kan man være fornøyd med å kreve en funksjon $f$ som til et hvilket som helst heltall $n$ tilknyttede et primtall, og slik at hver verdi tas det bare tatt en gang.

Til slutt vil vi at funksjonen skal kunne beregnes i praksis (noe som ikke er tilfellet med Mills 'formel ). For eksempel sikrer Wilsons teorem at $p$ er et primtall hvis og bare hvis $( p -1)! \equiv -1 mod p$ . Det følger at funksjonen $f ( n ) = 2 + [(( n - 1)!) Mod n ] er$ verdt $n$ hvis $n$ er et primtall og ellers er verdt 2. Imidlertid er beregningen av faktoren (samme modulo ) uoverkommelig for store verdier av $n$ , og denne funksjonen har derfor liten nytte for å generere primtall. $ikke$

Det er derfor fristende å se etter polynomfunksjoner hvis verdier er primtall. Dette førte til følgende (negative) resultat: et polynom (med en eller flere variabler) hvis naturlige heltallverdier er primtall, er et konstant polynom .

Søket etter polynomer som tilfredsstiller en svakere egenskap har utviklet seg fra forestillingen om et Diophantine-sett med heltall; slike mengder kan karakteriseres som sett med strengt positive verdier tatt av et polynom (med flere variabler) hvis koeffisienter og variabler er heltall.

Et arbeid utført på 1960- og 1970-tallet, særlig av Putnam , Matiassevich , Davis og Robinson , viser at settet med primtall er Diophantine, noe som fører til eksistensen av polynomer med heltallskoeffisienter og variabler, som alle har positive verdier. er primtall. Å skrive forskjellige eksplisitte polynomer var da mulig, med forskjellig antall variabler og i varierende grad. Spesielt bestemte Jones, Sato, Wada og Wiens i 1976 et slikt polynom, av grad 25 til 26 variabler . Når det gjelder faktorformlene, er dette polynomet faktisk ubrukelig, fordi det praktisk talt bare gir negative verdier når vi varierer de 26 variablene fra 0 til $+ \ infty.$

Begrepet Diophantine-sett har mer generelt utviklet seg fra studiet og løsningen av Hilberts tiende problem med Diophantine-ligninger , og Matiassevich har vist at alle rekursivt tallrike sett er Diophantine.

Fordeling av primtall

Uendelig med primtall

Euclid demonstrerte i sine elementer (proposisjon 20 i bok IX ) at primtall er i større mengde enn noen foreslått mengde primtall . Med andre ord er det uendelig med primtall. Euclids bevis er basert på observasjonen at en endelig familie p 1 , ..., p n av primtall som blir gitt, hvilket som helst primtall som deler produktet av elementene i denne familien økt med 1, er utenfor denne familien (og en slik skiller eksisterer, noe som også er bevist av Euclid).

Andre bevis på uendelig av primtall er gitt. Eulers bevis bruker identiteten:

{\ displaystyle \ sum _ {n = 1} ^ {\ infty} \ {\ frac {1} {n}} \ = \ \ prod _ {p \ in {\ mathcal {P}}} \ {\ frac { 1} {1 - {\ frac {1} {p}}}}}

I den forrige formelen er begrepet til venstre summen av den harmoniske serien , som er divergerende. Derfor må produktet til høyre inneholde en uendelig faktor.

Furstenberg gir et bevis ved hjelp av topologisk argumentasjon .

Rarefaksjon av primtall

XVIII th århundre

Det første resultatet av oppførselen til primtall ved uendelig skyldes Euler:

Eulers rarefaksjonssetning (1737) - Serien med inverser av primtall er divergerende: ${\ displaystyle \ sum _ {p \, {\ text {first}}} {\ frac {1} {p}} \, = \, + \, \ infty.}$

Siden serien med inverser av alle heltall også er divergerende, indikerer dette intuitivt at selv om primtall blir uendelig knappe, blir de ikke knappe veldig raskt.

Videre fører resultatet på uendelig av primtall til å lure på hvor mange primtall det er opp til et gitt tall og å studere den tilsvarende funksjonen. For dette betegner vi, for ethvert primtall, sin rangering i den økende sekvensen av primtall, som indikert i følgende tabell for de 25 primtallene mindre enn 100: ${\ displaystyle p,}$

De 25 primtallene er mindre enn 100	$s$ :		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 .
Rang	${\ displaystyle \ pi (p)}$ :		1	2	3	4	5	6	7	8	9	10	11	12	1. 3	14	15	16	17	18	19	20	21	22	23	24	25

For en reell variabel, er definert som antall primtall. Denne heltallverdige reelle funksjonen kalles primtallfunksjonen . Det er en trappefunksjon, konstant mellom to etterfølgende primtall: er lik , blir den størst primtall $x$ $\ pi (x)$ ${\ displaystyle \ leq x.}$ $\ pi (x)$ $\ pi (q)$ $q$ ${\ displaystyle \ leq x.}$

Begrenset til domenet til definisjonen , er funksjonen har en invers funksjon, generelt bemerket , som representerer den n - th primtall, f.eks . ${\ mathbb P}$ $\ pi$ $p_ {n}$ ${\ displaystyle p_ {16} = 53}$

Funksjonen øker og har en tendens mot uendelig. Dette er en triviell konsekvens av uendigheten av primitallsetningen (se forrige avsnitt). $\ pi (x)$

Det første viktige resultatet på oppnås av Legendre: $\ pi (x)$

Legendres sjeldne setning - Forholdet har en tendens til null når det har en tendens til uendelig. $\ frac {\ pi (x)} {x}$ $x$

Mot slutten av XVIII th århundre , Legendre (1797) og Gauss (1792) formodning om at den prime-tellingsfunksjon er ekvivalent med funksjonen når en tendens til uendelig. Med andre ord, andelen primtall blant tallene mindre enn det vil si har en tendens til 0 med hastigheten på . $\ pi (x)$ ${\ displaystyle {\ frac {x} {\ ln (x)}}}$ $x$ ${\ displaystyle x,}$ ${\ displaystyle {\ frac {\ pi (x)} {x}},}$ ${\ displaystyle {\ frac {1} {\ ln x}}}$

Vi kan sette pris på relevansen av denne antagelsen ved å undersøke verditabellen for og for verdier som tilsvarer det første heltallets krefter på 10: $\ frac {\ pi (x)} {x}$ ${\ displaystyle {\ frac {\ pi (x)} {\ frac {x} {\ ln (x)}}}$ $x$

$m$	${\ displaystyle \ pi (m)}$	${\ displaystyle {\ frac {\ pi (m)} {m}}}$	${\ displaystyle {\ frac {\ pi (m)} {\ frac {m} {\ ln (m)}}}$
10	4	0,400	0,921
100	25	0,250	1.151
1000	168	0,168	1.161
10.000	1 229	0,123	1.132
100.000	9,592	0,096	1.104
...	...	...	...
${\ displaystyle \ rightarrow \, \ infty}$	${\ displaystyle \ rightarrow \, \ infty}$ (Euclid)	$\ høyre pil$ 0 (Legendre)	$\ høyre pil$ 1 (gjetning)

Det vil ta hele XIX th århundre at formodning er påvist (se neste avsnitt).

XIX th århundre

Et første fremskritt mot beviset på Legendre-Gauss-formodningen oppnås av Tsjebychev fra 1848:

Chebyshevs teorem - Det er to konstanter C og D slik at vi har innrammingen, for x stor nok:

{\ displaystyle \ mathrm {C} \ leq {\ frac {\ pi (x)} {\ frac {x} {\ ln x}}} \ leq \ mathrm {D},}

(Chebyshev ulikheter),

Legendre-Gauss-formodningen som består i å hevde gyldigheten av uttalelsen for enhver og enhver ${\ displaystyle \ mathrm {C} <1}$ ${\ displaystyle \ mathrm {D}> 1.}$

Den demonstrerer også følgende teorem om sjeldenhet av primtall:

Chebyshevs teorem - Si har en grense når denne grensen er 1.

{\ displaystyle {\ frac {\ pi (x)} {\ frac {x} {\ ln x}}}

{\ displaystyle x \ rightarrow \ infty,}

Som en konsekvens av ulikhetene ovenfor, kan Chebyshev også demonstrere Bertrands postulat at det i et hvilket som helst intervall av naturlige heltall, mellom et heltall og dets dobbel eksisterer minst ett primtall.

Ved å gjenoppta studien av Euler, ved hjelp av et verktøy kalt Dirichlet-tegnet , og ved å bruke i stedet for Riemann zeta-funksjonen analoge funksjoner kalt Dirichlet L-funksjonen , er Dirichlet i stand til å tilpasse beviset til primtall i aritmetiske progresjoner: hvis en og b er primære for hverandre, så er det uendelig med primtall av formen aq + b . Mer presist er primtallene jevnt fordelt mellom de forskjellige aritmetiske progresjonene av fornuft a (det vil si med en fast, og b varierer mellom de forskjellige inverterbare restene i den euklidiske divisjonen med a ).

Et nytt fremskritt skyldes Riemann i en berømt artikkel i 1859: han utvider definisjonens domene for funksjonen til det komplekse plan fratatt antallet ; han formulerer sin berømte hypotese , ifølge hvilken nollene til å være i bandet har som sin virkelige del hans tilnærming utgjør en avgjørende drivkraft for utviklingen av analytisk tallteori , kilden til mange fremskritt innen tallteori. $\ zeta (r)$ $s = 1$ ${\ displaystyle \ zeta (s)}$ ${\ displaystyle 0 \, \, <\ operatorname {Re} (s) \, <\, 1}$ ${\ displaystyle {\ frac {1} {2}} \,;}$

På slutten av århundret ble antagelsen om Legendre og Gauss demonstrert uavhengig av Jacques Hadamard og Charles-Jean de La Vallée Poussin , og har siden blitt kalt primtalsetningen . Beviset er basert på observasjonen at det er tilstrekkelig å sikre at funksjonen ikke avbrytes i halvplanet til den virkelige delen og å finne et domene som inkluderer dette halvplanet der det er tilfelle. $\ zeta$ $\ geq 1$

Primtall teorem ( Hadamard og de la Vallee Poussin , 1896) - Når ${\ displaystyle x \ rightarrow \ infty, \; \ pi (x) \ sim {\ frac {x} {\ ln x}}.}$

Demonstrasjonene bruker kraftige verktøy for kompleks analyse for å demonstrere en uttalelse om ekte regning og analyse. En strategi for disse bevisene er studiet av Riemann zeta-funksjonen på et domene av det komplekse planet som er større enn et enkelt nabolag av z = 1: det er nødvendig å kontrollere den, dvs. øke dens modul, i nærheten av den vertikale linjen av tallene av reell del lik 1. Kraften til verktøyene for kompleks analyse som brukes til å løse teoremet til primtallene fører til en viktig utvikling av en hel gren av matematikken, den analytiske teorien om tall , der studiet av Riemann zeta-funksjonen blir et sentralt tema. Spesielt vil Riemanns hypotese , fremdeles uprøvd, om lokalisering av nuller, få sterke konsekvenser for oppførselen til tellefunksjonen til primtall .

XX - tallet

Basert på Riemanns resultater (artikkel fra 1859) kan vi utlede estimatet:

Teorem (Helge von Koch, 1901) - Under Riemanns hypotese har vi: ${\ displaystyle \ pi (x) = \ operatorname {li} (x) + O (x ^ {1/2} \ ln x),}$

hvor (Riemann bemerker denne funksjonen ) og hvor betyr at det eksisterer en konstant slik at for alle store nok. ${\ displaystyle {\ rm {li}} (x) = \ int _ {0} ^ {x} {\ frac {\ mathrm {d} t} {\ ln (t)}}}$ ${\ displaystyle {\ rm {Li}} (x)}$ ${\ displaystyle f = O (g)}$ ${\ displaystyle \ mathrm {C}> 0}$ ${\ displaystyle | f (x) | \ leq \ mathrm {C} g (x)}$ $x$

Resultatene av funksjonen til å telle primtallene gjør det mulig å oppnå resultater på det niende primtallet. For eksempel, som direkte konsekvenser av Chebyshevs teoremer, etablerte Ishikawa i 1934 egenskaper for den niende primtallfunksjonen, betegnet med : $p_ {n}$

{\ displaystyle p_ {n} + p_ {n + 1}> p_ {n + 2}, \ qquad p_ {n} p_ {m}> p_ {n + m}.}

Eller ifølge et resultat av Felgner fra 1990:

{\ displaystyle 0.91 \ n \ \ ln (n) \ <\ p_ {n} \ <\ 1.7 \ n \ \ ln (n).}

Elementære bevis på primtalsetningen er funnet. Ved grunnleggende må vi forstå at de ikke bruker komplekse analyser. Dette er spesielt tilfelle med Erdős og Selberg .

Green-Tao-teorem

Den grønn-Tao teorem , demonstrert i 2004 av Ben Joseph grønne og Terence Tao , særlig generaliserer en Dirichlet-teoremet ved å sikre at for et hvilket som helst heltall k , der eksisterer en uendelighet av sekvenser av k primtall i aritmetisk progresjon, som er - det vil si om skjemaet:

{\ displaystyle a, \, a + b, \, a + 2b, \, \ dots, \, a + (k-1) b}

Green-Tao-teoremet er faktisk mye sterkere enn denne uttalelsen alene: for eksempel fastslår den at en slik aritmetisk progresjon eksisterer, med heltall som er mindre enn:

2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {100k}}}}}}

(eksperimentelt synes dette bundet å være i størrelsesorden k !). Det sørger også for at for alle heltall k og alle strengt positive reelle , for alle x tilstrekkelig store, hvis P er et sett med primtall mindre enn x som inneholder minst elementer, så inneholder P minst en aritmetisk progresjon av primtall med k- termer. $\ delta$ $\ delta \ pi (x)$

Bateman-Horn-formodning

Mange resultater og antagelser om fordelingen av primtall er inkludert i følgende generelle antagelser. La f 1 , ..., f k være ikke-konstante, irredusible polynomer som tilfredsstiller egenskapen at for ethvert primtall p er det minst ett heltall n blant 0 , ..., p - 1 slik at p ikke deler produkt av f i ( n ). Vi betegner det komplementære til p av antallet slike heltall. Et slikt sett med polynomer sies å være tillatt; vi vil vite hvor stor andel polynomene samtidig tar primverdier, og å begrense seg til sett med tillatte polynomer gjør det mulig å unngå trivielle tilfeller som f 1 ( t ) = t og f 2 ( t ) = t + 1. Det formodes da at antall heltall n mindre enn et reelt x slik at verdiene f 1 ( n ), ..., f k ( n ) samtidig er primær, er, for x stor nok, rekkefølgen på: $\ omega (p)$

{\ displaystyle \ left (\ prod _ {p} {\ frac {1 - {\ frac {\ omega (p)} {p}}} {\ left (1 - {\ frac {1} {p}} \ høyre) ^ {k}}} \ høyre) {\ frac {x} {\ log | f_ {1} (x) | \ prikker \ log | f_ {k} (x) |}}}

Den primtallet teoremet svarer til det tilfelle k = 1 og f t = t , Dirichlet teorem for k = 1 og f t = i + b , og for k = 2, f 1 ( t ) = t og f 2 ( t ) = t + 2, får vi en kvantitativ (og derfor mer generell) versjon av tvillingens primære antagelser .

applikasjoner

Den Primtallfaktorisering er nyttig for å forenkle fraksjonelle beregninger, og generelt Forenkle formler. Det er bare rimelig å bruke for små tall. De fysikalske fag har mange formler som små hele tall, enten de er koeffisienter som kommer fra utledningen eller integrering av monomials, eller de er frivillig valgt heltall koeffisienter for et program.

Primtall , og tallteori mer generelt , har lenge blitt sett på som et rent matematisk emne, med lite eller ingen applikasjoner utenfor. Dette endret seg raskt på 1970-tallet, da nye kryptografiske systemer basert på egenskapene til primtall ble utviklet.

Offentlig nøkkelkryptografi

Fram til 1970-tallet var kjente krypteringssystemer basert på prinsippet om symmetrisk kryptografi , der den samme (hemmelige) nøkkelen brukes til å kryptere og dekryptere en melding. I 1978 beskrev Ronald Rivest , Adi Shamir og Leonard Adleman det første offentlige asymmetriske kryptografisystemet (oppkalt etter initialene RSA ), basert på egenskapene til primtall og faktorisering. I et slikt system brukes to nøkler: den ene brukes til å kryptere, den andre for å dekryptere. Nøkkelen som brukes til å kryptere, er ledsaget av et stort heltall, produktet av to store primer som holdes hemmelige (i størrelsesorden 200 sifre). For å beregne dekrypteringsnøkkelen krever den eneste kjente metoden å kjenne til de to viktigste faktorene. Sikkerheten til systemet er basert på det faktum at det er lett å finne to store primtall (ved hjelp av primalitytester) og å multiplisere dem mellom dem, men at det ville være vanskelig for en angriper å finne disse to tallene. Dette systemet tillater også opprettelse av digitale signaturer, og har revolusjonert kryptografiens verden.

Generaliseringer av primtall

Begrepet primtall ble sett generalisert i løpet av XIX E århundre i andre algebraiske strukturer enn ringen av relative heltall. For å løse aritmetiske problemer som teoremet om to firkanter , satsen for fire firkanter eller loven om kvadratisk gjensidighet (det første beviset på grunn av Carl Friedrich Gauss i hans Disquisitiones arithmeticae ), har matematikere blitt ledet til å utføre resonnementer på delbarhet som er analog med de som antyder heltallene i andre ringer, for eksempel det av heltallene til Gauss eller det heltallene til Eisenstein .

Det moderne synspunktet finner sin kilde i arbeidet til Ernst Kummer , som introduserer forestillingen om "ideelt primtall", i sitt forsøk på å bevise Fermats store setning . Denne forestillingen er opprinnelsen til den moderne teorien om ringer av algebraiske heltall, avledet fra arbeidet til Dedekind og Kronecker: i moderne termer sies det at disse ringene har en struktur av Dedekind-ringer ; Spesielt blir setningen om faktorisering av primtall erstattet av et resultat av faktorisering av ringens idealer (det vil si de absorberende undergruppene for multiplikasjonen, som i denne sammenheng er relatert til dette som Kummer kalte "ideelle tall ") som et produkt av hovedidealer. Aritmetikken i disse ringene har generelt dype og vanskelige koblinger med aritmetikken til klassiske primtall: For eksempel klarer Kummer i sitt arbeid med Fermats teorem å demonstrere umuligheten av å finne ikke-trivielle løsninger (dvs. 'dvs. med x , y og z ikke null) til ligningen x p + y p = z p hvis p er et vanlig primtall (dette er en tilstand som relaterer seg til arten av ringen av algebraiske heltall generert av en primitiv rot p- enhetens enhet).

På den eneste basis av noen få statistiske eksperimenter har noen antagelser om primtall blitt overført til heldige tall (konstruert av en variant av silen til Eratosthenes ).

Antagelser og åpne spørsmål

Det er mye gjetning og åpne spørsmål om primtall. For eksempel :

Landaus fire problemer :
- Goldbachs antagelse : ethvert partall som er strengt større enn 2 kan skrives som summen av to primtall;
- formodning om tvillingprimetall : det er en uendelig primetvilling
- Legendarisk antagelse : det eksisterer alltid minst ett primtall mellom n 2 og ( n + 1) 2 ; denne antagelsen er knyttet til Riemann-hypotesen og, som den siste, forblir uprøvd til i dag;
- eksistensen av en uendelig primtall av formen n 2 + 1.
Eksistensen av en uendelig hovedtall av Sophie Germain .
Den formodning av Polignac (også i forhold til tvillingprimtall er det spesielle tilfellet n = 2): naturlig jevnt, helt tall n kan skrives som forskjellen mellom to påfølgende primtall, og at et uendelig antall måter.
Schinzel 's hypotesen H : den omfatter formodning av to primtall og Landau' fjerde problem; den sier at hvis vi har en endelig familie av polynomer med heltallskoeffisienter, så eksisterer det uendelig med heltall n slik at alle polynomer i familien gir primtall når vi vurderer dem i n (forutsatt at det ikke er noen åpenbar hindring for for å være tilfelle: for eksempel hvis et av polynomene er n ( n + 1) eller 2 n , er dette tydeligvis ikke mulig).
Den Bateman-Horn formodningen : spesifiserer den Schinzel hypotesen ved å gi en tilnærmet verdi av antallet n < x med denne egenskap.
Er det en uendelig mengde Fermat eller Mersenne eller Fibonacci primtall ?
Er det en uendelighet av faktorielle eller primorial primtall ?
En antagelse av Daniel Shanks : la sekvensen, kjent som Euclid-Mullin , med første sikt u 1 = 2 og slik at begrepet u n er den minste hoveddeleren til etterfølgeren til produktet av begrepene u i for i <n . Antagelsen sier at alle primtall vises i denne sekvensen.
Den Ulam spiral (eller Ulam klokke) er ennå ikke fullt ut forklart.

Merknader og referanser

(in) Chris Caldwell Yeng Xiong, " What Is The Smallest premium?] " , Journal of Integer Sequences , Vol. 15, n o 9,2012( les online ).
Se Marcus du Sautoy , The Symphony of Prime Numbers , s. 42 .
Olivier Keller, “ Prehistory of geometry: the problem of sources ” .
Paul Benoit ( dir. ), Karine Chemla ( dir. ) Og Jim Ritter ( dir. ), Histoire des fractions, fractions d'histoire , Bâle, Birkhäuser,1992.
Kawai Han bemerket også i sin avhandling (i) at til tross for langt overlegne tekniske ferdigheter, ser det ikke ut til at primtallene (eller andre steder koniske ) har blitt sett i Kina før det XVII - tallet , da vestlige misjonærer gjorde dem kjent.
(in) Chris Caldwell, The Largest Known Primes at The Prime Pages .
(no) GIMPS pressemelding, GIMPS finner First Digit Million-Prime .
(in) Chris Caldwell, The Largest Known Prime by Year: A Brief History at The Prime Pages. Del 1: Før elektroniske datamaskiner, del 2: Elektroniske datamaskiners alder.
(no) EFF Cooperative Computing Awards .
villemin.gerard.free.fr Primtall : Historie.
Østerriksk matematiker ( 1793 - 1863 ): (In) John J. O'Connor og Edmund F. Robertson , "Jakob Philipp Kulik" i MacTutor History of Mathematics archive , University of St. Andrews ( les online ).
(en) primes.utm.edu Betinget beregning av pi (10 ^ 24).
Naudin et Quitté 1992 , begynnelsen på kapittel 3.
Gouvêa 1997 .
Han skrev således til Bernard Frénicle de Bessy : “ Men her er det jeg beundrer mest: det er at jeg nesten er overbevist om at alle de progressive tallene økte med enhet, hvor eksponentene er tall for den doble progresjonen, er primtall , slik som 3, 5, 17, 257, 65537, 4 294 967 297 og de neste 20 bokstavene 18 446 744 073 709 551 617; etc. Jeg har ikke den eksakte demonstrasjonen av det, men jeg har ekskludert et så stort antall skillelinjer ved ufeilbarlige demonstrasjoner, og jeg har så store innsikter som etablerer min tanke at jeg ville ha problemer med å trekke meg tilbake . » , Brev XLIII, av? August 1640, i Œuvres de Fermat , vol. 2, Paris, Gauthier-Villars ,1894( les online ) , s. 206.
B. Schott, " De brasilianske Numbers ", Quadrature , vol. 76,2010, Tilgjengelig i lenken etter A125134 i OEIS .
Cohen 1993 , begynnelsen på kapittel 8, spesielt algoritme 8.1.1.
Cohen 1993 , kapittel 10, spesielt avsnitt 5.
Naudin og Quitté 1992 , kap. 4, seksjon 6.
Cohen 1993 , kap. 8, avsnitt 2.
Ribenboim 1996 , innføring i kapittel 3.
Ribenboim 1996 , kap. 3, avsnitt II.
Ribenboim 1996 , kap. 3, avsnitt III.
Hardy og Wright 2007 , avsnitt 2.1.
(Ia) Leonh. Euler, “Variae observationes circa series infinitas”, Commentarii academiae scientiarum Petropolitanae , vol. 9, 1744, s. 160-188 eller Opera Omnia , serie 1, vol. 14, s. 217-244 . Nedlastbar på [1] . Identitet er teorem 7, s. 172 og uendelig av primtall blir implisitt tilbakekalt og analysert i de følgende resultatene.
Ribenboim 1996 .
Som en tendens til uendelig illustrerer følgende ulikheter hastigheten på knapphet: $x$ ${\ displaystyle {\ begin {alignat} {5} \ sum _ {n \, {\ text {integer}}} ^ {\ leq x} {\ frac {1} {n ^ {1+ \ varepsilon}}} \ qquad & <& \ sum _ {p \, {\ text {først}}} ^ {\ leq x} {\ frac {1} {p}} \ quad & <& \ sum _ {n \, {\ tekst {int}}} ^ {\ leq x} {\ frac {1} {n}}. \ quad \\\ overbrace {\ qquad \ qquad \ qquad \ qquad \ qquad} && \ overbrace {\ qquad \ qquad \ qquad} && \ overbrace {\ qquad \ qquad \ qquad} \\ {\ text {konvergerende til}} \, \ zeta (1+ \ varepsilon) && {\ text {divergent}} && {\ text {divergent}} \ \ = {\ frac {1} {\ varepsilon}} \, + \, \ gamma + o (1) && \ sim \ ln \ ln x && \ sim \ ln x \ end {alignat}}}$
Serien til venstre er konvergent, mens summen gjelder alle heltall og (positiv) kan velges så lite som vi vil, mens serien i midten, ifølge Eulers teorem, er divergerende og har en tendens til uendelig, mens summen gjelder bare primtall. $\ varepsilon$
Ribenboim 1996 , kap. 4, avsnitt I.
Hardy og Wright 2007 , kap. 22, avsnitt 1 til 4.
Hardy og Wright 2007 , setning 15.
Ellison og Mendes Frankrike 1975 , kap. 7.
Ellison og Mendes Frankrike 1975 , kap. 2, avsnitt 1.2.
Ellison og Mendes Frankrike 1975 , kap. 2, setning 2.4, deretter avsnitt 4.
Ribenboim 1996 , kap. 4, avsnitt II, A.
Nicolas Bourbaki , Elementer i matematikkens historie , kapittel Kommutativ algebra. Teori om algebraiske tall.
(in) David Wells, Prime Numbers: The Most Mysterious Figures in Math , John Wiley & Sons ,2011, s. 147–148.

Nevnte verk

[Cohen 1993] (no) Henri Cohen , A Course in Computational Algebraic Number Theory ,1993[ detalj av utgaver ] - Moderne referanse om effektive metoder i tallteori.
[Ellison og Mendès Frankrike 1975] William John Ellison og Michel Mendès Frankrike , Les Nombres Premiers ,1975[ detalj av utgaven ] - Veldig tydelig bok, som en introduksjon til analytisk tallteori.
[Gouvêa 1997] (en) Fernando Q. Gouvêa , P-adic Numbers: An Introduction ,1997[ detalj av utgaven ] - Introduksjon til p-adic tall innenfor rekkevidden til et stort publikum, orientert mot analytiske mål.
[Hardy and Wright 2007] GH Hardy og EM Wright ( oversatt fra engelsk av François Sauvageot, pref. Catherine Goldstein ), Introduksjon til tallteorien [" En introduksjon til teorien om tall "] [ detalj av utgaven ] - En flott klassiker av introduksjon til tallteori, som dekker grunnleggende emner (kongruenser), introduserer algebraiske metoder ved eksempel (Gaussiske og Kronecker-heltall), og gir et bevis på primtallsetningen.
[Naudin og Quitté 1992] Patrice Naudin og Claude Quitté , algebraisk algoritmikk ,1992[ detalj av utgaven ]
[Ribenboim 1996] (no) Paulo Ribenboim , The New Book of Prime Number Records , Springer,1996, 3 e ed. ( les online )

Se også

Relaterte artikler

Bibliografi

Pierre Colmez , Elementer av analyse og algebra (og tallteori) , Éditions de l'École Polytechnique,2009
Jean-Paul Delahaye , Fantastiske primtall: Reisen til hjertet av regningen ,2000[ detalj av utgaven ]
Michel Demazure , algebra-kurs. Primality, delbarhet, koder , Cassini,1997. - Denne boka inneholder mange algoritmer skrevet i Caml Light .
Michel Demazure, Kurs i algebra. Primality, delbarhet, koder , Cassini,2008. - Utvidet versjon (spesielt på korrigerende koder ) av den første utgaven, de fleste algoritmene er blitt omskrevet i Ruby .
Flere verk med samme tittel, men veldig forskjellig innhold, har dukket opp i Que sais-je? :
- Émile Borel , The Prime Numbers , PUF , koll. "Hva vet jeg? "( N o 571),1953 ;
- Jean Itard , The Prime Numbers , PUF , koll. "Hva vet jeg? "( N o 571),1969.
- Gérald Tenenbaum og Michel Mendès France , Les Nombres Premiers , PUF , koll. " Hva vet jeg? "( N o 571),2000( 1 st ed. 1997), 127 s. ( ISBN 2-13-048399-2 ).
- Gérald Tenenbaum og Michel Mendès Frankrike, The Prime Numbers, mellom orden og kaos , Paris, Dunod ,2014, 2 nd ed. , 170 s. ( ISBN 978-2-10-070656-3 )- Utvidet og oppdatert versjon av den forrige, med for eksempel referanser til Green-Tao-teoremet , eller til resultatene av Zhang Yitang .

Eksterne linker

Pierre Colmez , primtall
(in) Andrew Granville Page
(no) Primtallene : suite A000040 fra OEIS
En stor liste med primtall (opptil 1.000.000.000)
" Primtall " , på www.math93.com
Primality test