Aritmetikens fundamentalsats

Från Wikipedia

Aritmetikens fundamentalsats är ett teorem inom den gren av matematiken som kallas talteori. Om ett naturligt tal, som är större än 1, till fullo delas upp i primtalsfaktorer, så är denna uppdelning unik:

Varje naturligt tal större än 1 kan skrivas som en produkt av primtal på ett och endast ett sätt.

Uppdelningar som endast skiljer sig åt med avseende på primtalsfaktorernas ordning är ekvivalenta och räknas som identiska.

Exempel på tal helt uppdelade i primtalsfaktorer:

Bevis av existensen av primtalsfaktorisering[redigera | redigera wikitext]

Låt A vara mängden av alla positiva heltal som kan skrivas som en produkt av primtal.

Vi skall visa att mängden A innehåller alla positiva heltal genom att använda ett motsägelsebevis (Latin: reductio ad absurdum).

1 Antag att A inte är mängden av alla positiva heltal
2 Det finns då positiva heltal som inte tillhör A. Låt alla sådana tal tillhöra en mängd B.
3 Enligt välordningsaxiomet för de positiva heltalen gäller att
Varje icke-tom mängd av positiva heltal innehåller ett minsta element

Därför innehåller B ett minsta element som vi betecknar m.

4 Inget element i B är ett primtal då varje primtal b i B skulle ha primtalsuppdelningen b = b och således inte tillhöra B.
5 m, genom att tillhöra B, inte är ett primtal kan det skrivas som en produkt av två positiva heltal p och q som båda är mindre än m.
6 Om p är ett element i B är detta en motsägelse då p är mindre än det minsta elementet m i B.

Om p inte är ett element i B är det ett element i A. Eftersom varje element i A kan skrivas som en produkt av primtal kan p skrivas som en produkt av primtal.

7 Steg 6 kan upprepas för q vilket leder till att både p och q kan skrivas som produkter av primtal. Då är även m en produkt av primtal då m = pq.

Men detta är en motsägelse eftersom m, genom att tillhöra B, inte kan skrivas som en produkt av primtal.

8 Det var således fel att anta att A inte var mängden av alla positiva heltal. Det är därmed visat att varje positivt heltal kan skrivas som en produkt av primtal.

Q.E.D.

Bevis av primtalsfaktoriseringens entydighet[redigera | redigera wikitext]

Vi skall visa att varje positivt heltal kan uppdelas i en produkt av primtal på endast ett sätt. Primtalsuppdelningar som endast skiljer sig med avseende på primtalsfaktorernas ordning räknas som en uppdelning. Satsen bevisas med ett motsägelsebevis.

Hjälpsats[redigera | redigera wikitext]

Om är ett primtal som delar en produkt av heltal, , så delar primtalet minst en av faktorerna

Hjälpsatsen bevisas först för en produkt av två positiva heltal, och i steg 1 till 3.

1 Låt primtalet dela produkten
2 Antag att inte delar det positiva heltalet ; vi skall visa att kommer att dela det positiva heltalet .
3 Om inte delar talet så måste deras största gemensamma delare vara talet . Enligt Bezouts identitet går det då att finna heltal och sådana att

vilket efter multiplikation med b övergår till

Primtalet delar båda termerna i vänsterledet och därför delar också (högerledet).

4 Om primtalet delar det positiva heltalet är vi klara; annars måste dela produkten av positiva heltal

Proceduren kan upprepas och för något i måste primtalet dela ett av de positiva heltalen enligt ovan.

Q.E.D.

Bevis[redigera | redigera wikitext]

1 Antag att det finns positiva heltal som kan framställas som en produkt av primtal på mer än ett sätt.
2 Låt n vara ett sådant positivt heltal och anta två framställningar av heltalet n som en produkt av primtal:
3 Vissa av primtalen p kan vara identiska med vissa av primtalen q. Om dessa primtal divideras bort erhålls

där ingen faktor är lika med någon faktor .

4 Om vi tillämpar hjälpsatsen på primtalet och produkten så måste primtalet , eftersom det delar , dela något av primtalen .

Men detta är omöjligt och således var det fel att anta att det fanns positiva heltal som kunde framställas som en produkt av primtal på mer än ett sätt.

Q.E.D.

Se även[redigera | redigera wikitext]

Externa länkar[redigera | redigera wikitext]