Aritmetikkens fundamentalteorem

I tallteori så sier aritmetikkens fundamentalteorem at ethvert naturlig tall større enn 1 kan skrives som en unik kombinasjon av primtall. For eksempel er:

$36 = 2^2 \times 3^2$

$6936 = 2^3 \times 3 \times 17^2$

Det er ingen annen måte å faktorisere disse tallene på (dette kalles primtallsfaktoriseringen av de nevnte tallene). Dette betyr at primtallene kan ses på som en type "byggesteiner" som alle de andre heltallene består av. Fordi multiplikasjon er kommutativ, spiller det ingen rolle hvilken faktor som skrives først (og som regel skriver man de fra minste til høyeste).

[rediger] Anvendelser

En kan si at det er på grunn av aritmetikkens fundamentalteorem og det at alle heltall er bygd opp av primtall at matematikere opp gjennom tidene har vært så opptatt av nettopp primtall. Dette teoremet viser hvor viktige de (primtallene) er.

Om man kjenner primtallsfaktorisingen til et gitt tall, er det lett å finne største felles nevner og minste felles multiplum. Eksempelvis er største fellesnevner til tallene over $2^2 \times 3 = 12$ . Om primtallsfaktoriseringen imidlertid ikke er kjent, er det som regel raskere å bruke Euklids algoritme for å finne største fellesnevner.

[rediger] Bevis

Vi skal vise at enhvert naturlig tall $n > 1$ på en unik måte kan skrives som produktet av primtall (om man ser bort i fra rekkefølgen faktorene skrives i). Vi beviser først at man kan skrive at vilkårlig tall på denne måten. Etterpå beviser vi at denne representasjonen er unik.

Enten er $n$ et primtall eller ikke. Hvis $n$ er et primtall så er det ikke noe mer å bevise. Om $n$ ikke er noe primtall, så finnes det et heltall $d$ som deler $n$ , hvor $1 < d < n$ . Blant alle slike $d$ , velg $p_1$ som det minste. Da må $p_1$ våre et primtall. Ellers ville også det tallet hatt en divisor $q$ hvor $1 < q < p_1$ , noe som motsier at $q_1$ er det minste tallet som deler $n$ .

Vi kan dermed skrive $n = p_1n_1$ . Hvis $n_1$ et et primtall er det ikke mer å bevise. Hvis ikke kan vi gjenta argumentasjonen og produsere et nytt primtall $p_2$ slik at $n = p_1p_2n_2$ .

Dette kan vi fortsette med lenge, men $n > n_1 > n_2 \cdots > 1$ kan ikke fortsette evig, så til slutt vil $n_{k-1}$ være et primtall vi kan kalle $p_k$ .

For å bevise at denne representasjonen er unik, anta at $n$ kan skrives som produktet av primtall på to måter, la oss si $n = p_1p_2 \cdots p_r = q_1q_2 \cdots q_s$ , der $r \leq s$ , og $p_i$ og $q_j$ er primtall skrevet i stigende rekkefølge slik at $p_1 \leq p_2 \leq \cdots \leq p_r$ og $q_1 \leq q_2 \leq \cdots \leq q_s$ .

Fordi $p_1$ deler $q_1q_2 \cdots q_s$ må $p_1 = q_k$ for en eller annen $k$ . Men da er $p_1 \geq q_1$ . Om vi argumenterer på lignende måte får vi også at $q_1 \geq p_1$ , og dermed at $p_1 = q_1$ . Om vi gjentar denne prosessen får vi at $p_2 = q_2$ , altså at $p_3p_4 \cdots p_r = q_3q_4 \cdots q_s$ . Om $r < s$ får vi at $1 = q_{r+1}q_{r+2} \cdots q_s$ , noe som er absurd, og dermed er $r = s$ , og $p_1 = q_1$ , $p_2 = q_2 \cdots p_r = q_r$ , noe som gjør de to faktoriseringene identiske. Beviset er dermed fullført.