动机
像 这样的方程要求系数为整数的解,因此普通的除法无法解决它。在有理数范围内有无穷多个解;在整数范围内,整除性造成了一种障碍。最大公因数恰好度量了这一障碍。其计算过程还给出了相应的系数,使这一障碍同时成为充分条件。
定义
定义 1.1.1
(整除、最大公因数与素数)
对于整数 ,若存在整数 使得 ,则记 。对于不全为零的 , 是它们的最大正公因数。若两个整数的 gcd 为 ,则称它们互素。素数是满足 且仅有正因数 与 的整数 ;大于 且不是素数的整数称为合数。
要求正性使得 gcd 是唯一的;输入的正负号无关紧要。特别地,对于非零的 ,有 。我们把 排除在此处使用的定义之外。整除关系具有传递性,而 的公因数能整除每一个整数组合 。这一初等观察正是连接算术与方程的桥梁。
对于带符号的输入,先取绝对值;若其中一个输入为零,则另一个的绝对值就是 gcd,并且已经给出了贝祖(Bézout)等式。否则,在开始做除法之前,先把两个正的绝对值排好顺序,并在最后的系数中恢复正负号。对于 与 ,带余除法给出唯一的整数 ,使得 且 。存在性可取不超过 的 的最大倍数得到。若存在两个这样的表达式,相减后会得到 的一个绝对值小于 的倍数,这迫使两个余数相等,进而两个商也相等。
定理/命题
定理 1.1.2
(欧几里得(Euclid)算法与贝祖等式)
设 为不全为零的整数,并设 。反复做除法会终止,其最后一个非零余数等于 。存在整数 使得 。因此,方程 有整数解,当且仅当 。
定理 1.1.3
(欧几里得引理与唯一分解)
若素数 整除 ,则 或 。每个整数 都是若干素数的乘积,并且其素因数构成的多重集是唯一的。
证明思路
证明
(每次除法保留公因数)
若 ,则一个数同时整除 ,当且仅当它同时整除 。因此每一次欧几里得除法都保持公因数的集合不变。正的余数严格递减,所以这一过程会终止。在最后的数对 处,正的公因数恰好是 本身的因数。通过回代,每个余数、从而 ,都可以表示为原始输入的整数组合。方程的必要性成立,是因为 整除每一个组合;充分性成立,是因为把 乘以 即可。
证明
(由贝祖等式得欧几里得引理,再以递降与约去得唯一分解)
要证明欧几里得引理,设 。由于 是素数,故 。写出 并乘以 。若 ,则 与 都能被 整除,所以 。
分解的存在性由强归纳法得到:若 是合数,则写 ,其中 ,再对这两个较小的整数做分解。对于唯一性,比较两个素数乘积。一侧的第一个素数整除另一侧的乘积,因此反复使用欧几里得引理可知,它等于另一侧的某个素数。在整数中约去这个素数,然后重复这一步骤。由于非空的素数乘积大于 ,这一过程会同时耗尽两个列表。
证明透视
各个假设在唯一分解中的作用位置
正性使得对大小做归纳成为可能。合数的输入分裂为严格更小的正因数,从而给出存在性。素性与贝祖等式一起给出欧几里得引理,使得相互竞争的两个乘积中的因数可以配对。随后的约去把比较化归为更短的比较。结论与试除因数被找到的顺序无关,因为每一种有效的分解都具有相同的素数重数。
例题详解
例题 1.1.4
(计算障碍并求出一个解)
以下除法 ,,, 给出 gcd 为 。回代得到
因此 是 的一个解。相反,同一个左端不可能等于 ,因为 。
例题 1.1.5
(描述全部整数解)
由前一个解可得 。两边除以 ,得到 。由 互素,推出 。于是每个解都形如
代入即可验证所有这些数对都是解。这一论证同时证明了不存在其他的解。
例题 1.1.6
(赋值把 gcd 与 lcm 变成逐坐标的运算)
对于素数 与正整数 ,令 为 在 的分解中的指数。由于 且 ,它们的 gcd 为 ,它们的最小正公倍数为 。取最小指数得到 gcd;取最大指数得到 lcm。因此,对于正整数 ,有 。
把 gcd 理解为完整的障碍
在“gcd 控制着方程”这句话里,隐含着两个断言。第一,每个可取到的右端都能被 gcd 整除。这是一个必要条件,在运行任何算法之前就已成立。第二,gcd 的每个倍数都是可取到的。这是一个充分性的陈述,需要用到贝祖等式。把这两个方向分开,可以避免一个常见的逻辑漏洞:找到一个障碍本身并不能证明不存在其他的障碍。
考虑所有能写成两个输入的组合的整数。这个集合包含零,对加法封闭,对取相反数也封闭。若两个输入不全为零,它就包含一个正整数。取其中最小的正元素,记为 。用 去除任何可取到的整数,所得余数仍是可取到的;由最小性,该余数必为零。因此,全体可取到的整数恰好就是 的倍数。由于输入本身是可取到的, 整除这两个输入。又由于每个公因数都整除每一个组合,不可能有更大的正公因数。这就给出了贝祖等式的第二个证明,它强调的是全体组合的结构,而不是某个具体的计算。
概念视角结构
用两种描述看同一个 gcd
按大小关系的定义,是选取最大的正公因数。按组合的描述,是选取可取到的最小正线性组合。上面的论证证明了这两种描述一致。其中“最大”与“最小”所指的是不同的集合。混淆这两个集合会使结论听起来自相矛盾;分清这两个集合,则能说明这一等价为何有用。
这第二个证明还说明了为什么整数在这里很关键。由正有理数组合构成的非空集合不一定有最小元素。在有理数范围内,把系数除以另一个正整数,就会产生更小的正组合。整数的离散序在这里起着真正的作用,即使初等的计算掩盖了这一点。
从一个解到全部解
一个特解固然有用,但它很少是整数方程问题的终点。设两个系数均非零,gcd 为正,并且已经找到了一个解。把它所满足的方程与任意第二个解所满足的方程相减,右端相互抵消,剩下一个齐次方程。两个系数同除以 gcd,它们就互素了。其中一个约化后的系数必须整除另一个变量的改变量。引入由此得到的整数参数,再代回去。这就是为什么例题中的参数是系数除以其 gcd,而不是原来的系数本身。
这些参数的正负号是相互关联的。第一个变量增加约化后的第二个系数时,第二个变量必须减少约化后的第一个系数;否则左端会发生变化,而不是保持不变。因此,快速代入是检验所提出的参数化的一个有用方法。它验证充分性,而互素性的论证则验证完备性。两者不可互相替代。
随后还可以对参数施加额外的约束。例如,若问题要求非负解,则它变成关于单个整数参数的一对线性不等式。如果下界大于上界,那么即使不加限制的整数解有无穷多个,也不存在非负解。整除性回答的是一条直线是否与整数格点相交;符号约束问的则是这些格点中哪些落在指定的区域内。这两个问题相关,但并不相同。
为什么唯一分解是一个定理
人们很容易把分解看成一种毫无歧义的记法,因为熟悉的计算总是给出同样的结果。是证明为这种做法提供了依据。存在性用到的是下降到更小的正因数。唯一性用到的则是另一个要素:整除乘积的素数必须整除其中一个因数。没有这一蕴含,把一个列表中的素数与另一个列表中的素数对应起来的那一步就没有依据。
还要注意,一个列表中的素数如果整除另一侧的某个素数,它就必须等于那个素数。二者都是正素数,所以第二个素数的正因数只有 与它本身。当把分解的论证推广到不可约元与素元可能不同的情形时,这一小步就很重要。这里并不假定任何这样的推广;整数情形下的证明在其所述的范围内是完整的。
一个实际的推论是用指数来判断整除。对于正整数,一个数整除另一个数,当且仅当第一个数中每个素数的指数都不大于第二个数中对应素数的指数。正向的推导由对商做分解得到。反向的推导则通过指数相减来构造商,而所有这些差都仍然非负。这样便是证明,而不只是暗示了 gcd 与 lcm 的取最小与取最大法则。
验证证书比发现证书更容易
设某个计算报告了一个正的 gcd 候选值,以及把它表示为输入组合的两个系数。要验证这个答案,需检查候选值整除每个输入,并检查线性组合的等式。第一项检查说明候选值是一个公因数。第二项检查说明每个公因数都整除候选值。二者合起来就推出它是最大的。仅仅给出一个公因数,或者仅仅给出一个组合,都只提供了证书的一半。
即使算法是由软件实现的,这种验证方式也同样有用。余数表中的抄写错误,也许很难通过逐个检查商而发现,但最终的证书只有两个整除性检查和一个精确的等式。数学证明解释了为什么这些小小的检查就足够了;它不要求我们信任整个计算的过程。
思想史
同一化归的较早表述
在《几何原本》第七卷命题 2 中,欧几里得通过反复相减来处理最大公度,并通过余数来追踪公度。现代的商与余数记法把反复的相减归并为一步。这是与现存的一种书面表述所作的比较,而不是关于首次发现的断言。
常见错误
常见错误
(公因数不一定是最大公因数)
gcd 不是随便某个公因数: 同时整除 与 ,但它不是它们的 gcd。 也并不意味着 有唯一的解;它保证的是解的存在。必须保留整数参数,才能描述全部的解。
常见错误
(互素不等于素数)
另一个似是而非的说法是, 互素就使得它们各自是素数。互素只是说它们的素因数集合不相交: 与 就是互素的合数。使用唯一分解时,要指明是正整数,或者先把符号分离出去; 除了其正的素因数之外,还需要一个因子 。
反例模式
欧几里得引理需要素数除数
命题:若 ,则 或 。取 、、: 被 整除,但 且 。证明在第一步便失效: 并不推出 ,事实上 。若把合数除数当作素数来处理,引理和唯一性的论证都会失效。修正后的叙述是对素数 成立的欧几里得引理,以及它的互素版本:若 且 ,则 。
总结
欧几里得算法在缩小输入的同时保持公因数不变。回代给出 gcd 的证书,并求解相应的整数方程。贝祖等式证明了欧几里得引理,从而使素因数分解唯一,并把整除性问题转化为指数的比较。
练习
快速检查
(求 的全部整数解。)
在引入参数之前,先计算 gcd 并求出一个解。
解答 · 答案
由于 且 ,故 。一个解为 。把齐次的差方程除以 ,得到 。于是对 ,有 ,。每一个数对都是解,而 互素则证明了完备性。
快速检查
(证明:若 且 ,则 。并在去掉互素条件时给出一个反例。)
这里 是整数,且 。
解答 · 答案
取 使得 。乘以 得 。假设 ,则右端两项都能被 整除,因此 。若没有互素条件,取 :,但 。
快速检查
( 有整数解吗? 呢?在有解的情况下给出一个解。)
利用第一个例题算出的 gcd。
解答 · 答案
gcd 为 。由于 ,第一条方程没有整数解。由于 ,把 乘以 ,便得到第二条方程的解 ;验算:。