整数唯一分解定理,也称为算术基本定理,是由德国数学家高斯在其著作《算术研究》中首次提出的。本文回顾整数唯一分解定理以及对应的几个重要结论。
一、整数唯一分解定理
整数唯一分解定理,也称为算术基本定理,是数论中的一个重要定理。它指的是每个大于1的整数都可以唯一地表示为几个素数的乘积,而且这些素数的幂都是正整数。
n = p 1 a 1 ∗ p 2 a 2 ∗ … ∗ p k a k (1) n = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}\tag1 n=p1a1∗p2a2∗…∗pkak(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 n n 的正约数的个数为:
F ( n ) = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ ⋯ ( a k + 1 ) (2) F(n) = (a_1+1)*(a_2+1)*\cdots (a_k+1)\tag2 F(n)=(a1+1)∗(a2+1)∗⋯(ak+1)(2)
证明:对于 p i a i p_i^{a_i} piai, 它包含的因子有: p i 0 , p i 1 , p i 2 , ⋯ , p i a i p_i^0, p_i^1,p_i^2,\cdots ,p_i^{a_i} pi0,pi1,pi2,⋯,piai 共 a i + 1 a_i+1 ai+1个因子。同时,还可以进行组合,具体而言,可以
从 p 1 p_1 p1中取1个因子,有 a i + 1 a_i+1 ai+1种取法;
从 p 2 p_2 p2中取1个因子,有 a 2 + 1 a_2+1 a2+1种取法;
…;
从 p k p_k pk中取1个因子,有 a k + 1 a_k+1 ak+1种取法。
然后将他们连乘起来。
总的数目为: F ( n ) = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ ⋯ ( a k + 1 ) F(n) = (a_1+1)*(a_2+1)*\cdots (a_k+1) F(n)=(a1+1)∗(a2+1)∗⋯(ak+1)。
三、最大公约数和最小公倍数
给定两个数 x x x 和 y y y,他们可以分解为相同素数的幂的乘积:
x = p 1 a 1 ∗ p 2 a 2 ∗ … ∗ p k a k x = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k} x=p1a1∗p2a2∗…∗pkak y = p 1 b 1 ∗ p 2 b 2 ∗ … ∗ p k b k (3) y = p_1^{b_1} * p_2^{b_2} * … * p_k^{b_k} \tag3 y=p1b1∗p2b2∗…∗pkbk(3)
例如:给定 x = 100 , y = 210 x = 100, y = 210 x=100,y=210 则:
100 = 2 2 ∗ 3 0 ∗ 5 2 ∗ 7 0 100 = 2^2 * 3^0 *5^2*7^0 100=22∗30∗52∗70 210 = 2 1 ∗ 3 1 ∗ 5 1 ∗ 7 1 210=2^1 * 3^1 * 5^1 *7^1 210=21∗31∗51∗71
3.1 最大公约数
给定式(3)所示的两个数 x , y x,y x,y, 它们的最大公约数为:
gcd ( x , y ) = p 1 m i n ( a 1 , b 1 ) ∗ p 2 m i n ( a 2 , b 2 ) ∗ … ∗ p k m i n ( a k , b k ) (4) \text{gcd}(x,y) = p_1^{min(a_1,b_1)} * p_2^{min(a_2,b_2)} * … * p_k^{min(a_k,b_k)} \tag4 gcd(x,y)=p1min(a1,b1)∗p2min(a2,b2)∗…∗pkmin(ak,bk)(4)
简单证明:
首先, gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 一定能整除 x x x 和 y y y。因为这里所有素数的幂都是取的较小者,即 p i p_i pi 的幂为 m i n ( a i , b i ) min(a_i,b_i) min(ai,bi), 所以 p i m i n ( a i , b i ) ∣ p i a i p_i^{min(a_i,b_i)} | p_i^{a_i} pimin(ai,bi)∣piai 且 p i m i n ( a i , b i ) ∣ p i b i p_i^{min(a_i,b_i)} | p_i^{b_i} pimin(ai,bi)∣pibi。 因此 gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 一定能够整除 x x x 和 y y y 。
那么,为什么 gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 是 x x x 和 y y y 的最大公约数呢?这里使用反证法。
假设 g g g 才是 x x x 和 y y y 的最大公约数。
那么,必然存在 g g g 包含的某个素数 p i p_i pi 的指数 c i > m i n ( a i , b i ) c_i > min(a_i,b_i) ci>min(ai,bi)。
但是,此时 p i c i p_i^{c_i} pici 要么不能整除 p i a i p_i^{a_i} piai, 要么不能整除 p i b i p_i^{b_i} pibi。
因此, g g g 不能同时整除 x x x 和 y y y。
所以,与假设矛盾, gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 才是 x x x 和 y y y 的最大公约数。
3.2 最小公倍数
给定式(3)所示的两个数 x , y x,y x,y, 它们的最小公倍数为:
lcm ( x , y ) = p 1 m a x ( a 1 , b 1 ) ∗ p 2 m a x ( a 2 , b 2 ) ∗ … ∗ p k m a x ( a k , b k ) (5) \text{lcm}(x,y) = p_1^{max(a_1,b_1)} * p_2^{max(a_2,b_2)} * … * p_k^{max(a_k,b_k)} \tag5 lcm(x,y)=p1max(a1,b1)∗p2max(a2,b2)∗…∗pkmax(ak,bk)(5)
证明过程与最大公约数类似。
有了最大公约数和最小公倍数的定义,我们得出一个重要的结论:
x y = gcd ( x , y ) ∗ lcm ( x , y ) (4) xy = \text{gcd}(x,y)*\text{lcm}(x,y)\tag4 xy=gcd(x,y)∗lcm(x,y)(4)
因为 :
( p 1 m i n ( a 1 , b 1 ) ∗ p 2 m i n ( a 2 , b 2 ) ∗ … ∗ p k m i n ( a k , b k ) ) ∗ ( p 1 m a x ( a 1 , b 1 ) ∗ p 2 m a x ( a 2 , b 2 ) ∗ … ∗ p k m a x ( a k , b k ) ) = p 1 a 1 + b 1 ∗ p 2 a 2 + b 2 ∗ … ∗ p k a k + b k = 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 (p1min(a1,b1)∗p2min(a2,b2)∗…∗pkmin(ak,bk))∗(p1max(a1,b1)∗p2max(a2,b2)∗…∗pkmax(ak,bk))=p1a1+b1∗p2a2+b2∗…∗pkak+bk=xy