唯一分解定理初探
唯一分解定理,又叫算术基本定理
内容
她的内容是: 任何一个大于1的自然数N,如果N不为素数,那么,N就能被唯一的分解为有限个素数的乘积。
公式
$N=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times … \times p_n^{a_n}$,其中$p_1 < p_2 < p_3 < … < p_n$,且$p_i$为素数,$a_i$为正整数。
唯一分解定理证明
从唯一分解定理的内容中可以看出,其中值得证明的地方有两处,一处是,是否所有数都能被分解为素数的乘积,即存在性,第二处是,分解是否唯一,即唯一性。下面我们逐条证明。
存在性
此处使用反正法证明,假设n为不能被分解为质数乘积的自然数中的最小的一个。
因为如果n为素数,那么n显然只能被分解为n,所以假设n为大于1的合数。
既然n为合数,那么一定存在两个数a,b,且$1 < a, b < n$,所以得到 $n=a\times b$。
下面对于a和b进行分析,显然当两个数都为素数的时候矛盾已经出现了,所以下面来讨论一下为合数的情况
如果a,b中有一个为合数,假设是a,那么由于n已经是最小的不能被分解为素数乘积的合数了,那么显然a是可以被分解为素数乘积的(因为如果不能被分解,那么N为最小的不能被分解的合数这个条件就出现了矛盾)。那么矛盾就出现了。同理当两个数都为合数的时候会得到相同的矛盾。
证毕
唯一性
有存在性作为基础,那么唯一性也就值得被证明了,这里我采用相同的方法来证明。假设n为最小的不能被唯一分解为一系列素数乘积的合数,那么我们不妨设n能被分解为一下两形式
Ⅰ.$n=q_1\times q_2\times … \times q_n$
Ⅱ.$n=t_1\times t_2\times …\times t_n$
其中$q_i$和$t_i$均为素数,且都已经按升序排列好了,显然$q_i\neq t_i$,因为如果相等,那么两式联立时会被约掉,那样的话我们能得到一个更小的素数组合。所以$q1\neq t1$,那么不妨设$q_1 < t_1$,然后我们用$q_1$去替换Ⅱ中的$t_1$,从而得到一个比n更小的数m。
于是我们设$X=n-m$,那么她应该会有以下两种形式:
Ⅲ.$X=q_1\times (q_2\times … \times q_n-t_1\times t_2\times …\times t_n)$
Ⅳ.$X=(t_1-q_1)\times (t_1\times t_2\times …\times t_n)$
由于X比n要小,由假设得,X是能被唯一分解为一系列素数的乘积的。由Ⅲ得,$q_1$为X的一个质因子,由于X的分解具有唯一性,那么$q_1$要么包含于$q_1-t_1$中,要么包含于$t_1\times t_2\times …\times t_n$中,下面我们来分别讨论
①.当$q_1$包含于$t_1\times t_2\times …\times t_n$中时,显然于假设中
显然$q_i\neq t_i$,因为如果相等,那么两式联立时会被约掉,那样的话我们能得到一个更小的素数组合。
相矛盾。
②当$q_1$包含于$q_1-t_1$中,那么我们将得到一个这样的等式$\frac {t_1-q_1}{q1}$为整数,也就是${\frac {t_1}{q_1}}-1$为整数,那么也就意味着$\frac {t_1}{q_1}$为整数,这与假设中的
其中$q_i$和$t_i$均为素数
相矛盾。
证毕。
代码
由此我们证明了唯一分解定理的正确性,为我们之前提到的做了个补充,也为我们接下来的学习做了铺垫,当然证明方法不唯一,如果有更好的证明方法欢迎指出,下面给出代码实现。
1 |
|