同余式保留了部分信息: 表示 属于理想 。当同时施加多条同余式时,是否存在一个元素同时满足全部条件?这个元素又是否唯一?答案取决于各理想之间如何配合。本节借助 MATH2076 笔记中的理想与贝祖(Bézout)工具,推导中国剩余定理,然后把它应用于整数和多项式。我们考虑的是有单位元的交换环;商环可以是零环。
两个理想的重构定理
设 为 的理想。它们的和 是一个理想。
定义 5.1.1
(互素理想)
若 ,则称 的理想 互素(comaximal)。这等价于存在 及 ,使得 。
把和的定义应用于元素 ,就得到这个等价关系:若这个和包含 ,则它包含每个 。用 表示由所有乘积 (其中 、)的有限和组成的理想;总有 。
定理 5.1.2
(两个理想的中国剩余定理)
设 为有单位元的交换环 的互素理想。则对任意 ,都存在 使得 且 ,而任何两个这样的 之差属于 。等价地说,映射
是环同构。此外 。
证明
(用贝祖恒等式挑选原像)
考虑映射
由于两个坐标都保持加法、乘法和单位元,所以这个映射也保持它们。它的核是 :像为 ,当且仅当 同时属于两个理想。若 ,这个映射还是满射。事实上,选取 、 使得 。那么 且 ,而 的表现正好相反。对任何所需的配对 ,令
它模 变成 ,模 变成 。只要有 的贝祖恒等式,这个公式就是一个算法。
核描述了唯一性:任何两个解的差都是 的元素。因此 上的诱导映射是良定义的,因为 的元素在两个坐标中都变成零;由核的计算可知它是单射;由上述构造可知它是满射。
最后一项:设 如上,且 ,则 。由于 且 ,第一项属于 ;由于 且 ,第二项也属于 。因此 ,配合 ,在互素的条件下就有 。
证明透视
互素性用在哪里,而且只用在哪里
互素性恰好在两处进入。映射 、它的核 ,以及由此得出的唯一性,对任意理想都成立,不需要恒等式 。这个恒等式用来构造选择器: 模 为 、模 为 , 则相反,于是 在第一个坐标读作 、在第二个坐标读作 ,两项互不干扰。
最后一段中不显然的一步是 。它把每一项送进必须包含该乘积的理想: 中 、, 中 、。两个加项都属于 ,证明就完成了。乘积公式是由假设推出的结果,并非对任意理想都成立的恒等式。下面的反例表明没有这个假设时哪里出错:唯一性的模是交集而不是乘积,而存在性需要相容条件。
反例模式
互素这个条件不能去掉
断言:对交换环的任意理想 ,都有 ,且每一对余数都能取到。取 、。则 ,但 只含 的倍数,所以 ,即 。至于第二部分,取 、,此时 。这里 ,所以 的像有 个元素,而目标有 个。配对 取不到: 迫使 为偶数,而 迫使 为奇数。补救办法是假设 ;没有它时,结论只对相容的配对成立,见理想不互素时的一节。
例题:整数
例题 5.1.3
(模数互素的两条同余式)
求所有满足以下条件的整数 :
由于 ,理想 与 互素。我们可以选取 及 。于是
是一个解。直接验算得 。其他每个解与 17 的差都是同时被 5 和 7 整除的整数,因此被 35 整除;完整答案是 ,。负的代表元,例如 ,描述的是同一个剩余类。
常见错误
(把两个选择器弄反)
系数 和 是选择器,很容易不小心弄反: 必须模 5 等于 1,因为它乘的是所需的余数 2;而 必须模 7 等于 1,因为它乘的是 3。若角色对调,就会算出 ,它模 是 、模 是 ,两个余数正好互换。
例题:多项式
例题 5.1.4
(有理数域上模互素的多项式)
在 中,求次数低于 3 并满足以下条件的多项式:
两个模互素:。取 及 ,得 。因此
乘积模为 。利用 化简,得到次数低于 3 的代表元 。验算两项要求:它的常数项是 1,而模 时它变成 。所有解都是 ,其中 。多项式除法给出恰好一个次数小于 3 的代表元。
同样的推理适用于域上互素的多项式 :贝祖恒等式给出 ,而乘积模为 。域这个条件保证了多项式除法和贝祖恒等式成立;引用这个证明时不应忽略此条件。
理想不互素时会有什么变化?
命题 5.1.5
(两条同余式的可解性)
设 为 的理想,。同余式 与 有解,当且仅当 。若有解存在,所有解之间的差都属于 。
证明
(把差拆成两部分)
把 与 相加,得 ,这就是必要性。至于充分性,把 写成 ,其中 、,并取 。那么 且 。两个解 满足 且 ,所以 。
因此,互素保证了每一对余数都相容;但即使理想不互素,个别相容的配对仍然可以存在。
例题 5.1.6
(模 4 与模 6 的相容与不相容配对)
条件 与 是相容的:。整数 9 同时满足两者;由于 ,完整的解集是 。相反, 与 不可能同时成立:它们的差 不是偶数,所以不在 之中。
练习及完整解答
练习 5.1.7
(解 、,并写出整数解的完整集合。)
基础
解答(4)
- 1
写出模数的贝祖恒等式
由于 ,一个方便的恒等式是 。取 及 ,则 。
- 2
用选择器组合出解
关键一步
。
依据: 模 为 、模 为 ,而 正好相反。
- 3
化简并验算
,而 、,所以 且 。另一种做法:由 得 ,4 模 9 的逆元是 7,从而 ,同样得到 。
- 4
写出所有解
解之间的差属于 ,所以所有解为 ,。
练习 5.1.8
(在 中,求所有满足 及 的 。)
核心
解答(4)
- 1
检验相容性
所需余数的差为 ,由于 ,它属于 。因此两条同余式相容。
依据: 两个模有公因式 ,所以不互素,须用可解性命题。
- 2
找出一个解
取 。它模 同余于 1,而 ,所以它满足第二条同余式。
- 3
求唯一性理想
关键一步
与 的公倍式必须同时被 和 整除,而两者互素。因此 。
依据: 两个解之差属于交集,而不是乘积。
- 4
写出所有解
练习 5.1.9
(判断 与 是否有公共解;若有,求出全部解。)
核心
解答(4)
- 1
计算和理想
。
依据: 可解性取决于 ,而 由 生成。
- 2
检验相容性
余数之差为 ,所以有解。
- 3
找出一个解
设 。由 得 ,故 ,即 。取 得 ,而 。
- 4
写出所有解
由于 ,所有解为 ,。