从最大公因数到所有可达的值
固定不全为零的整数 。正的最大公因数 同时整除两数。因此每个整数组合 都被 整除。这是方程 有整数解的必要条件:若 ,便无解。值得注意的是,这个基本障碍也是唯一的障碍。
定义 3.5.1
(最大公因数与贝祖证书)
对不全为零的整数 , 是同时整除两者的最大正整数。它的贝祖(Bézout)证书是一对整数 ,满足 。
定理 3.5.2
(贝祖等式与可达的值)
若 不全为零,且 ,则存在整数 使 ,并且
证明
(最小的正组合就是最大公因数)
至少有一个非零;必要时改变符号,即得一个正整数组合。令 是最小的正组合。用 除 得 ,其中 。由于 和 都是 的整数组合, 也是。若 ,便与 的最小性矛盾;故 。同理 。 的每个公因数都整除每个整数组合,特别是 。因此 ,其构造正给出贝祖等式。
至于集合等式,每个组合都被 整除。反过来,若 , 为整数,把 乘以 便得 。
这里把带余除法当作前置知识,而不是暗中容许负余数。约定 保证非零余数会成为更小的正组合。集合等式包含两个方向。它并非说任意组合都等于最大公因数,也没有说贝祖系数唯一。
不只一个解,而是所有解
定理 3.5.3
(整数解的完整解族)
设 不全为零,,且 。设 是 的一组整数解,并令 、。则 ,而所有整数解为
证明
(先代入,再相减)
直接代入可证每一对都有效。反过来,设另一组解为 ,记 、。相减得 。
若 ,则 。由互素及贝祖等式可得 :若 ,两边乘 便把 写成 的倍数之和。令 ;原式给出 ,故消去得 。若 ,则 ,方程迫使 ;任意整数 都可对某个整数 写成 。因此同一公式也涵盖这个零系数情形。证明包含负系数,整除均按整数定义理解。
证明透视
互素性在解族证明中的位置
这个论证只有一个真正的想法:除以 之后, 互素,而正是互素性把 变成 。在此之前都只是整理:两组解相减会消去右边,剩下齐次方程 。贝祖等式在这里第二次出现,这次用于 ,写出 ,把整除性从乘积移到单个因数。最后消去 之所以合法,是因为 ; 的情形不是事后补充的退化例子,而是必须单独处理,因为此时消去不合法。若不先除以 ,论证只能得到 ,无法除掉 ,这就是解族中步长是 而不是 的原因。
若 ,则我们采用的正最大公因数约定不适用。方程变为 :当 时每一对整数都是解;当 时无解。这个情形必须分开处理,不能除以零的最大公因数。
反例模式
步长是系数除以最大公因数,而不是系数本身
命题:若 是 的一组解,则所有解为 、。以 及 检验,后者成立,因为 。数对 也是解:,,而 。但 不是 的倍数,所以命题漏掉了它。正确的步长是 和 :取 得 、。补救办法是先除以最大公因数。
下面的交互图对选定的 a、b、c 作扩展欧几里得(Euclid)算法,列出解族 、 并逐一核对各成员,也显示你输入的数对在解族中的位置。
常见错误
(除同余式后仍保留原来的模)
把 除以公因数 时,模也要一并除去:结果是 ,不是 。除后仍保留模 是错误的;它会排除原同余式中成立的解 (),因为 ,而 。
例题
例题 3.5.4
(从欧几里得到完整解族)
求 的全部整数解,给出贝祖证书并证明列出的解族完整。
反复做除法得
最后的非零余数是 。回代得
因此 ,一组解是 。由于 、,完整解族为
代入时参数项互相抵消;上面的定理证明没有其他解。
例题 3.5.5
(无解的方程与可解的同余式)
说明为何 没有整数解,然后求满足 的全部整数。
,因为 、、。每个 都被六整除,而七不是;因此方程不可能成立。
同余式表示 ,等价于对某个整数 有 。此处可以用公因数六除同余式,得到 。由于 且 ,乘以三得 。反过来,若 ,则 被 整除。因此所有解为 ,。
例题 3.5.6
(系数为零的情形)
求 的全部整数解。这里 、,所以 ,它整除 。一组解是 。取 、,解族为 、。所以每个解都有 ,而 任意。直接看, 迫使 ,对 没有任何条件,公式与此一致。若对 使用未约简的步长 ,会把 限制为 的倍数,漏掉解 ,因为 。
练习
快速检查
( 有整数解吗?)
先计算系数的最大公因数。
解答 · 答案
,而 。每个值 都是 的倍数,所以没有整数解。
快速检查
(求 的全部整数解。)
先找 的贝祖证书,再按比例放大。
解答 · 答案
,乘以 得 ,故 。取 、,解为 、,。以 检验:、,而 。
快速检查
(求所有满足 的整数 。)
把同余式写成对某个整数 有 。
解答 · 答案
把 除以 得 ,所以 。解为 ;例如 时 。相除之后,模由 变成 。