算数基本定理:
任何一个大于1的自然数 ,如果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的自然数可以以多于一种的方式写成多个质数的乘积,那么假设n是最小的一个。
首先 不是质数。将n用两种方法写出:
根据引理,质数
所以 中有一个能被 整除,即 中有一个能被 整除。不妨设为 。但 也是质数,因此 。
假设 ,则 。那麽,按照之前类似的论证, 有一个能被 整除,但 。所以不能有 ,同理,也不能有 ,因此 。
两边相除得 ,於是一个存在比 小的正整数,可以用多于一种的方式写成多个质数的乘积。
这与 的最小性矛盾。
因此唯一性得证。