数论 | 算术基本定理

算术基本定理（唯一分解定理）：任何一个大于 $1$ 的自然数 $N$，如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积 $N=P_1^{a_1}{P}_2^{a_2}{P}_3^{a_3}\cdots P_n^{a_n}$，$P_1<P_2<P_3<\cdots <P_n$ 且均为质数，$a_1,a_2,a_3,\cdots ,a_n$ 均为正整数。

定理推论

• 一个大于 $1$ 的整数 $N$，如果它的标准分解式为 $N=P_1^{a_1}{P}_2^{a_2}{P}_3^{a_3}\cdots P_n^{a_n}$，那么它的正因数个数为 ${\sigma }_0(N)=(1+a_1)(1+a_2)\cdots (1+a_n)$

简单证明：

$P_1^{b_1}{P}_2^{b_2}{P}_3^{b_3}\cdots P_n^{b_n}(0\le b_1\le a_1,0\le b_2\le a_2,\cdots )$ 一定是 $N$ 的正因数。其中 $b_1$ 可选 $[0,a_1]$ 共 $1+a_1$ 种，$b_2$ 可选 $[0,a_2]$ 共 $1+a_2$ 种 $\cdots \cdots$

根据乘法原理，整体选法总数为：$(1+a_1)(1+a_2)\cdots (1+a_n)$。每一种选法对应一个正因数，则选法数量就是正因数的个数。

• 它的全体正因数之和为 ${\sigma }_1(N)=(P_1^0+P_1^1+P_1^2+\cdots +P_1^{a_1})(P_2^0+P_2^1+P_2^2+\cdots +P_2^{a_2})\cdots (P_n^0+P_n^1+P_n^2+\cdots +P_n^{a_n})$

简单证明：

我们将 $(P_1^0+P_1^1+P_1^2+\cdots +P_1^{a_1})(P_2^0+P_2^1+P_2^2+\cdots +P_2^{a_2})\cdots (P_n^0+P_n^1+P_n^2+\cdots +P_n^{a_n})$ 使用分配律展开，会得到一个多项式。

多项式中每个单项式的结构均为 $P_1^{b_1}{P}_2^{b_2}{P}_3^{b_3}\cdots P_n^{b_n}(0\le b_1\le a_1,0\le b_2\le a_2,\cdots )$，即 $N$ 的一个正因数。多项式的值便是所有正因数的和。

常见题型

求正因数个数

需要先用到欧拉筛生成质数，然后用质数从小到大分解 $N$ 得到 $a_1,a_2,a_3,\cdots ,a_n$，然后计算出正因数个数 ${\sigma }_0(N)=(1+a_1)(1+a_2)\cdots (1+a_n)$

bool is_prime[SIZE];
int prime[SIZE], primesize = 0;
// 欧拉筛生成质数代码省略
int fact_cnt(int n)
{
    int now = n, ans = 1;
    for (int i = 0; i < primesize && prime[i] <= sqrt(now); i++)
    {
        int cnt = 0;
        while (now % prime[i] == 0)
        {
            cnt++;
            now /= prime[i];
        }
        ans *= (cnt + 1);
    }
    if (now != 1)
        ans *= 1 + 1;
    return ans;
}

判断正因数之和奇偶性

需要以下结论：

• 奇数个奇数相加为奇数，偶数个奇数相加为偶数
• 奇数乘奇数为奇数，奇数乘偶数为偶数，偶数乘偶数为偶数
• 除了 $2$，质数均为奇数。因此除了 $2$，质数的任意次幂都是奇数。

假设 ${\sigma }_1(N)=(1+P_1+P_1^2+\cdots +P_1^{a_1})(1+P_2+P_2^2+\cdots +P_2^{a_2})\cdots (1+P_n+P_n^2+\cdots +P_n^{a_n})$ 为奇数，那么：

情况 1：若 $2\mid N$，那么 $P_1=2$，所以 $P_1+P_1^2+\cdots +P_1^{a_1}$ 为偶数，$1+P_1+P_1^2+\cdots +P_1^{a_1}$ 为奇数。

如果 ${\sigma }_1(N)$ 为奇数，那么 $(1+P_2+P_2^2+\cdots +P_2^{a_2}),\cdots ,(1+P_n+P_n^2+\cdots +P_n^{a_n})$ 均为奇数

即 $(P_2+P_2^2+\cdots +P_2^{a_2}),\cdots ,(P_n+P_n^2+\cdots +P_n^{a_n})$ 均为偶数

因为 $P_2,\cdots ,P_n$ 均为质数，由结论可知，一定是偶数个奇数相加，即 $a_2,\cdots ,a_n$ 均为偶数

情况 1.1：若 $a_1$ 为偶数，$N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=(P_1^{a_1/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2}{)}^2$ 为完全平方数 $x^2$

情况 1.2：若 $a_1$ 为奇数， $N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=P_1\times (P_1^{(a_1-1)/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2}{)}^2$ 为完全平方数的两倍 $2\cdot x^2$

情况 2：若 $2\nmid N$，同上得 $(P_1+P_1^2+\cdots +P_1^{a_2}),\cdots ,(P_n+P_n^2+\cdots +P_n^{a_n})$ 均为偶数

所以 $N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=(P_1^{a_1/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2}{)}^2$ 为完全平方数 $x^2$

综上所述：若 $N=x^2\mathrm{或}2\cdot x^2$，${\sigma }_1(N)$ 为奇数，反之为偶数。

代码实现非常简单，略去。