y 总在算法基础课数学知识章节中的第一讲中多次提到了算术基本定理，这里记录一下作为一个数论小白的我搞清楚算术基本定理所需要的一切。
分为几个部分：
1. 前置概念定义：简要介绍后文证明过程中需要的名词定义以及基本公理
2. 算术基本定理的证明需要的前置定理证明：算术定理的唯一性证明需要用到欧几里得引理，而欧几里得引理的证明需要用到贝祖定理，贝祖定理的证明又依赖带余除法定理。因此这里按照带余除法定理->贝祖定理->欧几里得引理->算术基本定理 的顺序一路证明下去
3. 算术基本定理的证明

前置概念定义

质数定义

质数（Prime）又称素数，一个大于 $1$ 的自然数，除了 $1$ 和它自身外，不能被其他自然数整除的数叫做质数；否认称为合数

约数/因数定义

约数/因数（Divisor）
对于两个整数 $a$ 和 $b$ ，如果存在一个整数 $k$ ，使得 $b=a\cdot k$ 成立，那么我们就说 $a$ 是 $b$ 的约数（或因数），也称作 $a$ 整除 $b$ ，通常用符号 $a | b$ 表示 $a$ 整除 $b$

最大公约数（GCD) 定义

GCD （Greatest Common Divisor）
两个或多个整数的最大公约数，是指能够同时整除这些整数的最大正整数。例如， 8 和 12 的最大公约数是 4，因为 4 是能同时整除 8 和 12 的最大整数。通常用 $gcd(a,b)$ 来表示 $a$ 和 $b$ 的最大公约数

ps: 当两个数的 gcd 为 1 时，我们就说两个数是互质的

线性组合

对于两个整数 $a$ 和 $b$ ，他们的线性组合是指任何形如 $ax+by$ 的表达式，其中 $x$ 和 $y$ 也是整数。

良序公理

良序原理是皮亚诺算术公理系统（PA）的一个推论，PA 简单来说 就是一个算术系统，它规定了有关自然数的五条公理，很多基本的定理都是从这五条公理推出。当然还有其他的公理系统存在，公理一般都是一些平凡的不证自明的事实。设置公理系统目的是为了让数学证明更标准化，就像各种编程语言中的最基础的语法一样。想要深入了解就要窥探到数理逻辑领域了，在此不做展开。
简而言之良序公理描述了自然数的一个基本性质：任何非空的自然数集合都包含一个最小元素。用通俗的话来说就是，想象一个装满了自然数的袋子，只要这个袋子里至少有一个数，你就能保证在里面找到一个最小的数，无论袋子里的数有多大，排列有多么混乱，一定有一个最小的存在。

数学归纳法

数学归纳法源自于皮亚诺算术公理的五条公理中的归纳公理。简单来说，归纳公理表达的是：如果我们可以证明一个命题对自然数 0 为真；同时当我们假定该公理对自然数 $k$ 为真时，可以推理出该公理对自然数 $k+1$ 也为真； 那么，命题对所有自然数都为真。（就是一个递推的过程，先证明了对初始值为真，再假定对 k 为真时如果能推出对 k+1 为真，那么显而易见可以从初始值出发递推出集合内所有k 都为真）

带余除法定理

数论意义上的除法

定理陈述

任意 $a,b \in \mathbb{Z},b>0$ ，则存在唯一 $r, q \in \mathbb{Z}$
使其写为 $a=r+bq$ 且 $0\leq r<b$
简单来说就是 对于任意整数 $a$ （被除数）和任意正整数 $b$ （除数），存在唯一的整数 $q$ （商）和整数 $r$ （余数）。

定理证明

1. 存在性证明（证明存在整数 $q$ 和 $r$ 满足 $a=bq+r$ 且 $0\leq r<b$）
2. 唯一性证明 （证明商 $q$ 和 余数$r$ 是唯一的）

证1

• 构造集合
  考虑集合 $S$ ，定义为 $S=\left\{ a-bk|k为整数，且a-bk\geq 0 \right\}$
  证明集合不是空集（分类讨论 $a$）：

  • 如果 $a\geq 0$ ，只要取 $k=0$ ，那么 $a-b \cdot 0=a\geq 0$，$S$ 非空
  • 如果 $a<0$ ，可以取 $k=a$ ，那么 $a - b \cdot a=a(1-b)$，由于除数 $b$ 一定是正整数，所以 $1-b \leq 0$，因此 $a(1-b) \geq 0$ ，$S$ 非空。
  • 总之 无论 $a$ 正负， $S$ 一定非空，且是非负整数集合。由于良序公理，$S$ 中必然存在最小正整数，记作 $r$

