Aritmetikens fundamentalsats (unika faktoriseringssatsen)
Sats inom talteorin som säger att varje heltal >1 kan skrivas som en produkt av primtal, och att denna faktorisering är unik upp till ordning. Betydelse för bevis, UFD och kryptografi.
Aritmetikens fundamentalsats är en grundläggande sats inom talteori som formulerar hur positiva heltal byggs upp av primtal. Satsen säger att varje heltal större än 1 antingen är ett primtal eller kan skrivas som en produkt av primtal – och att denna uppdelning är unik, bortsett från i vilken ordning faktorerna står. Denna enkla men djupgående princip är central i både teoretisk matematik och tillämpningar som kryptografi.
Bildgalleri
1 Bild
Vad satsen uttrycker
Satsens två delar är:
- Existens: Varje positivt heltal n > 1 kan faktoriseras som en produkt av primtal (det vill säga finns en primtalsfaktorisering). Se även faktorisering.
- Unikhet: Denna primtalsfaktorisering är unik om man bortser från ordningen hos primtalen; samma primtal och samma exponenter uppträder i alla faktoriseringar.
En standardform är att skriva faktoriseringen i kanonisk form med potenser: n = p1^a1 · p2^a2 · ... där p1 < p2 < ... är primtal och ai är positiva heltal. Exempel: 6936 = 2^3 · 3 · 17^2 och 1200 = 2^4 · 3 · 5^2. Om någon påstår en annan primtalsuppdelning kan man, efter omordning, se att faktorerna och exponenterna måste vara desamma.
Bevisidé – översikt
Beviset delas vanligen i två delar. För existensen används ofta stark induktion: varje sammansatt tal har en primfaktor, och genom att dela bort primfaktorn stegvis når man så småningom primtal. För unikheten använder man en viktig egenskap hos primtal, ofta kallad Euklides lemma: om ett primtal p delar en produkt ab så måste p dela a eller p dela b. Genom att applicera detta på två olika primfaktoriseringar visar man att primtalen i den ena faktoriseringen måste dyka upp med samma multipliciteter i den andra. Mer tekniska bevis och varianter finns i läroböcker om bevis- och talteori.
Historik och förgreningar
Satsen har sina rötter i antikens matematik men fick sin klassiska form genom Euklides’ arbete med primtal och senare formalisering i modern talteori. Euklides gav också ett känt bevis för att det finns oändligt många primtal, vilket är nära besläktat med förståelsen av primtalsfaktorisering. Begreppet generaliseras i abstrakt algebra till vad som kallas "unika faktoriseringsdomäner" (UFD), där liknande unika faktoriseringsegenskaper gäller. Dock finns det ringer där unik faktorisering bryter samman, ett klassiskt exempel är ringen Z[√−5] där talet 6 har två icke-ekvivalenta faktoriseringar: 6 = 2·3 = (1+√−5)(1−√−5).
Användningar och beräkning
Primtalsfaktorisering är inte bara teoretiskt viktig: den är praktiskt betydelsefull. Svårigheten att faktorisera mycket stora tal är grunden för flera kryptosystem, till exempel RSA, där säkerheten bygger på att även om det är lätt att multiplicera två stora primtal så är inversen — att hitta primfaktorerna ur produkten — beräkningsmässigt svår för nuvarande algoritmer. Samtidigt utvecklas effektiva algoritmer för faktorisering, såsom kvadratiska såll och generaliserade kvadratiska såll, samt kvantalgoritmer som Shors algoritm i kvantdatorteori. Läs mer om algoritmer och faktorisering i teknisk litteratur.
Viktiga punkter och vidare läsning
- Satsen är ett fundament i aritmetik och kallas ibland den "unika faktoriseringssatsen" eller "fundamentalsatsen i aritmetiken" (mer om satsen).
- Beviset bygger på grundläggande egenskaper hos primtal, särskilt Euklides lemma; formella bevis återfinns i många kursböcker (bevisöversikt).
- Faktoriseringen ger en kanonisk representation av heltal och är central för studier av delbarhet, största gemensamma delare, och multipla aritmetiska strukturer (se talteori och primtal).
För en introducerande förklaring och praktiska exempel finns populära resurser och läroböcker; för mer avancerad behandling som rör UFD och algebraiska undantag, sök vidare inom algebraisk talteori och abstrakt algebra (grundläggande heltal och begrepp).
Bevis
Den första som bevisade teoremet var Euklid. Det första detaljerade och korrekta beviset fanns i Disquisitiones Arithmeticae av Carl Friedrich Gauß.
En del människor kanske tror att satsen är sann överallt. Men satsen är inte sann i mer allmänna talsystem, som t.ex. algebraiska heltal. Detta nämndes första gången av Ernst Kummer 1843 i hans arbete om Fermats sista sats. För mer information om detta: läs algebraisk talteori.
Beviset består av två delar: för det första visar vi att varje tal kan skrivas som en produkt av primtal, för det andra visar vi att om vi skriver ett tal som en produkt av primtal för andra gången måste de två listorna med primtal vara desamma.
Första delen av beviset
Vi visar att om inte alla tal större än 1 kan skrivas som en produkt av primtal, så hamnar vi i någon form av omöjlighet. Efter det drar vi slutsatsen att det måste vara sant att alla tal kan skrivas som en produkt av primtal.
Se nu vad som händer när någon säger att han/hon känner till ett positivt heltal, större än 1, som inte kan skrivas som en produkt av primtal. I så fall ber vi honom/henne att nämna alla tal som är större än 1 och som inte kan skrivas som en produkt av primtal. Ett av dessa tal måste vara det minsta: vi kallar det n. Naturligtvis kan detta tal n inte vara 1. Dessutom kan det inte vara ett primtal, eftersom ett primtal är en "produkt" av ett enda primtal: sig självt. Det måste alltså vara en produkt av tal. Således-
n = ab
där både a och b är positiva heltal som naturligtvis är mindre än n. Men: n var det minsta tal som inte kan skrivas som en produkt av primtal. Det måste alltså vara möjligt att skriva a och b som produkter av primtal, eftersom de båda är mindre än n. Men då är produkten
n = ab
kan också skrivas som en produkt av primtal. Detta är en omöjlighet eftersom vi sade att n inte kan skrivas som en produkt av primtal.
Vi har nu visat på den omöjlighet som föreligger om den första delen av satsen inte skulle vara sann. På detta sätt har vi nu bevisat den första delen av satsen.
Andra delen av beviset
Nu måste vi bevisa att det bara finns ett sätt att skriva ett positivt tal större än 1 som en produkt av primtal.
För att göra detta använder vi följande lemma: om ett primtal p delar en produkt ab, så delar det a eller b (Euklids lemma). Först ska vi nu bevisa detta lemma. Anta nu att p inte delar a. Då är p och a lika många primtal och vi har Bezouts identitet som säger att det måste finnas heltal x och y så att
px + ay = 1.
Genom att multiplicera allt med b får man
pbx + aby = b,
Kom ihåg att ab kan delas av p. Så nu har vi på vänster sida två termer som är delbara med p. Termen på höger sida är alltså också delbar med p. Vi har nu bevisat att om p inte delar a, måste det dela b. Det bevisar lemmat.
Nu ska vi bevisa att ett heltal större än 1 bara kan skrivas på ett sätt som en produkt av primtal. Ta två produkter av primtal A och B som har samma resultat. Vi vet alltså för resultatet av produkterna att A = B. Ta ett valfritt primtal p från den första produkten A. Det delar A, så det delar också B. Genom att flera gånger använda det lemma som vi just bevisat kan vi se att p då måste dela minst en faktor b av B. Men faktorerna är alla primtal i sig själva, så även b är primtal. Men vi vet att p också är primtal, så p måste vara lika med b. Så nu delar vi A med p och delar också B med p. Och vi får ett resultat som A* = B*. Återigen kan vi ta ett primtal p från den första produkten A* och ta reda på att det är lika med något tal i produkten B*. Om vi fortsätter på detta sätt ser vi till slut att primfaktorerna i de två produkterna måste vara exakt lika. Detta bevisar att vi kan skriva ett positivt heltal som en produkt av primtal på endast ett unikt sätt.
Relaterade sidor
- Grundläggande sats i algebra
| Delbarhetsbaserade mängder av heltal | ||
| Översikt |
|
|
| Faktorsformer |
| |
| Begränsade divisorsummor |
| |
| Med många divisorer |
| |
| Aliquot sekvensrelaterad |
| |
| ||
| Andra uppsättningar |
| |
Frågor och svar
F: Vad är aritmetikens grundläggande sats?
S: Aritmetikens grundläggande sats är en sats inom talteorin som säger att varje positivt heltal större än 1 kan skrivas som en produkt av primtal, och att det bara finns ett sätt att skriva talet.
F: Hur kan denna sats användas?
S: Denna sats kan användas inom kryptografi.
F: Vad händer om två personer hittar två olika sätt att skriva samma tal?
S: Om två personer hittar två olika sätt att skriva samma tal är det enda som kan skilja sig åt den ordning i vilken primtalen skrivs.
F: Vad är faktorisering?
S: Faktorisering är att hitta alla primtal som utgör ett givet tal.
F: Är 6936 ett exempel på ett primtal?
S: Nej, 6936 är inte ett primtal, utan kan skrivas som 23 - 3 - 172.
Nej, 6936 är inte ett primtal; det kan skrivas som 23 - 3 - 172.
Relaterade artiklar
Författare
AlegsaOnline.com Aritmetikens fundamentalsats (unika faktoriseringssatsen) Leandro Alegsa
URL: https://sv.alegsaonline.com/art/37027