整数唯一分解定理及其应用
整数唯一分解定理及其应用
整数唯一分解定理，又称算术基本定理，是数论中的一个核心定理，由德国数学家高斯在其著作《算术研究》中首次提出。该定理不仅揭示了整数分解的内在规律，还为数论中的许多重要结论提供了理论基础。本文将详细介绍整数唯一分解定理及其相关应用，包括数的约数个数计算、最大公约数和最小公倍数的求解方法。
一、整数唯一分解定理
整数唯一分解定理，也称为算术基本定理，是数论中的一个重要定理。它指的是每个大于1的整数都可以唯一地表示为几个素数的乘积，而且这些素数的幂都是正整数。
$$
n = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}
$$
整数唯一分解的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)(a_2+1)\cdots (a_k+1)
$$
证明：对于$p_i^{a_i}$, 它包含的因子有：$p_i^0, p_i^1,p_i^2,\cdots ,p_i^{a_i}$共$a_i+1$个因子。那么，$n$有多少个因数呢？我们可以：
- 从$p_1$中取1个因子，有$a_i+1$种取法；
- 从$p_2$中取1个因子，有$a_2+1$种取法；
- …;
- 从$p_k$中取1个因子，有$a_k+1$种取法。
然后将他们连乘起来。
总的数目为：$F(n) = (a_1+1)(a_2+1)\cdots (a_k+1)$。
三、最大公约数和最小公倍数
给定两个数$x$和$y$，他们可以分解为相同素数的幂的乘积：
$$
x = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}
$$
$$
y = p_1^{b_1} * p_2^{b_2} * … * p_k^{b_k}
$$
例如：给定$x = 100 , y = 210$则：
$$
100 = 2^2 * 3^0 5^27^0
$$
$$
210=2^1 * 3^1 * 5^1 *7^1
$$
3.1 最大公约数
给定式（3）所示的两个数$x, y$, 它们的最大公约数为：
$$
gcd(x,y) = p_1^{min(a_1,b_1)} * p_2^{min(a_2,b_2)} * … * p_k^{min(a_k,b_k)}
$$
简单证明：
首先，$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}$。 因此$gcd(x,y)$一定能够整除$x$和$y$。
那么，为什么$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$。
所以，与假设矛盾，$gcd(x,y)$才是$x$和$y$的最大公约数。
3.2 最小公倍数
给定式（3）所示的两个数$x, y$, 它们的最小公倍数为：
$$
lcm(x,y) = p_1^{max(a_1,b_1)} * p_2^{max(a_2,b_2)} * … * p_k^{max(a_k,b_k)}
$$
证明过程与最大公约数类似。
有了最大公约数和最小公倍数的定义，我们得出一个重要的结论：
$$
xy = gcd(x,y)*lcm(x,y)
$$
因为 ：
$$
\left(p_1^{min(a_1,b_1)} * p_2^{min(a_2,b_2)} * … * p_k^{min(a_k,b_k)}\right) *\left(p_1^{max(a_1,b_1)} * p_2^{max(a_2,b_2)} * … * p_k^{max(a_k,b_k)}\right) \
= p_1^{a_1+b_1} * p_2^{a_2+b_2} * … * p_k^{a_k+b_k}=xy
$$