整数唯一分解定理

整数唯一分解定理，也称为算术基本定理，是由德国数学家高斯在其著作《算术研究》中首次提出的。本文回顾整数唯一分解定理以及对应的几个重要结论。

一、整数唯一分解定理

整数唯一分解定理，也称为算术基本定理，是数论中的一个重要定理。它指的是每个大于1的整数都可以唯一地表示为几个素数的乘积，而且这些素数的幂都是正整数。
$$n=p_1^{a_1}\ast p_2^{a_2}\ast \dots \ast p_k^{a_k}\text{\hspace{1em}(1)}$$

整数唯一分解的C++代码如下：

void IntDecompose(int n) {
	map<int,int> maps;  		//存储质数以及对应的幂
	int i = 2, e = 0;
	while (n != 1) {
		if (n % i == 0) {
			n /= i;
			maps[i]++;
		}
		else i++;
	}

	auto it = maps.begin();		//输出n对应的分解结果
	cout << n << "=" << it->first << "^" << it->second;
	for (++it; it != maps.end(); ++it)
		cout << " * " << it->first << "^" << it->second;
}

二、数的约数个数

根据整数唯一分解定理，可以得到一个结论：$n$ 的正约数的个数为：
$$F(n)=(a_1+1)\ast (a_2+1)\ast \cdots (a_k+1)\text{\hspace{1em}(2)}$$
证明：对于 $p_i^{a_i}$, 它包含的因子有：$p_i^0,p_i^1,p_i^2,\cdots ,p_i^{a_i}$ 共 $a_i+1$个因子。同时，还可以进行组合，具体而言，可以
从 $p_1$中取1个因子，有 $a_i+1$种取法；
从 $p_2$中取1个因子，有 $a_2+1$种取法；
…;
从 $p_k$中取1个因子，有 $a_k+1$种取法。
然后将他们连乘起来。
总的数目为：$F(n)=(a_1+1)\ast (a_2+1)\ast \cdots (a_k+1)$。

三、最大公约数和最小公倍数

给定两个数 $x$ 和 $y$，他们可以分解为相同素数的幂的乘积：
$$x=p_1^{a_1}\ast p_2^{a_2}\ast \dots \ast p_k^{a_k}$$$$y=p_1^{b_1}\ast p_2^{b_2}\ast \dots \ast p_k^{b_k}\text{\hspace{1em}(3)}$$
例如：给定 $x=100,y=210$ 则：
$$100=2^2\ast 3^0\ast 5^2\ast 7^0$$$$210=2^1\ast 3^1\ast 5^1\ast 7^1$$

3.1 最大公约数

给定式（3）所示的两个数 $x,y$, 它们的最大公约数为：
$$\text{gcd}(x,y)=p_1^{min(a_1,b_1)}\ast p_2^{min(a_2,b_2)}\ast \dots \ast p_k^{min(a_k,b_k)}\text{\hspace{1em}(4)}$$
简单证明：
首先， $\text{gcd}(x,y)$ 一定能整除 $x$ 和 $y$。因为这里所有素数的幂都是取的较小者，即 $p_i$ 的幂为 $min(a_i,b_i)$, 所以 $p_i^{min(a_i,b_i)}|p_i^{a_i}$ 且 $p_i^{min(a_i,b_i)}|p_i^{b_i}$。 因此 $\text{gcd}(x,y)$ 一定能够整除 $x$ 和 $y$ 。

那么，为什么 $\text{gcd}(x,y)$ 是 $x$ 和 $y$ 的最大公约数呢？这里使用反证法。
假设 $g$ 才是 $x$ 和 $y$ 的最大公约数。
那么，必然存在 $g$ 包含的某个素数 $p_i$ 的指数 $c_i>min(a_i,b_i)$。
但是，此时$p_i^{c_i}$ 要么不能整除 $p_i^{a_i}$， 要么不能整除 $p_i^{b_i}$。
因此， $g$ 不能同时整除 $x$ 和 $y$。
所以，与假设矛盾，$\text{gcd}(x,y)$ 才是 $x$ 和 $y$ 的最大公约数。

3.2 最小公倍数

给定式（3）所示的两个数 $x,y$, 它们的最小公倍数为：
$$\text{lcm}(x,y)=p_1^{max(a_1,b_1)}\ast p_2^{max(a_2,b_2)}\ast \dots \ast p_k^{max(a_k,b_k)}\text{\hspace{1em}(5)}$$
证明过程与最大公约数类似。

有了最大公约数和最小公倍数的定义，我们得出一个重要的结论：
$$xy=\text{gcd}(x,y)\ast \text{lcm}(x,y)\text{\hspace{1em}(4)}$$
因为 ：
$\left(p_1^{min(a_1,b_1)}\ast p_2^{min(a_2,b_2)}\ast \dots \ast p_k^{min(a_k,b_k)}\right)\ast \left(p_1^{max(a_1,b_1)}\ast p_2^{max(a_2,b_2)}\ast \dots \ast p_k^{max(a_k,b_k)}\right)=p_1^{a_1+b_1}\ast p_2^{a_2+b_2}\ast \dots \ast p_k^{a_k+b_k}=xy$