动机
一个同余式只记录一个剩余类,但把多个同余式合并起来并不总是可行。当模数有公因子时,两个给定的余数可能在两个模数都保留的信息上互相矛盾。即使解存在,把各模数相乘也可能高估真正的周期。
正确的不变量是完整解类:处理了若干约束之后,每一个解且只有解与某个代表元模某个正周期同余。扩展欧几里得(Euclid)算法提供相容性检验,并给出合并下一个条件所需的修正量。另有一个素数幂的论证说明,对有限方程组而言,检查所有两两组合也是充分的。
这里的数学是在精确整数上进行的;证明与算法都不依赖于猜测一小段候选解的范围。
定义
定义 4.2.1
(同余与完整解类)
对正整数 ,当 整除 时记 。这一关系与加法和乘法相容。模一不施加任何限制,因为任何整数差都能被一整除。
完整解类 (其中 )恰好指整数 ()。其规范代表元满足 。线性同余式是 ,其中 可以是负数或零。
的最大公约数指它们绝对值的正的最大公约数。正整数 的最小公倍数是它们最小的正公倍数,等于 。我们使用整数算法笔记中已经证明的裴蜀(Bézout)等式及由系数给出的逆元。空族的最小公倍数约定为一,与空方程组没有任何限制相符。无需调用模一的逆元:对模一的余数要求只有一个不受限制的类。
定义 4.2.2
(有限余数方程组的两两相容)
有限族 (每个 )称为两两相容,当且仅当对每一对下标都有
两两互素会使这些条件自动成立,但相容并不要求模数互素。
定理/命题
定理 4.2.3
(单个线性同余式的全部解)
设 。同余式 有解当且仅当 整除 。若有解,其整数解构成模 的一个类,因此恰好构成模 的 个不同的类。
当 时,代表元可由 乘以 模 的逆元得到。当 时,每个整数都是解,取代表元零即可。
定理 4.2.4
(任意两个正模数的构造性合并)
方程组 , 有解当且仅当 整除 。若有解,则其解类在模 下唯一。
记 。若 ,利用系数的逆元选取满足 的 。若 ,取 。则 模 约化后是一个规范的解代表元。该过程需要最大公约数和裴蜀系数,而不需要对模数做因数分解。
定理 4.2.5
(两两相容对每个有限方程组都是充分的)
对正模数而言,有限余数方程组有解当且仅当它两两相容。有解时,其完整解集是模所有模数的最小公倍数的一个类。逐次应用两模数合并法即可构造出该类,或正确地拒绝不相容的方程组。
这里的唯一性是指模最小公倍数的剩余类唯一,并不意味着只有一个整数解;当模数含有公因子时,也不意味着模乘积唯一。
证明思路或证明
证明
(解单个线性同余式)
若 能被 整除,则 的每个公因子都整除 ,这就证明了线性同余式的必要性。当 时,两边同除即得等价的同余式 。约化后的系数与模数互素,故当模数大于一时由裴蜀等式逆元存在。相乘得到模 的唯一一个类;反之,该类乘以 后满足原方程。
若约化后的模数为一,则除后的同余式不施加条件,所有整数都是解。无论哪种情形,都可把解类写成 。在 个连续剩余构成的完整区间内,它恰好有 个不同的值,即加上零到 个 所得的值。这些值之间的差不是 的倍数,除非所加的个数相同。这就证明了解的个数,包括 的情形。
证明
(合并两个同余式与逐次求解)
对于两模数合并,第一个条件的每个解都具有形式 。第二个条件变为 。由线性同余定理,它恰在所述的最大公约数条件下有解。同除以 得到关于 的方程,其中 互素。它模 的唯一类转化为 模 的一个类。这同时证明了全部解的唯一性,而不仅仅是所构造代表元的正确性。
对于逐次算法,从模一的代表元零开始。保持已处理的约束恰好具有当前的解类这一不变式。由定理,将其与下一个同余式合并恰好得到它们的交集;合并失败意味着该交集为空。因此归纳法证明了接受与拒绝两方面的正确性。若旧代表元已规范化,且修正量满足 ,则 已经成立;显式的最终约化同样可处理未规范化的输入余数。
证明透视
合并不变式包含每一个可能的解
检验新代表元的余数只能确立可行性。代换 以及唯一的系数逆元类还证明了没有丢失任何其他解类。保持这一反向方向,才使得之后合并失败时能证明整体不相容,而不只是所选的某个候选失败。
证明
(以素数幂证明两两相容的充分性)
对于两两判据,必要性成立,因为一个公共解使每个差 都能被两个模数的最大公约数整除。我们利用素数幂因子证明充分性。素数是至少为二且正因数只有一和自身的整数。这里的素因子都取正数。所需的因数分解事实是初等的:存在性可由归纳法得到,把任何合数拆成更小的因子;唯一性由素因子引理得到。该引理由裴蜀等式推出:若素数整除一个乘积却不整除其第一个因子,则它与该因子的最大公约数为一,于是把裴蜀等式乘以第二个因子即知它整除第二个因子。重复此论证可在任意两个相互竞争的分解中找出另一侧对应的素数,然后约去即证唯一性。整数一的分解为空。
设 为最小公倍数。对每个在各模数中以最大指数出现的素数幂 ,选取达到该指数的一个下标,并规定相应的模 的余数。这些素数幂两两互素,故反复使用已证的合并法,可得到模它们乘积 的一个类。
对任一原模数及其每个素数幂 ,它与所选最大指数下标的相容性使其余数与所选余数模 一致。因此构造出的整数满足该原模数的每个素数幂因子,从而满足它们互素的乘积。它满足所有原同余式。若 ,则所有模数均为一,每个整数都成立,结论一致。
最后,两个公共解之差是每个模数的倍数,从而是每个最大素数幂及其乘积 的倍数。反之,加上 的任意倍数不改变所有同余式。这就证明了完整解类和有限方程组定理。素因数分解解释了该判据,但逐次实现并不需要它。
例题详解
例题 4.2.6
(不可逆的系数仍可能有解)
解 。最大公约数为二,且整除八。两边同除得 。由于三是七模十的逆元,。因此模二十的两个类是二和十二。代入后两种情形的余数都是八。试图求十四模二十的逆元会失败,但这并不能证明原同余式无解。
例题 4.2.7
(公因子使周期缩短)
解 与 。它们的最大公约数是三,余数之差是三,故相容。代入 得 ,因此 。完整解为 。相反,若把五换成四,则余数之差为二,不能被三整除,因而无解。
例题 4.2.8
(第三个条件改变周期,却不改变最小代表元)
在这个相容的一对上加入 。把 与它合并。最大公约数是二,差为负十;约化后的修正方程是 ,其解类为零。因此代表元仍为十四,周期变为九十。
三个原模数的乘积是 ,并不是真正的周期。模该乘积有六个解,即 ()。仅有一个正确的代表元并不足以断言模 唯一。
算法规模与因数分解的作用
先把每个输入余数按其正模数规范化。每次合并时,周期是一个最小公倍数,且至多等于已处理模数的乘积。因此其二进制长度至多是这些模数二进制长度之和,至多相差一个常数。修正余数也可取在其约化模数之内,使所构造的代表元落在新周期之内。
扩展欧几里得算法与精确算术因此作用于位长受多项式控制的数。逐次相容性求解器不需要枚举直到周期的整数,而大周期的数值大小并不等于其书写的输入长度。两两充分性的因数分解证明不应被误认为在应用基于最大公约数的算法之前必须对每个输入做因数分解。
概念视角代数
相容性比较的是两个模数共同保留的信息
共有的素数幂对未知余数的同一部分约束了两次。两个规定必须在它们共同的分辨率上一致。最小公倍数把每个所需的素数指数只保留一次,这解释了最终的周期。最大公约数能检测重叠,而无需计算其素因子。
常见错误
常见错误
(只除系数而不除模数)
不能由 推到 。后者只有一个类 ,因为 是 模 的逆元;它丢失了解 :,但 。在已证的条件 之下,应把系数、右端与模数一起除以 ,得到 ,从而得到模 的两个类 与 。
常见错误
(模数之积不是周期)
对 与 ,解为 ,所以 与 都是解,虽然它们模 不同。互素情形的周期 只在 时正确;一般情形的周期是 。
常见错误
(相容不等于互素)
模数 与 有公因子 ,但同一方程组有解,因为 。互素的模数使每一对都相容,但反过来不成立;因此只要 就拒绝方程组,会丢掉有解的方程组。在模一的分支中,约束本已是空约束,不应在那里选取模逆元。
反例模式
没有逆元不等于没有解
同余式 的系数在模四下没有逆元,但它的解是全部奇数。除以最大公约数得 。逆元检验失败只说明乘法不是四个剩余类上的双射,并不说明其像集不包含所要求的右端。
总结
最大公约数刻画了单个线性同余式的可解性,并给出所有剩余解的个数。同一定理给出非互素余数的精确合并,保持已处理的完整解类。素数幂相容性证明了所有两两一致性检验已经足够,而实际的逐次算法只用最大公约数和逆元,并返回以最小公倍数为周期的结果。
练习
快速检查
(对正整数 ,分类 的解。包括 的情形,并在有解时数出模 的类的个数。)
应用最大公约数条件,而不要虚构零的逆元。
解答 · 答案
此时 。可解性意味着 。若成立,则每个整数都是解,即模一的单个类,也即模 的恰好 个类。若不成立,则无解。当 时,每个 都能被它整除,每个整数都是解。定理中约化后的模数为一,故直接适用其显式的空约束分支,无需任何求逆计算。
快速检查
(解 且 。模乘积 有多少个解类?)
先给出最小周期的完整解类。
解答 · 答案
记 。第二个条件给出 ,从而 。于是 ,。模乘积的两个类是九和二十一。两者都满足两个原约束,它们共同的十二步周期正是四与六的最小公倍数。
快速检查
(解 、、。检查两两相容性并验证一个规范代表元。)
合并两次,并给出最终的最小公倍数。
解答
两两的最大公约数是四、二、六,对应的余数之差为四、十、六,均按要求可被整除。先合并模八余三与模十二余七:代入 得 ,故 。
现令 。最后一个同余式给出 ,从而 ,。因此 。它模八、十二、十八的余数分别是三、七、十三。周期七十二是它们的最小公倍数,而六十七落在其规范区间内。