- Kjennetegn på primtall
- Hvordan vite om et tall er primtall
- Måter å finne et primtall på
- Eulers formel
- Silen til Eratosthenes
- Øvelser
- - Oppgave 1
- Løsning
- - Oppgave 2
- Løsning på
- Løsning b
- referanser
De primtall , også kalt prime absolutte, er de naturlige tall som bare er delelig med seg selv og 1. Denne kategorien tall som 2, 3, 5, 7, 11, 13, 17, 19, 23 og mange i tillegg til.
I stedet kan et sammensatt tall deles av seg selv, med 1 og minst ett annet tall. Vi har for eksempel 12, som kan deles med 1, 2, 4, 6 og 12. I henhold til konvensjonen er 1 ikke inkludert i listen over primtall eller i listen over forbindelser.
Figur 1. Noen primtall. Kilde: Wikimedia Commons.
Kunnskap om primtall stammer fra eldgamle tider; de gamle egypterne brukte dem allerede, og de var sikkert kjent lenge før.
Disse tallene er veldig viktige, siden et hvilket som helst naturlig tall kan være representert med produktet av primtall, og denne representasjonen er unik, bortsett fra i størrelsesorden for faktorene.
Dette faktum er fullt etablert i et teorem som kalles det grunnleggende teoremet om aritmetikk, som sier at tall som ikke er primære, nødvendigvis består av produkter med tall som er.
Kjennetegn på primtall
Her er de viktigste egenskapene til primtall:
-De er uendelige, siden uansett hvor stort primtall er, kan du alltid finne et større nummer.
-Hvis et primtall p ikke nøyaktig deler et annet tall a, så sies det at p og a er primetall for hverandre. Når dette skjer, er den eneste fellesdeleren som begge har 1.
Det er ikke nødvendig for a å være en absolutt fyrste. For eksempel er 5 primer, og selv om 12 ikke er det, er begge tallene primære for hverandre, siden begge har 1 som en felles divisor.
-Når et primtall p deler en kraft på tallet n, deler det også n. La oss vurdere 100, som er en kraft på 10, nærmere bestemt 10 2 . Det hender at 2 deler både 100 og 10.
-Alle primtall er rare, bortsett fra for 2, derfor er det siste sifferet 1, 3, 7 eller 9. 5 er ikke inkludert, for selv om det er merkelig og primt, er det aldri det endelige tallet på et annet primtall. Faktisk er alle tallene som ender på 5 multiplum av dette, og derfor er de ikke primære.
-Hvis p er en prim og deler av produktet av to tall ab, deler p deretter ett av dem. For eksempel deler primtallet 3 produktet 9 x 11 = 99, siden 3 er en divisor på 9.
Hvordan vite om et tall er primtall
Primality er navnet som gis til kvaliteten på å være prime. Vel, den franske matematikeren Pierre de Fermat (1601-1665) fant en måte å verifisere primaliteten til et tall i den såkalte lille Fermat-teoremet, som lyder slik:
"Gitt et naturlig naturlig tall p og et hvilket som helst naturlig tall større enn 0, er det sant at en p - a er et multiplum av p, så lenge p er primetall".
Vi kan bekrefte dette ved hjelp av små tall, for eksempel anta at p = 4, som vi allerede vet ikke er førsteklasses og allerede = 6:
6 4 - 6 = 1296 - 6 = 1290
Tallet 1290 er ikke helt delbart med 4, derfor er ikke 4 et primtall.
La oss gjøre testen nå med p = 5, som er førsteklasses og ya = 6:
6 5 - 6 = 7766 - 6 = 7760
7760 kan deles med 5, siden et hvilket som helst nummer som ender på 0 eller 5 er. Faktisk 7760/5 = 1554. Siden Fermats lille teorem inneholder, kan vi sikre at 5 er et primtall.
Beviset gjennom teoremet er effektivt og direkte med små tall, der operasjonen er enkel å utføre, men hva skal jeg gjøre hvis vi blir bedt om å finne ut om det store antallet er?
I så fall er tallet suksessivt delt mellom alle de mindre primtallene, inntil en nøyaktig inndeling er funnet eller kvotienten er mindre enn deleren.
Hvis noen deling er nøyaktig, betyr det at tallet er sammensatt, og hvis kvotienten er mindre enn deleren, betyr det at tallet er primtall. Vi vil implementere det i løst oppgave 2.
Måter å finne et primtall på
Det er uendelig mange primtall, og det er ingen formel for å bestemme dem. Men ser på noen primtall som disse:
3, 7, 31, 127 …
Det blir observert at de er av formen 2 n - 1, med n = 2, 3, 5, 7, 9 … Vi sørger for dette:
2 2 - 1 = 4 - 1 = 3 ; 2 3 - 1 = 8 - 1 = 7 ; 2 5 - 1 = 32 - 1 = 31 ; 2 7 - 1 = 128 - 1 = 127
Men vi kan ikke sikre at 2 n - 1 generelt er førsteklasses, fordi det er noen verdier av n som det ikke fungerer for, for eksempel 4:
2 4 - 1 = 16 - 1 = 15
Og tallet 15 er ikke primært, siden det ender på 5. Imidlertid er en av de største kjente primene, funnet ved datamaskinberegninger, av formen 2 n - 1 med:
n = 57,885,161
Mersennes formel forsikrer oss om at 2 p - 1 alltid er prime, så lenge p er prime også. For eksempel er 31 prim, så det er sikkert at 2 31 - 1 også er prim :
2 31 - 1 = 2 147 473 647
Imidlertid lar formelen deg bestemme bare noen primtall, ikke alle.
Eulers formel
Følgende polynom tillater å finne primtall forutsatt at n er mellom 0 og 39:
P (n) = n 2 + n + 41
Senere i delen med løste øvelser er det et eksempel på bruken.
Silen til Eratosthenes
Eratosthenes var en fysiker og matematiker fra antikkens Hellas som levde i det 3. århundre f.Kr. Han utarbeidet en grafisk metode for å finne primtallene som vi kan utføre med små tall, det kalles Eratosthenes-sil (en sil er som en sil).
-Tallene er plassert i en tabell som den som er vist i animasjonen.
-Detallene blir deretter krysset ut, bortsett fra 2 som vi vet er primære. Alle de andre er flere av dette og er derfor ikke førsteklasses.
-Multiplene på 3, 5, 7 og 11 er også merket, ekskluderer dem alle fordi vi vet at de er førsteklasses.
-Multiplene på 4, 6, 8, 9 og 10 er allerede merket, fordi de er sammensatte og derfor multiplum av noen av de angitte primene.
-Endelig er tallene som forblir umerkede primære.
Figur 2. Animasjon av Eratosthenes-silen. Kilde: Wikimedia Commons.
Øvelser
- Oppgave 1
Ved å bruke Euler-polynomet for primtall, finn 3 tall større enn 100.
Løsning
Dette er polynomet som Euler foreslo å finne primtall, som fungerer for verdier på n mellom 0 og 39.
P (n) = n 2 + n + 41
Ved prøving og feiling velger vi en verdi av n, for eksempel n = 8:
P (8) = 8 2 + 8 + 41 = 113
Siden n = 8 produserer et primtall større enn 100, vurderer vi polynomet for n = 9 og n = 10:
P (9) = 9 2 + 9 + 41 = 131
P (10) = 10 2 + 10 + 41 = 151
- Oppgave 2
Finn ut om følgende tall er primære:
a) 13
b) 191
Løsning på
De 13 er små nok til å bruke Fermats lille teorem og hjelp av kalkulatoren.
Vi bruker a = 2 slik at tallene ikke er for store, selv om a = 3, 4 eller 5 også kan brukes:
2 13 - 2 = 8190
8190 kan deles med 2, siden den er jevn, derfor er 13 førsteklasses. Leseren kan bekrefte dette ved å gjøre den samme testen med a = 3.
Løsning b
191 er for stor til å bevise med teoremet og en felles kalkulator, men vi kan finne skillet mellom hvert primtall. Vi unnlater å dele med 2 fordi 191 ikke er engang og inndelingen ikke vil være nøyaktig eller kvotienten mindre enn 2.
Vi prøver å dele med 3:
191/3 = 63,666 …
Og det gir ikke nøyaktig, og kvotienten er heller ikke mindre enn deleren (63 666 … er større enn 3)
Vi fortsetter dermed og prøver å dele 191 mellom primene 5, 7, 11, 13, og verken den nøyaktige inndelingen er nådd, eller kvotienten mindre enn divisoren. Inntil det er delt med 17:
191/17 = 11, 2352 …
Siden det ikke er nøyaktig og 11.2352 … er mindre enn 17, er tallet 191 et primtall.
referanser
- Baldor, A. 1986. Aritmetikk. Utgaver og distribusjoner Codex.
- Prieto, C. Primtallene. Gjenopprettet fra: paginas.matem.unam.mx.
- Egenskaper for primtall. Gjenopprettet fra: mae.ufl.edu.
- Smartick. Primtall: hvordan finne dem med Eratosthenes sil. Gjenopprettet fra: smartick.es.
- Wikipedia. Primtall. Gjenopprettet fra: es.wikipedia.org.