Aritmetikens fundamentalsats

Wikipedia

Aritmetikens fundamentalsats är ett teorem inom talteori som säger att varje positivt heltal kan skrivas som en produkt av primtal på precis ett sätt.

Med "på precis ett sätt" menas att det finns endast en uppsättning primtal som multiplicerade med varandra ger det givna heltalet, men faktorernas ordningsföljd i produkten bortser man ifrån eftersom ordningsföljden inte påverkar resultatet. Att satsen gäller är inget som man kan se direkt på ett uppenbart sätt. Exempelvis är talet 16709 en produkt av primtalen 7, 7, 11 och 31. Man skulle mycket väl kunna tro att det finns en annan uppsättning primtal som multiplicerade med varandra gav 16709, om man inte kände till satsen.

[redigera] Bevis för existensen av en primtalsfaktorisering

Vi ska, genom reductio ad absurdum, visa att varje heltal större än ett kan skrivas som en produkt av primtal.

Antag att det finns ett sådant tal som inte kan skrivas som en produkt av primtal och kalla det minsta för $n$ . Försök att dividera $n$ med alla talen från $2$ till $n - 1$ . Om det inte går att dividera $n$ med något av dem utan att få en rest, så är $n$ per definition ett primtal, och därför en produkt av ett primtal. Om det däremot finns ett $k$ som delar $n$ , så är $n = k m$ där både $k$ och $m$ är heltal som kan skrivas som en produkt av primtal eftersom de är mindre än $n$ . Men då är också $n$ en produkt av primtal vilket motsäger vårt antagande att det finns ett heltal större än ett som inte kan skrivas som en produkt av primtal. Alltså kan varje heltal större än ett skrivas som en produkt av primtal.

[redigera] Bevis för primtalsfaktoriseringens entydighet

Antag att det finns två olika primtalsfaktoriseringar av ett tal $a$ . Kalla dessa primtalsfaktoriseringar $p_1, \ldots ,p_n$ respektive $q_1, \ldots ,q_m$ :

$a = p_1 p_2 \ldots p_n = q_1 q_2 \ldots q_m$

Eftersom $p 1$ delar vänsterledet, så måste det också dela högerledet, det vill säga $p 1$ måste dela något av $q_1 \ldots q_m$ . Alltså måste $p 1$ vara lika med något av $q_1 \ldots q_m$ . Upprepas detta för $p_2 \ldots p_n$ får vi att de två faktoriseringarna är lika så när som på ordningen.