算术基本定理

概述

算术基本定理（Fundamental Theorem of Arithmetic）：每个大于 $1$ 的整数都可以唯一地表示为素数的乘积（不计因子的顺序）。即若 $n>1$，则 $n=p_1{p}_2\cdots p_k$，其中 $p_i$ 为素数，且该分解在因子排列的意义下唯一。

定理陈述

形式化陈述

定理（算术基本定理 / 唯一分解定理）： 设 $n$ 是大于 $1$ 的整数，则：

（存在性） $n$ 可以写成素数的乘积，即存在素数 $p_1,p_2,\dots ,p_k$（$k\ge 1$），使得 $n=p_1\cdot p_2\cdot \cdots \cdot p_k$

（唯一性） 若 $n$ 有两种素因子分解： $n=p_1{p}_2\cdots p_r=q_1{q}_2\cdots q_s$ 其中 $p_i$、$q_j$ 均为素数，则 $r=s$，且在适当重排后 $p_i=q_i$（对所有 $i=1,2,\dots ,r$）。

标准形式：通常将相同的素因子合并，写成 $n=p_1^{a_1}\cdot p_2^{a_2}\cdot \cdots \cdot p_m^{a_m}$ 其中 $p_1<p_2<\cdots <p_m$ 为不同素数，$a_i\ge 1$ 为正整数。

证明概要

证明思路

存在性：强归纳法

基础步：$n=2$ 是素数，本身就是素数的乘积（单个素因子）。

归纳步：假设对所有满足 $2\le m<n$ 的整数 $m$，存在性成立。考虑 $n$：

• 情况一：$n$ 是素数。则 $n$ 本身就是素数的乘积，存在性成立。
• 情况二：$n$ 是合数。则存在 $a,b$ 满足 $2\le a<n$，$2\le b<n$，使得 $n=a\cdot b$。由归纳假设，$a$ 和 $b$ 都可以分解为素数的乘积： $a=p_1{p}_2\cdots p_j,b=p_{j+1}{p}_{j+2}\cdots p_k$ 因此 $n=p_1{p}_2\cdots p_k$，存在性成立。

由强归纳法原理，存在性对所有 $n>1$ 成立。$■$

唯一性：欧几里得引理 + 反证法

唯一性的证明依赖于以下关键引理：

欧几里得引理：若素数 $p$ 整除 $ab$，则 $p\mid a$ 或 $p\mid b$。

该引理可由 贝祖定理 证明：若 $p\nmid a$，则 $\gcd (p,a)=1$，存在 $x,y$ 使得 $px+ay=1$，两边乘以 $b$ 得 $pbx+aby=b$。因为 $p\mid ab$，所以 $p\mid b$。

唯一性证明（反证法）：

假设存在大于 $1$ 的整数拥有两种不同的素因子分解。由良序性，设 $n$ 是满足此条件的最小整数：

$n=p_1{p}_2\cdots p_r=q_1{q}_2\cdots q_s$

其中两种分解在排列意义下不同。

1. 因为 $p_1\mid n=q_1{q}_2\cdots q_s$，反复应用欧几里得引理，可知 $p_1$ 必须整除某个 $q_j$。
2. 由于 $q_j$ 是素数，且 $p_1$ 也是素数，故 $p_1=q_j$。
3. 两边消去 $p_1$（即 $q_j$），得到： $n^{\prime }=p_2{p}_3\cdots p_r=q_1\cdots q_{j-1}{q}_{j+1}\cdots q_s$
4. 但 $n^{\prime }=n/p_1<n$，且 $n^{\prime }$ 也有两种不同的素因子分解，这与 $n$ 的最小性矛盾。

因此不存在这样的 $n$，唯一性得证。$■$

关键推论

• 推论1（素数整除性）：若素数 $p$ 整除 $n=p_1^{a_1}\cdots p_m^{a_m}$，则 $p$ 必等于某个 $p_i$。
• 推论2（整除的判定）：$a\mid b$ 当且仅当 $a$ 的标准分解中每个素因子的指数不超过 $b$ 中对应素因子的指数。
• 推论3（GCD与LCM公式）：利用素因子分解可直接计算 最大公约数 和最小公倍数： $\gcd (a,b)=\prod p_i^{\min ({\alpha }_i,{\beta }_i)},\mathrm{lcm}(a,b)=\prod p_i^{\max ({\alpha }_i,{\beta }_i)}$
• 推论4（素因子个数）：$n$ 的正因子个数为 $\tau (n)=(a_1+1)(a_2+1)\cdots (a_m+1)$。

应用场景

1. 简化分数：将分子分母分别分解为素因子乘积，然后消去公共因子。
2. 密码学基础：RSA 的安全性依赖于大整数素因子分解的计算困难性，而算术基本定理保证了这种分解的存在性和唯一性。
3. 数论函数计算：欧拉函数 $\phi (n)$ 的计算公式 $\phi (n)=n{\prod }_{p\mid n}(1-1/p)$ 直接依赖于唯一分解。
4. 整除性分析：证明整除关系时，通过比较素因子分解中的指数是最基本的方法。

数值示例

• $600=2^3\times 3^1\times 5^2$（唯一分解）
• $360=2^3\times 3^2\times 5^1$
• $\gcd (600,360)=2^{\min (3,3)}\times 3^{\min (1,2)}\times 5^{\min (2,1)}=2^3\times 3^1\times 5^1=120$
• $\mathrm{lcm}(600,360)=2^{\max (3,3)}\times 3^{\max (1,2)}\times 5^{\max (2,1)}=2^3\times 3^2\times 5^2=1800$

参见

• 整除
• 素数
• 最大公约数
• 欧拉函数
• 欧几里得算法
• 贝祖定理

参考链接

• Fundamental Theorem of Arithmetic (U Hawaii)
• Unique Factorization - LibreTexts