• 证明 $r$ 满足 $0\leq r<b$

  • 采用反证法：
  • 假设 $r\geq b$ ，由于 $r=a-bk$，那么 $a-bk \geq b$ ，即 $a-(k+1)b\geq 0$ ，即不等式左侧为 $r_{1}$
  • 由于 $k$ 为整数，$k+1$ 显然为整数，因此 $r_{1} \in S$
  • 由于 $b > 0$ 可知， $r_{1} < r$ ，而 $r$ 是 $S$ 中的最小元素， $r_{1} < r$ 说明 $r$ 不是最小元素，矛盾。因此 $r\geq b$ 不可能，即 $0\leq r<b$

证毕

证2

为了证明商 $q$ 和余数 $r$ 是唯一的。先假设存在两组解 $(q_{1},r_{1})$ 和 $(q_{2},r_{2})$ 都满足带余除法定理的条件，即

• $a=bq_{1}+r_{1}$ 且 $0\leq r_{1}<b$
• $a=bq_{2}+r_{2}$ 且 $0\leq r_{2}<b$

因此 $bq_{1}+r_{1}=bq_{2}+r_{2}$ ，移项得 $r_{2}-r_{1}=b(q_{1}-q_{2})$
由于 $0\leq r_{1}<b$ ，所以 $-b<-r_{1}\leq 0$
由于 $0\leq r_{2}<b$，与上面不等式相加得到 $-b\leq r_{2}-r_{1} < b$ ，即$\left| r_{2}-r_{1}\right| <b$
由于 $r_{2}-r_{1}=b(q_{1}-q_{2})$ 且 $\left| r_{2}-r_{1}\right| <b$ 且 $b$ 是非负整数，$q_{1},q_{2}$ 都是整数，那么只可能： $r_{2}-r_{1}=0$ 且 $q_{1}-q_{2}=0$ , 即 $r_{1}=r_{2},q_{1}=q_{2}$， 因此 商 $q$ 和余数 $r$ 是唯一的

证毕

总结：对于任意整数 $a$ （被除数）和任意正整数 $b$ （除数），整数 $q$ （商）和整数 $r$ （余数）存在且唯一。

贝祖定理

贝祖定理也称为为贝祖恒等式、裴蜀定理，是数论中要给非常重要且实用的定理。它描述了两个整数的最大公约数（$GCD$）和 这两个整数的线性组合 之间的关系

定理陈述

对于任意两个整数 $a$ 和 $b$ ，设它们的最大公约数为 $d=gcd(a,b)$ 。那么，一定存在整数 $x$ 和 $y$ （不一定唯一），使得以下等式成立：
$$ax + by = d$$
换句话说，两个整数 $a$ 和 $b$ 的最大公约数 $d$ ，总是可以表示成 $a$ 和 $b$ 的线性组合

ps ： 且这个 d 一定是 ax + by 能凑出来的最小正整数

定理证明

• 构造集合
  对于就任意非零整数 $a$ 和 $b$ ，考虑它们的所有整数线性组合构成的集合：
  $$S=\left\{ ax+by|x,y \in \mathbb{Z},ax+by>0 \right\}$$
  证明集合不是空集：由于 $a$ 和 $b$ 不全为零，可以选取适当的整数 $x,y$ 使得 $ax+by$ 大于零。故 $S$ 中必有正整数，$S$ 非空。
  由于良序公理，$S$ 中存在最小正整数，记作 $d$ ，即 $d=ax_{0}+by_{0}$ ，其中 $x_{0},y_{0} \in \mathbb{Z}$ 且 $d>0$

• 证明 $d$ 整除 $a$ 、 $b$
  根据带余除法定理，对于整数 $a$ ，可以写成 $a=dq+r$ , 其中 $q \in \mathbb{Z}$ 且 $0\leq r<d$
  由于 $d=ax_{0}+by_{0}$ , $r=a-dq = a-q(ax_{0}+by_{0})=a(1-qx_{0})+b(-qy_{0})$
  $r$ 也是 $a$ 和 $b$ 的整数线性组合，来分析以下 $r$
  $0\leq r<d$ ，但一旦 $r > 0$ ，那么 $r \in S$ ，与 $d$ 是 $S$ 中的最小正整数矛盾
  因此， 必有 $r=0$ ，即 $d$ 整除 $a$
  同理也可证 $d$ 整除 $b$

• 证明 $d$ 是 $gcd(a,b)$
  假设 $c$ 是 $a,b$ 的任意公约数，则 $c$ 整除 $ax_{0}$ 和 $by_{0}$ ，从而 $c$ 整除 $ax_{0}+by_{0}$ ，即 $c$ 整除 $d$
  由于 $d$ 是正数，且 $d$ 可以同时整除 $a,b$，这说明 $d$ 是所有公约数中最大的一个，即 $d=gcd(a,b)$

综上所述，证明完毕 , 一定有整数 $x_{0},y_{0}$ 使得 $ax_{0}+by_{0}=d=gcd(a,b)$

欧几里得引理

引理陈述

若质数 $p$ 整除 $a\cdot b$ （即 $p|a\cdot b$），则 $p$ 必整除 $a$ 或 $p$ 必整除 $b$

引理证明

分类讨论
当质数 $p$ 整除 $a \cdot b$ 时

