算数基本定理

定理

对于整数 \(a > 1\)，必有 \(a=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}\)，其中 \(p_j(1\leq j\leq s)\) 是两两不相等的质数，\(a_j(1\leq j\leq s)\) 表示对应质数的幂次。在不计次序的意义下，该分解式是唯一的。

运用于质因数分解：

int Decomposition(int x, int a[])
{
	int cnt = 0;
    for (int i = 2; i <= x / i; i++)
    {
		for (; x % i ==0; x /= i)
        {
            a[++cnt] = i;
        }
    }
    if (x > 1) a[++cnt] = x;
    return cnt;
}

推论

1. \(d\) 是 \(a\) 的约数的充要条件是 \(d=p_1^{e_1}p_2^{e_2}\dots p_s^{e_s},0\leq e_j \leq a_j,1\leq j \leq s\)，即 \(d\) 中每个质数的幂次都不超过 \(a\) 中每个质数的幂次。

   1. 每个质因子上的幂次直接决定了两数之间的整除性。
   2. \(12=2^2\times 3,72=2^3\times 3^2\)，看到 \(12\) 的质因子上的每个幂次都对应地比 \(72\) 小，便可以在进行取模运算的情况下给出 \(12|72\) 的结论。

2. 若 \(b=p_1^{e_1}p_2^{e_2}\dots p_s^{e_s}\)，（这里允许某些 \(a_j\) 或 \(e_j\) 为零），那么 \((a,b) = p_1^{d_1}p_2^{d_2}\dots p_s^{d_s},d_j = \min(a_j,e_j),1\leq j \leq s\)，以及\([a,b] = p_1^{y_1}p_2^{y_2}\dots p_s^{y_s},y_j = \min(a_j,e_j),1\leq j \leq s\)

   1. \(10 = 2\times 5,16 = 2 ^ 4\)

      1. \((10,16) = 2^{\min(1,4)} \times 5^{\min(1,0)} = 2^1 \times 5^0 = 2\)

      2. \([10,16] = 2^{\max(1,4)} \times 5^{\max(1,0)} = 2^4 \times 5^1 = 80\)

      3. \[(10,16)[10,16] = 2^{\min(1,4)} \times 5^{\min(1,0)}\times 2^{\max(1,4)} \times 5^{\max(1,0)} \\= 2^{\min(1,4) + \max(1,4)} \times 5^{\min(1,0) + \max(1,0)} \\= 2^{1 + 4} * 5^{1 + 0} \\10 \times 16 = 2 \times 5 \times 2^0 = 2 ^{1 + 4} \times 5^{1+0} \]

      4. 这刚好证明了 \([a_1,a_2](a_1,a_2) = a_1a_2\)，本质上是 \(\min(a,b) + \max(a,b) = a + b\)。

3. 用除数函数 \(r(a)\) 表示 \(a\) 的所有正约数的个数，则 \(r(a) = (a_1 + 1)(a_2+1)\dots (a_s+1) = r(p_1^{a_1})\dots r(p_1^{a_s})\)

   1. 即推论1.的推论，对于每个质因子上的幂次，可以取 \(0\) 到 \(a_i\) 中的任意整数，共有 \(a_i + 1\) 个。由乘法原理可以直接得出。
   2. 如 \(a=2^7 \times 3^8\times 5^9\)，可以直接写出 \(a\) 的因子个数 \((7 + 1)(8 + 1)(9 + 1) = 720\)
   3. 第二个等号展现了质因子的“独立性”。

4. 用除数和函数 \(o(a)\) 表示 \(a\) 的所有正约数的和，则 \(o(a) = \frac {p_1^{a_1 + 1} - 1} {p_1 - 1}\dots \frac {p_1^{a_s + 1} - 1} {p_1 - 1} = o(p_1^{a_1})\dots o(p_1^{a_s})\)。

   1. 亦为推论1.的推论，对于 \(a=120=2^3\times 3\times 5\) 的因子分别是 \(1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\)。

   2. 然后用等比数列求和公式(\(\frac {p_1^{a_1 + 1} - 1}{p_1 - 1} = 1 + p_1 + \dots + p_1^{a_1}\))展开那个算式。

      \(o(120) = \frac {2^4 -1}{2-1} \frac {3^2 -1}{3-1} \frac {5^2 -1}{5-1} = (2^3 + 2^2 + 2^1 + 1)(3^1 + 1)(5^1+1)\)

      最后再展开括号，即为所有因数。