数论初步:唯一分解定理

唯一分解定理初探

唯一分解定理，又叫算术基本定理

内容

她的内容是: 任何一个大于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$均为素数

相矛盾。

证毕。

代码

由此我们证明了唯一分解定理的正确性，为我们之前提到的做了个补充，也为我们接下来的学习做了铺垫，当然证明方法不唯一，如果有更好的证明方法欢迎指出，下面给出代码实现。

#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6 + 5;
vector<int > v[N];
void init(){
    int temp;
    for(int i = 2; i < N; i ++){
        if(v[i].size() == 0){
            for(int j = i; j < N; j += i){
                temp = j;
                while(temp % i == 0){
                    v[j].push_back(i);
                    temp /= i;
                }  
            }
        }
    }
}
int main(){
    init();
}

参考链接

Ⅰ.唯一性

Ⅱ.存在性