• 如果 $p$ 整除 $a$ （即 $p|a$），结论成立
• 如果 $p$ 不整除 $a$ （即 $p\nmid a$） ：
  • 因为 $p$ 是质数， 且 $p\nmid a$ ，所以 $p$ 与 $a$ 互质，即 $gcd(p,a)=1$
  • 根据贝祖定理，存在 $x,y$ 使得 $px+ay=1$
  • 等式两边同时乘以 $b$ ，得到 $pbx+aby=b$
  • 由于 $p|ab$ ，即 $ab=kp$ ，代入得 $pbx+pky=p(bx+ky)=b$
  • 因此 $p|b$ ，即 如果 $p$ 不整除 $a$ ，那么 $p$ 一定整除 $b$

结论：对于质数 $p$ 整除 $ab$ 时，无论 $p$ 是否整除 $a$ ， 最后 $p$ 一定要么整除 $a$ , 要么整除 $b$
证毕 （同时利用这个方法递推，很容易把这个引理推广到多个数的乘积，即若质数$p$ 整除 $a_{1}\times a_{2}\times \dots \times a_{r}$ ，则 $p$ 必然至少整除 $a_{1}\dots a_{r}$ 集合中的一个）

算术基本定理

算术基本定理，又称唯一分解定理，是数论中的核心定理之一

定理陈述

每个大于 $1$ 的自然数，要么本身是质数，要么可以唯一的分解为有限个质数的乘积。（这里的唯一是指不考虑质数排列顺序的情况下，分解形式是唯一的）

定理证明

1. 存在性证明（证明对任意大于 $1$ 的自然数 $n$, 要么是质数，要么存在至少一种质因数分解）
2. 唯一性证明（分解方式唯一）

证1

证明对任意大于 $1$ 的自然数 $n$, 要么是质数，要么存在至少一种质因数分解
数学归纳法：

• 当 $n=2$ 时, $2$ 是质数，成立
• 归纳假设：对于任意 $2 \leq m \leq k$ ，m 都存在质因数分解
• 需要证明对于整数 $k+1$ 也存在质因数分解
  • 若 $k+1$ 为质数，成立
  • 若 $k+1$ 为合数，一定有 $k+1=a\cdot b\ (1<a, b<k+1)$。根据归纳假设，$a$、$b$ 一定存在质因数分解, 即 $a = p_{1}\cdot p_{2}\cdot\dots p_{r},b = q_{1}\cdot q_{2}\cdot\dots q_{s}$ , 那么 $k+1=a\cdot b=p_{1}\cdot p_{2}\cdot\dots p_{r}\cdot q_{1}\cdot q_{2}\cdot\dots q_{s}$ ，即 $k+1$ 为合数时存在质因数分解成立

证毕

证2

证明分解方式唯一
假设存在一个大于1 的自然数 $n$ ，它存在两种不同的质因数分解方式（不考虑顺序），设这两种分解为：

• $n=p_{1}\times p_{2}\times \dots \times p_{r}$
• $n=q_{1}\times q_{2}\times \dots \times q_{s}$

其中 $p_{1}\dots p_{r},q_{1}\dots q_{s}$ 都是质数，由于我们假设这是两种不同的质因数分解方式，那么意味着至少有一个质因数只出现在其中一个分解中。
为了方便我们可以把 $p_{1}\dots p_{r},q_{1}\dots q_{s}$ 中相同的质因数约掉，只保留不同的那些质因数，约减后的结果为：
$$p_{1}’\times p_{2}’\times \dots \times p_{r}’=q_{1}’\times q_{2}’\times \dots \times q_{s}’$$
此时 $p_{1}’\dots p_{r}’,q_{1}’\dots q_{s}’$ 是两组互不相同的质数集合了，完全没有共同元素
根据欧几里得引理（推广到多个整数乘积的版本）， $p_{1}’$ 必然整除 $q_{1}’\dots q_{s}’$ 其中的至少一个
现在假设 $p_{1}’$ 整除的是 $q_{j}’$ （其中 $j$ 属于 $1 \dots s$ 中的一个），但 $q_{j}’$ 是个质数啊，一个质数能整除另一个质数，只有一种可能 $p_{1}’=q_{j}’$ ，这与 $p_{1}’\dots p_{r}’,q_{1}’\dots q_{s}’$ 是两组互不相同的质数集合的推论矛盾了。因此存在两种不同的质因数分解方式的假设是错误的！ $p_{1}\dots p_{r},q_{1}\dots q_{s}$ 两个集合约掉相同的质数后，永远至少还能找到一对相同的质数，即 $p_{1}\dots p_{r},q_{1}\dots q_{s}$ 两个集合一定是相同的集合。
结论：任意大于1 的自然数 $n$ ，它的质因数分解方式一定是唯一的（不考虑顺序），唯一性证明完成。

总结：每个大于 $1$ 的自然数，要么本身是质数，要么可以唯一的分解为有限个质数的乘积。