Aritmetikens fundamentalsats

Från Wikipedia
Hoppa till: navigering, sök

Aritmetikens fundamentalsats är ett teorem inom den gren av matematiken som kallas talteori. Om ett positivt heltal som är större än 1, helt delas upp i primtalsfaktorer är denna uppdelning unik:

Varje heltal 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 en uppdelning.

Exempel på tal helt uppdelade i primtalsfaktorer:

12   = 2^2 \cdot 3
120 = 2^3 \cdot 3\cdot 5
98   = 2 \cdot 7^2

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 p är ett primtal som delar en produkt av heltal, a_1 \, a_2 \, \cdots \, a_n, så delar primtalet p minst en av faktorerna a_1, \, a_2, \, \dots, a_n

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

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

vilket efter multiplikation med b övergår till

\ xpb + yab = b

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

4 Om primtalet p delar det positiva heltalet  a_{1}\, är vi klara; annars måste p dela produkten av positiva heltal
a_{2}a_{3} \cdots a_{n}

Proceduren kan upprepas och för något i måste primtalet p dela ett av de positiva heltalen a_{i} 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:
p_1\,p_2 \, \cdots \, p_s \, \,= \, q_1 \, q_2 \, \cdots \, q_t = \,n
3 Vissa av primtalen p kan vara identiska med vissa av primtalen q. Om dessa primtal divideras bort erhålls
p_{i_1} \, p_{i_2} \, \cdots \, p_{i_u} = q_{j_1} \, q_{j_2} \, \cdots \, q_{j_v} = m

där ingen faktor  p_{i_r} är lika med någon faktor  q_{j_s}.

4 Om vi tillämpar hjälpsatsen på primtalet p_{i_1} och produkten q_{j_1} \, q_{j_2} \, \cdots \, q_{j_v}, så måste primtalet p_{i_1}, eftersom det delar \ m, dela något av primtalen q_{j_k}.

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]

Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.