动机
剩余恰好记录了一个整数在除以固定模数之后所能看到的那一部分信息。使用剩余可以缩短计算,但它会改变消去律的规则。方程 是有解的,尽管 在模 下没有逆元。理解这个例子,可以引出一般的可解性定理,进而引出由若干个余数重构整数的方法。
定义
定义 2.1.1
(同余与单位)
固定整数 。关系 表示 。剩余类 是所有与 同余的整数构成的集合。剩余类的加法与乘法由整数的运算诱导而来。单位是具有乘法逆元的剩余类; 是单位,当且仅当 。
这些运算是良定义的,因为把 换成 时,它们的和与积只改变 的倍数。逆元判据来自贝祖(Bézout)定理:由 得 ;反之,逆元等式说明对某些整数 有 。同余是一个等价关系,因此由 代表的这 个剩余类构成整数集的一个划分。
定理/命题
定理 2.1.2
(线性同余定理)
设 。同余式 有解,当且仅当 。若有解,则模 恰有 个不同的解。若 是一个解,则所有解为 ,其中 。
定理 2.1.3
(中国剩余定理与相容性)
对于两两互素的整数 ,任一方程组 模 恰有一个解类。对于任意两个模数 ,余数为 的方程组有解,当且仅当 ;有解时,解模 唯一。
证明思路
证明
(贝祖定理,然后约化模数)
线性同余式就是整数方程 ,因此可由贝祖定理证明可解性判据。除以 之后,系数 在模 下可逆。于是模 有唯一的解类,而它在模 下恰好分裂为 个类。所列出的两个代表元相差 ;它能被 整除,当且仅当 ,这就证明了这些解两两不同。
证明
(互素模数的选择子;两个模数的代入)
对于互素情形的定理,令 ,并选取 使 。则 具有每一个指定的余数:除第 项以外,所有加项在模 下都为零。两个解之差是能被每个 整除的整数,因而(利用两两互素与素因数分解)能被 整除。
对于两个一般的模数,令 。第二个方程变为 ,它有解恰好当所述的最大公约数条件成立。任意两个解之差同时被 整除,这恰好等价于被它们的最小公倍数整除。这也以正确的模数证明了唯一性。
证明透视
两两互素用在哪里
互素情形的证明把这个假设用了两次,目的各不相同。存在性需要每个 在模 下是单位;由于 与其他任何 没有公共素因子,。于是选择子 在模 下为 ,在其他每个模数下为 ,而解不过是组合 。唯一性需要由“被每个 整除”推到“被 整除”,这同样恰好是两两互素。
对模数 和 ,两步都明显失效: 满足 ,所以模 的选择子不存在;而 同时被 和 整除,却不被 整除。两个模数的论证把它归结为第一个定理,一并修补这两点。代入 得 ,这是 的线性同余式。它的可解性判据正是相容条件,而它的解 组成模 的一个类,所以 在模 下唯一确定。
例题详解
例题 2.1.4
(非单位系数)
对于 , 整除 。把整个整除关系式除以 ,得 ,因而 。模 的三个解为 。若在除以 的同时保持模数为 ,就会改变原来的问题。
例题 2.1.5
(由互素的余数重构整数)
解 ,,。取 ,用 ,相应的逆元分别为 。该构造给出 。确实, 具有所要求的三个余数。
例题 2.1.6
(先判断相容性,再做重构)
方程组 , 是相容的,因为 。代入 得 ,故 ,从而 。若把第二个余数改为 ,方程组就不可能有解:一个方程要求整数为奇数,另一个要求为偶数。
同余保持运算,但不保持所有推理
同余允许我们把整数换成更简单的代表元,因为加法与乘法都尊重这个等价关系。减法也包括在内,因为负数与同余相容。除法则不同:只有当除数有逆元,或者对模数作出调整以补偿丢失的信息时,这种运算才可能是良定义的。这一区别解释了为什么模运算在一长串计算中可以与普通算术相似,却会在某个看似无害的消去步骤上失效。
为了直接推导调整后的规则,设某个乘积之差能被模数整除。把系数与模数同时除以它们的最大公约数。此时约化后的系数与约化后的模数互素,因此贝祖定理允许在这里作消去。结论是一个以约化后的模数为模的同余式。所以消去并不神秘:它只是普通的整除性加上一个仔细表述的互素事实。模数的缩小恰好记录了非单位系数所带来的不确定性。
反例模式
消去非单位会丢失信息
错误的论断是:每个非零系数都可以在保持模数不变的情况下被消去。模六时,把剩余一与四分别乘以二,得到相同的剩余,尽管原来的两个剩余并不相同。修正后的表述只消去单位,或者把模数除以它与系数的最大公约数。当模数是合数时,非零是比可逆更弱的条件。
因此,线性同余式的最大公约数条件起着两种不同的作用。它决定目标是否落在“乘以该系数”这一映射的像中,同时也计数有多少个源剩余类共享这个像。一个像类恰好被齐次方程的解的个数那么多个元素所达到。把一个解平移一个齐次解,目标保持不变;而任意两个解相减,得到一个齐次解。这从概念上解释了为什么每个可解的目标都有相同数目的原像。
既数像,也数解
可达到的目标类的个数等于模数除以最大公约数。事实上,可达到的目标必须被该最大公约数整除,而可解性定理说明每个这样的目标都能被达到。每个可达到的目标恰有等于该最大公约数的个数的原像。把像的大小乘以这个共同的纤维大小,就恢复了源剩余类的总数。这为定理中的解数提供了一个有用的独立检验。
例如,模十五时乘以六,恰好能达到由零、三、六、九、十二所代表的五个类。每个类有三个原像。于是十五个源剩余类被划分成五个大小相等的纤维。要求这个映射的逆是不可能的:三个不同的输入给出同一个输出。把模数约化为五、系数约化为二之后,这个映射就成为双射,而这正是第一个例题的计算所用到的。
重构项起着选择器的作用
在计算任何目标余数之前,就可以理解中国剩余定理的构造。对每个模数,构造一个数,它模该模数为一,模所有其他模数为零。这样的数选出剩余元组的一个坐标。把它乘以所需的坐标值,再把所有这些贡献相加,就得到所要求的整数。该构造对剩余数据是线性的,所以同样的选择器项可以在模数相同的许多不同方程组中重复使用。
这一观点也解释了唯一性。如果一个整数的所有坐标都为零,它就能被每个模数整除。两两互素则使它能被这些模数的乘积整除。因此,映到零元组的类只有模乘积的零类。存在性为每个元组构造出一个类;唯一性说明不同的类不可能代表同一个元组。两者合起来描述了一个精确的对应,而不仅仅是一个碰巧产生解的做法。
概念视角结构
把一个剩余看作局部剩余的元组
对于两两互素的模数,约化把模乘积的剩余映为它模各因子的剩余所组成的元组。该映射逐坐标地保持加法与乘法。中国剩余定理证明这个映射是双射。因此,一个很大的模计算可以在较小的模数下分别进行,之后再重构,没有任何近似。
一个推论是,对互素的模数,单位的个数可以分解。一个整数与若干互素因子之积互素,当且仅当它与每个因子都互素。在剩余元组的对应之下,单位因此恰好就是由单位组成的元组。数这些元组,便得到欧拉(Euler)函数在互素情形下的积性。这把一个重构定理与一个起初看上去只是计数定义的算术函数联系了起来。
相容性是共享的信息,而不是技术上的麻烦
当两个模数有公约数时,两个同余式都已经规定了模该公约数的余数。这些规定必须一致。这不需要任何代数运算,就证明了相容性条件的必要性。线性同余式的约化随后证明其逆命题:对于两个模数,在共享信息上一致就已足够。最小公倍数是正确的唯一性模数,因为它综合了任一模数所要求的全部素数幂,而不会把重叠的要求重复计算两次。
为了具体看清这一区别,取一个模数整除另一个模数的情形。模较大模数的剩余已经确定了它模较小模数的剩余。较小的同余式要么与之一致而不提供新的信息,要么与之矛盾而使方程组不相容。在这种情形下把两个模数相乘,会引入人为多出的类。最小公倍数则恰好保留较大的模数,正如信息解释所预言的那样。
对于若干个并非两两互素的模数,可以每次合并两个同余式。一次合并成功之后,记下所得的余数和最小公倍数模数,再用两个模数的定理合并下一个条件。在每一阶段,所记录的同余式恰好代表迄今已处理的所有条件的解。若相容性失败,原方程组无解。这个过程不需要任何没有依据的乘积公式,并且能自然地处理多余的条件。
是的:方程组有解,当且仅当其中任意两个同余式都相容。
自然的下一个问题
对多个模数,两两相容是否足够?
是的:方程组有解,当且仅当其中任意两个同余式都相容。
必要性就是两个模数的情形。至于充分性,把每个条件 拆成各个素数幂部分。对固定的素数 ,保留一个来自 、指数最大的模 条件。任何其他来自 的模 部分满足 ,因此已经被推出。保留下来的条件涉及互不相同的素数,由互素情形的定理求解。
检验重构得到的答案
一个完整的解答应当包含一个代表元及其唯一性模数。把代表元代入每一个原始同余式。这验证了构造在算术化简之后依然成立。然后,通过考察两个解之差来论证模数。仅有代入检验并不能说明完备性;许多单独的整数都可能满足该方程组。反过来,只有正确的唯一性模数而没有代表元,也不能确立存在性。定理同时提供这两者,书面的解答应当让它们各自的作用清晰可见。
非线性的计算也可以分解为各个坐标
剩余对应保持乘法,所以它也可以用来整理多项式方程。例如,求解模两个不同奇素数之积时平方等于一的方程,相当于在每个素数模数下求解同一个方程。在每个域中恰有两种选择,一和负一:把平方差分解因式并利用没有零因子,即可证明这一点。中国剩余定理把每一对选择结合成模乘积的恰好一个剩余。于是,尽管这个多项式的次数是二,模该乘积却有四个根。域上根的个数上界只在每个素数坐标中使用,在那里它的假设成立。这个例子既显示了重构的威力,也显示了把域上的定理原封不动地搬到合数模数上的危险。它还区分了计数解与列出解:四种坐标选择确立了解的个数,而重构公式则计算出它们的实际代表元。
常见错误
常见错误
(消去不是单位的系数)
由 ,只有当 是单位时,才可以消去 并保持模数 不变。一般情况下,有效的结论是 。例如 ,但 。
常见错误
(乘积模数需要两两互素)
中国剩余定理中的乘积模数同样要求两两互素。对于模数 ,自然的唯一性模数是 ,而不是 :一个模 的解类在模 下分为两个类。要说明你的答案是一个整数代表元,还是整个剩余类。
常见错误
(二次同余式可以有多于两个根)
“二次多项式至多有两个根”是关于域的定理,所以它适用于素数模,却不适用于合数模。模 时,剩余 的平方都是 :例如 ,。应在每个素数坐标上使用根的个数上界,再用中国剩余定理组合。
总结
最大公约数控制着同余式中的除法。互素的模数允许任意的局部剩余;有重叠的模数则施加相容性条件。重构公式提供存在性,而差的整除性给出唯一性。
练习
快速检查
(求同余式 14x 同余于 8(模 30)的所有解。)
把系数与模数一起约化。
解答 · 答案
最大公约数为 ,故两边除以 得 。由于 ,得 。因此 ;直接相乘可知两种情形的余数都是 。
快速检查
(解 同余于 2(模 9)且 同余于 5(模 12),或证明无解。)
在代入之前先检查最大公约数。
解答 · 答案
由于 整除 ,写 。则 ,即 ,故 。因此 。它的余数是 和 ,且唯一性模数是最小公倍数 。
快速检查
(求所有满足 的模 剩余 。)
先分别在模 和模 下求解,再组合。
解答 · 答案
由于 与 是素数, 在素数模下迫使其中一个因子为零,所以 在每个坐标上都迫使 。中国剩余定理把四种符号选择组合成模 的四个类:、、、。验算:,。答案是 。