- Karakteristika for primtal
- Hvordan man ved, om et tal er primt
- Måder at finde et primtal
- Eulers formel
- Sigten fra Eratosthenes
- Øvelser
- - Øvelse 1
- Løsning
- - Øvelse 2
- Løsning på
- Løsning b
- Referencer
De primtal, også kaldet prime absolutte, er de naturlige tal, som kun kan deles i sig selv og 1. Denne kategori tal som 2, 3, 5, 7, 11, 13, 17, 19, 23 og mange plus.
I stedet kan et sammensat tal deles af sig selv, med 1 og mindst et andet tal. Vi har for eksempel 12, som kan deles med 1, 2, 4, 6 og 12. I konvention er 1 ikke inkluderet på listen over primtal eller på listen over forbindelser.
Figur 1. Nogle primtal. Kilde: Wikimedia Commons.
Kendskab til primtallene går tilbage til gamle tider; de gamle egyptere brugte dem allerede, og de var helt sikkert kendt længe før.
Disse tal er meget vigtige, da ethvert naturligt tal kan repræsenteres af produktet fra primtal, idet denne repræsentation er unik, undtagen i rækkefølge af faktorer.
Denne kendsgerning er fuldt ud etableret i et teorem kaldet Fundamental Theorem of Arithmetic, der siger, at tal, der ikke er primære, nødvendigvis består af produkter med antal, der er.
Karakteristika for primtal
Her er de vigtigste egenskaber ved primtal:
-De er uendelige, da uanset hvor stort et primtal er, kan du altid finde et større nummer.
-Hvis et primtal p ikke nøjagtigt deler et andet tal a, siges det, at p og a er primære til hinanden. Når dette sker, er den eneste fælles divisor, som begge har, 1.
Det er ikke nødvendigt for a at være en absolut prime. For eksempel er 5 prim, og selvom 12 ikke er det, er begge tal primære for hinanden, da begge har 1 som en fælles divisor.
-Når et primtal p deler en magt på tallet n, deler det også n. Lad os overveje 100, som er en magt på 10, nærmere bestemt 10 2. Det sker, at 2 deler både 100 og 10.
-Alle primtall er ulige undtagen for 2, derfor er det sidste ciffer 1, 3, 7 eller 9. 5 er ikke inkluderet, fordi selvom det er ulige og prim, er det aldrig det endelige tal for et andet primtal. Faktisk er alle numrene, der ender på 5, multipla af dette, og derfor er de ikke primære.
-Hvis p er en prim og divisor af produktet med to tal ab, deler p derefter et af dem. For eksempel deler primtallet 3 produktet 9 x 11 = 99, da 3 er en divisor på 9.
Hvordan man ved, om et tal er primt
Primality er det navn, der gives til kvaliteten af at være prime. Nå, den franske matematiker Pierre de Fermat (1601-1665) fandt en måde at verificere primaliteten af et tal i den såkaldte lille Fermat-sætning, der siger:
"Givet et naturligt primært tal p og ethvert naturligt tal større end 0, er det rigtigt, at en p - a er et multiplum af p, så længe p er prim".
Vi kan bekræfte dette ved hjælp af små tal, for eksempel antage, at p = 4, som vi allerede ved, ikke er prime og allerede = 6:
6 4 - 6 = 1296 - 6 = 1290
Tallet 1290 er ikke nøjagtigt delbart med 4, derfor er 4 ikke et primtal.
Lad os udføre testen nu med p = 5, som er prime og ya = 6:
6 5 - 6 = 7766 - 6 = 7760
7760 kan deles med 5, da ethvert tal, der ender på 0 eller 5, er. Faktisk 7760/5 = 1554. Da Fermats lille sætning indeholder, kan vi sikre, at 5 er et primtal.
Beviset gennem teoremet er effektivt og direkte med et lille antal, hvor operationen er let at udføre, men hvad skal man gøre, hvis vi bliver bedt om at finde ud af, om et stort tal er prioriteret?
I dette tilfælde er antallet successivt delt mellem alle de mindre primtal, indtil der findes en nøjagtig opdeling eller kvotienten er mindre end divisoren.
Hvis nogen opdeling er nøjagtig, betyder det, at antallet er sammensat, og hvis kvotienten er mindre end divisoren, betyder det, at antallet er prim. Vi vil omsætte det i løst øvelse 2.
Måder at finde et primtal
Der er uendeligt mange primtal, og der er ingen enkelt formel til at bestemme dem. Ser man dog på nogle primtall som disse:
3, 7, 31, 127…
Det bemærkes, at de er af 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 primære, fordi der er nogle værdier af n, som det ikke fungerer, for eksempel 4:
2 4 - 1 = 16 - 1 = 15
Og tallet 15 er ikke primært, da det slutter i 5. En af de største kendte primater, fundet ved computerberegninger, er imidlertid af formen 2 n - 1 med:
n = 57,885,161
Mersennes formel forsikrer os om, at 2 p - 1 altid er prime, så længe p også er prime. For eksempel er 31 prim, så det er sikkert, at 2 31 - 1 også er prim:
2 31 - 1 = 2.147.483.647
Formlen giver dig dog mulighed for kun at bestemme nogle primtal, ikke alle.
Eulers formel
Følgende polynom giver mulighed for at finde primtal, forudsat at n er mellem 0 og 39:
P (n) = n 2 + n + 41
Senere i afsnittet med løste øvelser er der et eksempel på brugen.
Sigten fra Eratosthenes
Eratosthenes var en fysiker og matematiker fra det antikke Grækenland, der levede i det 3. århundrede f.Kr. Han udtænkte en grafisk metode til at finde de primtal, som vi kan udføre i praksis med små numre, det kaldes Eratosthenes-sigten (en sigte er som en sigte).
-Tallene er placeret i en tabel som den, der er vist i animationen.
-Det lige antal er derefter krydset ud, bortset fra 2, som vi ved er primære. Alle de andre er multipla af dette og er derfor ikke førsteklasses.
-Multiplerne på 3, 5, 7 og 11 er også markeret, eksklusive dem alle, fordi vi ved, at de er de bedste.
-Multiplerne på 4, 6, 8, 9 og 10 er allerede markeret, fordi de er sammensatte og derfor multipla af nogle af de angivne primater.
- Endelig er de tal, der forbliver umærkede, primære.
Figur 2. Animation af Eratosthenes-sigten. Kilde: Wikimedia Commons.
Øvelser
- Øvelse 1
Brug Euler-polynomet til primtal, find 3 numre større end 100.
Løsning
Dette er det polynomium, som Euler foreslog at finde primtal, der fungerer for værdier på n mellem 0 og 39.
P (n) = n 2 + n + 41
Ved prøve og fejl vælger vi en værdi af n, for eksempel n = 8:
P (8) = 8 2 + 8 + 41 = 113
Da n = 8 producerer et primtal større end 100, vurderer vi polynomet for n = 9 og n = 10:
P (9) = 9 2 + 9 + 41 = 131
P (10) = 10 2 + 10 + 41 = 151
- Øvelse 2
Find ud af, om følgende tal er primære:
a) 13
b) 191
Løsning på
De 13 er små nok til at bruge Fermats lille sætning og hjælp af lommeregneren.
Vi bruger a = 2, så tallene ikke er for store, selvom a = 3, 4 eller 5 også kan bruges:
2 13 - 2 = 8190
8190 kan deles med 2, da den er jævn, derfor er 13 førsteklasses. Læseren kan bekræfte dette ved at udføre den samme test med a = 3.
Løsning b
191 er for stor til at bevise med teoremet og en fælles lommeregner, men vi kan finde opdelingen mellem hvert primtal. Vi udelader dividering med 2, fordi 191 ikke er engang, og opdelingen vil ikke være nøjagtig eller kvoten mindre end 2.
Vi forsøger at dele med 3:
191/3 = 63.666…
Og det giver ikke nøjagtigt, og kvotienten er heller ikke mindre end divisoren (63.666… er større end 3)
Vi forsøger således at dele 191 mellem primerne 5, 7, 11, 13, og hverken den nøjagtige opdeling er nået eller kvoten mindre end divisoren. Indtil det er divideret med 17:
191/17 = 11, 2352…
Da det ikke er nøjagtigt, og 11.2352… er mindre end 17, er antallet 191 en prim.
Referencer
- Baldor, A. 1986. Aritmetik. Editions and Distribution Codex.
- Prieto, C. Primtallene. Gendannes fra: paginas.matem.unam.mx.
- Egenskaber ved primtal. Gendannes fra: mae.ufl.edu.
- Smartick. Primtal: hvordan man finder dem med Eratosthenes-sigten. Gendannes fra: smartick.es.
- Wikipedia. Primtal. Gendannet fra: es.wikipedia.org.