Aritmetikkens fundamentalsætning

I matematikken, og særligt i talteori, siger aritmetikkens fundamentalsætning at ethvert positivt heltal større end 1 enten er et primtal eller kan opskrives som et produkt af primtal. Desuden er denne opskrivning unik, når man ser bort fra rækkefølgen. F.eks. kan man skrive

6936 = 2³ · 3 · 17²   eller   1200 = 2⁴ · 3 · 5²

og der findes ingen andre mulige faktoriseringer af 6936 eller 1200.

Man kan udvide sætningen til at gælde tallet 1, hvis man betragter 1 som produktet af nul primtal.

Sætningen kan nemt og elegant bevises. Beviset kunne for eksempel gå som følger:

Del I: Alle ikke-primtal kan opløses i en primfaktoropløsning

Antag det modsatte; at der findes et tal, som ikke kan opløses i primfaktorer. Vi kigger på det laveste af denne slags, og kalder dette tal n. Alle tal mindre end n kan opløses i primtal. Altså kan tallet n ikke have nogle divisorer, da disse ville kunne omskrives til primfaktorer. Men hvis det ikke har nogen divisorer, udover 1 og den selv, så er tallet n selv et primtal. Hermed er det vist, at alle tal enten er primtal eller sammensatte tal, som kan opløses i primfaktorer.

Del II: Primtalsfaktorisation er entydig

Vi antager at der findes et tal N hvorom der gælder at der findes 2 primtalsopløsninger af tallet:

$N=m_{1}m_{2}...m_{i}=n_{1}n_{2}...n_{j}$

Vi fjerner først alle fælles faktorer på begge sider. Nu tager vi så faktoren $n_{1}$ og dividerer med den på alle tre sider. Nu er siden med m-faktorerne ikke et heltal, mens at siden med n-faktorerne er. Derfor må vores udgangspunkt om den flertydige opløsning af N være fejlfuldt.