primtallsfaktorisering
Den Primtallfaktorisering er representasjon av en positiv naturlig tall som et produkt av primtall , som deretter som viktigste faktorene for kalles. Denne fremstillingen er tydelig (bortsett fra rekkefølgen av faktorene; det er et multisett ) og er et av tallteoriens grunnleggende og klassiske verktøy . Det er gjenstand for den grunnleggende setningen til aritmetikk . Ingen effektiv factoring-metode er hittil kjent for å oppnå primfaktorisering av et hvilket som helst tall.
Nummer | Faktorer | Nummer |
---|---|---|
1 | - | 0 |
2 | 1 | |
3 | 1 | |
4. plass | 2 | |
5 | 1 | |
Sjette | 2 | |
7. | 1 | |
8. plass | 3 | |
9 | 2 | |
10 | 2 | |
11 | 1 | |
12. plass | 3 | |
13 | 1 | |
14. | 2 | |
15. | 2 | |
16 | 4. plass | |
17. | 1 | |
18. | 3 | |
19. | 1 | |
20. | 3 |
Definisjoner
Vær et naturlig tall. Et tall kalles hovedfaktoren for ,
Primfaktorisering er representasjonen av tallet som produktet av dets primære faktorer. Siden multiplikasjon er kommutativ og assosiativ for reelle tall , er ikke rekkefølgen av primfaktorene viktig fra tallteoriens synspunkt. Den viktigste faktoriseringen av en kan sees på som et tomt produkt . Hvis det i seg selv er et primtall, er det i seg selv den eneste primfaktoren. Hvis det er mer enn en primfaktor, kalles det et sammensatt tall . Null er aldri en del av multiplikasjonsgruppen og er ekskludert fra slike betraktninger. En hovedfaktor kan forekomme flere ganger, og derfor må metoden for telling (med multipler eller hvor mange forskjellige) spesifiseres i visse sammenhenger. Flere primære faktorer kan oppsummeres på en lett lesbar måte ved hjelp av eksponenter . Hvis de forskjellige hovedfaktorene er i stigende rekkefølge ( ), snakker man også om den kanoniske primfaktoriseringen :
Eksponenten av en viktig faktor er den multiplum av i og er også referert til som den - vekting av . Det indikerer hvor ofte kan deles av . Regnet med mangfold har da hovedfaktorer.
Eksempler på prime faktorisering
- (Primtall)
- ( Kraft av to )
- , med den kanoniske representasjonen
- ( Kraft på ti )
Grunnleggende regning om regning
Uttalelsene for eksistensen av primærfaktoriseringen for hvert naturlig tall og dets unike karakter i den kanoniske representasjonen er den grunnleggende teoremet for aritmetikk , også kalt hovedsetningen til elementær tallteori . Begge uttalelsene er formulert og bevist hver for seg. Bevisene er grunnleggende, er klassisk formulert som bevis på motsigelse og bruker velordnen til de naturlige tallene. For første gang fullstendig og korrekt bevist, kan den grunnleggende setningen til aritmetikk finnes i Disquisitiones Arithmeticae av Carl Friedrich Gauß . Men det var allerede kjent for Euclid - om enn i en litt modifisert form .
Bevis for eksistens
Det er ingenting å vise for og (se delbarhet ). Hvert primtall er i seg selv dets primære faktorisering. Det gjenstår å vise at det er en primærfaktorisering for de gjenværende naturlige tallene.
Anta eksistensen av slike resttall som det ikke er noen primær faktorisering for. På grunn av velordnen av, er det da et minste slikt antall . Siden det ikke er et primtall, har det ikke- trivielle faktorer med hvor . Siden er det minste tallet som det ikke er noen primfaktorisering for, er det en primærfaktorisering for (eller ) (eller ). Da er en primær faktorisering av , i strid med antagelsen.
Bevis på unikhet
Det er ingenting å vise for , og primtall. Det gjenstår å vise at det maksimalt er en primærfaktorisering for de gjenværende naturlige tallene.
Anta eksistensen av slike gjenværende tall som flere forskjellige hovedfaktoriseringer eksisterer sammen. På grunn av velordnen av, er det da et minste slikt antall . Flere forskjellige primære faktoriseringer av sameksisterer på det meste (uten motsetning) hvis to forskjellige primære faktoriseringer og av sameksisterer. Dessuten er det ikke førsteklasses, så
Dessuten kan man anta. For hvis det var en felles faktor, for eksempel etter omsortering , ville det være . Siden minimumstallet er med to forskjellige faktorer, ville det være , og dermed ville ovennevnte faktorisering være identisk. En motsetning når det gjelder valg .
Siden produktet deler seg, ifølge Euclids lemma , deler en passende valgt faktor av dette produktet seg også. Dette kan imidlertid ikke være en hovedfaktor , ellers ville det vært . Så et produkt deler bare ut forskjellige elementer . Dette argumentet kan gjentas, det vil si distribuere et produkt av forskjellige elementer og så videre. Tross alt må et element være en del av det . Siden dette er primtall, er det det . Dette er en motsetning.
eiendommer
- og kan ikke ha hovedfaktorer til felles .
- For å beregne primfaktoriseringen av et tall, er det flere faktoriseringsmetoder tilgjengelig som beregner ikke-store delere av heltall. Denne oppgaven er kjent som et faktoriseringsproblem for hele tall og kan ikke beregnes effektivt med metodene som hittil er kjent , som sikkerhetskonsepter over hele verden er basert på, spesielt i moderne kryptografi . Se også primtallstest .
- Hardy viste flere forbløffende statistiske funn om emnet, blant annet at det gjennomsnittlige antall primære faktorer for økning bare øker veldig sakte, som f.eks. Den dobbelte naturlige logaritmen . Det sett av Erdos Kac angir dessuten at antallet av primfaktorer asymptotisk normalfordelt , med en forventet verdi og et standardavvik . (For notasjon se Landau-symboler .)
- Funksjonen som kartlegger hvert naturlig tall til antallet av de parede forskjellige hovedfaktorene, er et eksempel på en aritmetisk funksjon som er additiv, men ikke streng additiv . Det må skilles fra divisor nummer funksjon , som teller alle divisorene til et nummer, ikke bare de Primtallsdivisorer. For eksempel, er fordi det Primtallfaktorisering inneholder to ulike primtall: 2 og 5. Med den ovennevnte definisjon gjelder: .
- Det asymptotiske aritmetiske gjennomsnittet av de maksimale eksponentene for primfaktoriseringen av tallene 1, 2, 3, ... er Niven-konstanten (rundt 1,7), det asymptotiske aritmetiske gjennomsnittet av minimumseksponentene er nøyaktig 1.
- Den asymptotiske forventede verdien av det relative antall sifre til den største primfaktoren for et tall er gitt av Golomb-Dickman-konstanten .
generalisering
Det er flere måter å generalisere primtall på. Den mest kjente applikasjonen er hele tall , hvor primtall også kan ha et negativt tegn . På den annen side er dette et spesielt eksempel, siden primærfaktoriseringen også er unik der (bortsett fra tegnet og sekvensen).
En generell tilnærming krever minst ett begrep om delbarhet innenfor den matematiske strukturen. David Hilbert beviste at en additivstruktur er helt nødvendig for ønsket klarhet . Vanligvis antas en kommutativ ring med en , der primærelementer kan defineres: Et element er primær hvis Euklids lemma gjelder for det. Dette garanterer ikke at alle elementene i ringen har primtall, men hvis det er noen, er de unike. For å sikre eksistensen er en annen egenskap nødvendig: udelbarhet. For å kunne definere disse , begrenser man strukturen ytterligere og vurderer null delerfrie ringer (dvs. integritetsringer ). Irredusible elementer kan også defineres der, men de kan ikke kalles prime. De kan ikke spaltes og inneholder hovedelementene som en delmengde.
Nedbrytning til irredusible elementer i en integritetsring er ikke nødvendigvis unik. For å oppnå en struktur der produktnedbrytningen er entydig, må man eksplisitt kreve denne unikheten, noe som fører til definisjonen av faktorringer . Med dette kravet kan imidlertid ekvivalensen av irredusibel og prime allerede utledes der: Faktorringer er ZPE-ringer . En litt annen tilnærming følges med førsteklasses idealer .
Eksempler
- I integritetsringen er elementene ikke hovedelementer, men er ikke reduserbare, og ingen er assosiert med hverandre . Gjelder følgende: . Man kan altså ikke snakke om en primærfaktorisering.
- Et irreduserbart polynom kalles et primærpolynom hvis den ledende koeffisienten er den samme . I polynomringen over et legeme kan hvert ikke-konstante polynom i det vesentlige representeres unikt som et produkt av primære polynomer.
- Både de gaussiske tallene og Eisenstein-tallene har alltid en primærfaktorisering (bortsett fra 0).
Praktisk bruk
Deler
Primfaktoriseringen av to tall viser om det ene tallet kan deles av det andre. Det minst vanlige multiple ( lcm ) og den største felles divisoren ( gcd ) kan lett bestemmes ut fra primfaktoriseringen. Ved beregning av brøker kan brøk reduseres med tellerens og nevnernes GCF. Når du legger til og trekker fra, utvides to brøk til nevnerenes LCM.
Fra den kanoniske primfaktoriseringen
antall delere oppnås ved å øke eksponentene med en og deretter multiplisere dem sammen:
Kryptografi
Primtall spiller en viktig rolle i kryptografi . Krypteringssystemer som RSA er basert på at ingen effektiv faktoriseringsmetode er kjent. Dette gjør det enkelt å finne to 500-sifrede primtall og multiplisere dem i løpet av sekunder. Med dagens metoder vil imidlertid utvinning av de to viktigste faktorene fra dette 999- eller 1000-sifrede produktet ta veldig lang tid.
Gud teller
For hver oppregning av primtall uten repetisjon, er det gjennom
Definert kartlegging av alle tupler av hele tall injeksivt og kalkulerbart, den inverse funksjonen kan også beregnes gjennom primfaktorisering. Figuren er derfor egnet for å definere Godel-tall .
litteratur
- Jürgen Wolfart: Introduksjon til algebra og tallteori . Vieweg, Braunschweig / Wiesbaden 1996, ISBN 3-528-07286-5 .
weblenker
- Faktoriseringsdatabase av Markus Tervooren - rask behandling, opptil 200 000 desimaler
- Primtallsiden av Arndt Brünner - krever JavaScript , inneholder bl.a. primtallsfaktorisering
- Faktorisering ved hjelp av Elliptic Curve Method - Java-applet , behandler innganger opptil 10 000 desimaler
- Video: prime faktorisering . University of Education Heidelberg (PHHD) 2012, gjort tilgjengelig av Technical Information Library (TIB), doi : 10.5446 / 19878 .
- Video: Hovedsetningen til elementær tallteori (del 1) . University of Education Heidelberg (PHHD) 2012, gjort tilgjengelig av Technical Information Library (TIB), doi : 10.5446 / 19874 .
Individuelle bevis
- ↑ Franz Lemmermeyer: Om tallteorien til grekerne (PDF)
- ↑ Thomas Kantke: Billig og dyre numre . I: Spectrum of Science - SPESIAL: Omega . Nei. 4/2003 . Spectrum of Science, Heidelberg 2003, s. 68-74 .
- ↑ Jürgen Wolfart: Introduksjon til algebra og tallteori . Vieweg, Braunschweig / Wiesbaden 1996, ISBN 3-528-07286-5 , pp. 72, 37 .