数论初步:唯一分解定理

唯一分解定理初探

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

内容

她的内容是: 任何一个大于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();
}

参考链接

Ⅰ.唯一性

Ⅱ.存在性