质因数分解
zhì yīn shù fēn jiě
质因数分解是把一个合数表示为其质因数乘积的过程。
Formula
n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}
Definition
质因数分解是指把一个数拆解成若干质数的乘积，反复除下去直到每一部分都是质数为止。形式上，$n$ 的质因数分解是把它唯一地表示为质数幂的乘积，$n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$，其存在性与（不计顺序的）唯一性由算术基本定理保证。这种唯一性并非显然：它需要证明若 $p \mid ab$ 则 $p \mid a$ 或 $p \mid b$，而这依赖于贝祖等式，进而依赖于欧几里得算法；在唯一分解整环中，同样的唯一性对不可约元素更一般地成立。
Example
$36$ 的质因数分解：$36 = 2 \times 18 = 2 \times 2 \times 9 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$。$360 = 2^3 \times 3^2 \times 5$ 的质因数分解可以用来求 $\text{GCF}(360, 84)$，因为 $84 = 2^2 \times 3 \times 7$，所以 $\text{GCF} = 2^2 \times 3 = 12$。整数分解通常在计算上是困难的：已知最好的经典算法（一般数域筛法）运行时间为亚指数级 $\exp(O(n^{1/3}))$，而肖尔的量子算法能在多项式时间内完成分解，对 RSA 构成威胁。
Key Insight
因数树是一个很有用的工具：分出任意两个因数，然后继续对每个因数分支，直到所有分支都变成质数为止。每一次求最大公约数或最小公倍数的计算，本质上都是一个质因数分解问题：求最大公约数取每个质数的最小指数，求最小公倍数取最大指数。