概念

算术基本定理

任何大于 1 的整数可唯一分解为素数的乘积，欧几里得算法高效求最大公约数，是初等数论一切结论的基石。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

算术基本定理数系理论

01定义

算术基本定理断言：任何大于 1 的整数可唯一地分解为素数的乘积（不计顺序）。素数是乘法的「原子」，欧几里得算法高效求最大公约数——这组事实是初等数论一切结论的基石。

60 的唯一素因子分解：2² · 3 · 5

存在性由良序原理（最小反例法）得到；唯一性的关键是欧几里得引理：素数 $p\mid ab$ 则 $p\mid a$ 或 $p\mid b$ 。

辗转相除求 $\gcd$ ： $\gcd(a,b)=\gcd(b,a\bmod b)$ ，复杂度是对数级——两千多年前的算法至今是数论计算的核心。

欧几里得证明素数有无穷多个：假设有限则 $p_1\cdots p_n+1$ 有新素因子，矛盾——「最优美的证明」之一。

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\quad(\text{唯一})

\gcd(a,b)=\gcd(b,\,a\bmod b)

欧几里得《几何原本》卷 VII-IX（约公元前 300 年）已含算术基本定理与素数无穷的证明；高斯 1801 年《算术研究》给出第一个完全严格的一般陈述。

RSA 加密建立在大整数分解的困难性上；哈希、伪随机数、纠错码都依赖素数算术；分解唯一性也是代数数论研究「唯一性何时失效」的出发点。

算术基本定理：唯一素因子分解每个 n>1 可唯一写成素数乘积：因子树层层分解

n60