算术基本定理

学习辗转相除法的理解与回顾，参考《什么是数学》¹一书. 若无额外说明，文中整数均指正整数.

1. 欧几里得辗转相除法

也许你了解著名的欧几里得算法可用于求两个整数的最大公因子，并且能很快速的用一门编程语言写出该算法，但是…背后的原理是什么呢？对此我一直很好奇，从刚开始的百思不得其解到现在的似懂非懂，可算是有一番体会了.

从学习加减乘除到现在，可能你都没有在意过这样一个事实：对于任意整数$a$和$b$，总可以用式子$a = k \cdot b + r$表示两者的关系. 其中$k$为$a$除以$b$的商，$r$为余数，且$0 \le r < b$. 当$r=0$时，也就意味着$b$能整除$a$，即$a$是$b$的整数倍. 比如对于$a=13，b=5$，有$13=5 \cdot 2 + 3$. 基于上面这个简单的事实，可以得出重要的结论，从前面的式子可以看出，若一个整数$d$能同时整除$b$和$r$，则$d$也同时整除$a$和$b$. 因为当$d$整除$b$和$r$时，也整除了$a$. 换言之，所有能同时整除$b$和$r$的整数，也能整除$a$和$b$，反之亦然.

若用$(a,b)$表示$a$和$b$的最大公因子，那么根据上面的讨论我们得到

$$(a,b) = (b,r)\qquad\qquad\qquad(1)$$

也就是说，我们求$(a,b)$，可以换成求$(b,r)$，反复使用式(1)进行计算，直至余数为0. 比如我们要求$52$和$16$的最大公因子，因为$52=3 \cdot 16 + 4$，$16 = 4 \cdot 4 + 0$，故$(52,16)=(16,4)=(4,0)=4$. 相信你已经看出欧几里得算法的玄机了，精致优雅的算法来自于对简单事实的观察和应用.

从辗转相除法可以得到下面的推论：

推论

• 设$(a,b)=d$，则总能找到或正或负的整数$k$和$l$，使得

$$d=k\cdot a+l\cdot b$$

证明: 由前面的叙述可知

$$\begin{equation} a = k_1b + r_1\\ b = k_2r_1 + r_2\\ r_1 = k_3r_2 + r_3\\ \cdots \\ r_{n-1}=k_{n+1}r_n+r_{n+1}\\ r_n = k_{n+2}r_{n+1} + 0 \end{equation}$$

因此，得到

$$r_1=a-k_1b$$

这儿$k=1，l=-k_1$，继续这个步骤有

$$r_2=b-k_2r_1 = b-k_2(a-k_1b)=-k_2a+(1+k_1k_2)b$$

如此一直计算到$r_{n+1}$，可见始终可以将余数$r_i$用$a$和$b$表示为式(1)的形式，这包括$a$和$b$的最大公因子. 证毕.

或许你也和我一样，并不知道这个推论到底有什么用，但又总是在某些地方看见它的身影（比如离散数学？），没关系，下面我们就会看见它的一个应用. 所谓书到用时方恨少，而“定理难证时方恨工具少”，工具就是这些不起眼的推论、引理、事实、定义、概念等，工具用的熟悉了，用它们做东西自然就更快了，你觉得呢…

2. 算术基本定理

算术基本定理讲的是任意一个大于$1$的整数，将其分解为素因子的乘积的形式是唯一的. 比如$2\cdot 2\cdot 3\cdot 3$就是整数$36$的唯一素因子分解形式.

令人惊讶的是（至少我是惊讶的…），这个定理可以用前面讲述的辗转相除法及其推论加以证明，不过在此之前，我们先来看一条引理，平凡而优美.

引理

• 若素数$p$能整除$a$和$b$的乘积，那么$p$必能整除$a$或$b$.

证明: 假设$p$不能整除$a$，又$p$是素数，它的因子只有$1$和$p$，故$(p,a)=1$，由式$(1)$得

$$1=kp+la\qquad\qquad\qquad(2)$$

又因为$p$整除$ab$，故$ab=pr$，在式$(2)$两端同时乘以$b$得

$$b = kpb + lab = kpb + lpr=p(kb+lr)$$

所以$p$是$b$的一个因子，因而$p$整除$b$，于是我们从假设$p$不整除$a$推出了$p$必定整除$b$. 证毕.

我们可以将上面的引理进行推广：

推论

• 若$s=a_1a_2a_3\cdots a_n$且素数$p$整除$s$，那么$p$必定能整除$a_1, a_2, a_3, \cdots, a_n$中的某一个数.

证明: 用数学归纳法.

(1) 假设$n=r$时命题成立，当$n=r+1$时，

$$s=a_1a_2\cdots a_ra_{r+1}=(a_1a_2\cdots a_r)\cdot a_{r+1} = qa_{r+1}$$

由上述引理知，$p$必定整除$q$或$a_{r+1}$. 若$p$整除$q$，由假设可知，$p$必定整除$a_1, a_2, \cdots, a_r$中的一个数；否则$p$整除$a_{r+1}$，因此，当$n=r+1$时，命题也成立.

(2) 当$n=1$时，$p$整除$s=a_1$，命题显然成立.

证毕.

讲完诸多引理推论后，终于该证明一下我们期待已久的算术基本定理了. 假设整数$n$有两种不同的素因子分解形式

由于$p_1$是$n$的一个因子，所以$p_1$整除$n$，由上面的推论知，$p_1$必定整除$q_1, q_2, \cdots, q_s$的一个数，而$q_1, q_2, \cdots, q_s$均为素数，因子只能是$1$和自身，故$p_1$一定等于$q_1, q_2, \cdots, q_s$中的一个数，假设这个数是$q_1$，于是可以把等式两边的$p_1$和$q_1$约掉，然后重复上面的过程，最终等式两边只能是$1$. 由于$p_i$和$q_i$始终是成对抵消的，因此上面的的两种分解形式其实是一样的. 证毕.

参考