算術基本定理可表述為：任何一個大於1的自然數 N,如果N不為質數，那麼N可以唯一分解成有限個質數的乘積N=P1a1P2a2P3a3......Pnan，這裡P1<P2<P3......<Pn均為質數，其中指數ai是正整數。這樣的分解稱為 N 的標準分解式。

待證命題：大於1的自然數必可寫成質數的乘積。

用反證法：假設存在大於1的自然數不能寫成質數的乘積，把最小的那個稱為n。

非零自然數可以根據其可除性（是否能表示成兩個不是自身的自然數的乘積）分成3類：質數、合數和1。首先，按照定義，n大於1。其次，n不是質數，因為質數p可以寫成質數乘積：p=p，這與假設不相符合。因此n只能是合數，但每個合數都可以分解成兩個小於自身而大於1的自然數的積。設其中a和b都是介於1和n之間的自然數，因此，按照n的定義，a和b都可以寫成質數的乘積。從而n也可以寫成質數的乘積。由此產生矛盾。因此大於1的自然數必可寫成質數的乘積。

歐幾里得引理：若質數p|ab，則p|a或p|b。

證明：若p|a則證明完畢。若否，p和a的最大公約數為1。根據裴蜀定理，存在整數對(m,n)使得ma+np=1。於是b=b(ma+np) =abm+bnp。

由於p|ab，上式右邊兩項都可以被p整除。所以p|b。

算術基本定理,又稱為正整數的唯一分解定理,即:每個大於1的自然數均可寫為質數的積,而且這些素因子按大小排列之後,寫法僅有一種方式。