一个整数,两项信息
知道一个数模四的余数,通常不能决定它模五的余数。不过,两个相容的余数要求可共同描述一个较大模数下的剩余类。我们会构造这个类、确定它何时存在,并解释其商环意义。
定义 7.1.1
(同余与剩余类)
以下 是正整数, 是整数。 意味着 ;它描述整个剩余类,而不只是 0 至 的一个数。最小公倍数 取正值。
互素模数的构造
定理 7.1.2
(两个互素模数)
若 ,对任何 ,联立条件
都有解,而且任意两个解模 同余。
证明
(由 Bézout 等式得到两个选择子)
选整数 使 ,令
模 时,,;模 时,,。因此 同时满足两个要求:每个选择子保留一边的余数,消去另一边的余数。
若 都是解,则 都整除 。由互素性可知 :例如写 ,由 和 得 。反过来,加上 的任意倍数不改变两个同余条件。所以所有解恰好构成模 的一个剩余类。
证明透视
互素性用在何处
互素性被使用了两次,各有不同的用途。存在性需要等式 :它把 拆成 的一个倍数与 的一个倍数之和,正是这个拆分使每个选择子在一边 、在另一边 。唯一性需要消去律 ,这是唯一把 用在整除而非线性组合上的地方。真正起作用的想法,是 由两个要求分别构造而成,无需搜索。没有互素性便没有 ,而下一节会说明此时还剩下什么。
的选法不必唯一;不同选法可能给出不同整数 ,但上述唯一性保证它们代表同一个模 的类。
例题 7.1.3
(构造模二十的解)
解 ,。由 ,取 。选择子是 ,,故
验算:18 模 4 余 2,模 5 余 3。所有解是 ,其中 为整数;答案不是单个整数。
模数有公因数时
定理 7.1.4
(任意正模数的相容条件)
令 。联立条件有解,当且仅当 。有解时,所有解构成模 的一个剩余类。
证明
(化为互素的一元线性同余)
若 同时是解, 既整除 也整除 ,因此整除两者之差 ,得到必要性。
反过来,假设 。写 ,,则 。令 ,第二个条件化为
由 Bézout 等式选 使 。取 ,便有 ,所以 满足原来两个条件。此论证也包括 :模一同余自动成立。
若 都是解,它们的差同时被 整除。写成 ,由 得 ;互素性给出 ,故差被 整除。反过来,此最小公倍数的每个倍数都被两个模数整除,因此它正是解类的模数。
例题 7.1.5
(公因数可以允许或阻止解)
对 和 ,最大公因数是 2,且整除 。整数 14 满足两式,故完整答案为 。
相反, 和 无公共解:第一式要求奇数,第二式要求偶数。等价地,余数之差 1 不被 整除。
例题 7.1.6
(一个模数整除另一个(边界情形))
取 和 。这里 整除 ,所以有解。取 ,,则 ,模 的化简同余自动成立。解构成模 的一个类,即 :第二个要求没有增加任何信息,因为 已经成立。
反例模式
乘积不一定是正确的周期
断言:相容联立条件的解构成模 的单个类。对 ,,真正的周期是 ,不是 。14 和 38 都是解,两者相差 24,却不是模 48 同余。若只说 ,便漏掉有效解。模数 恰好在 时才正确。
乘积环的观点
定理 7.1.7
(中国剩余同构)
当 互素时,映射
是环同构。
证明
(检查代表元、运算及双射)
若 ,则两者分别模 同余,所以映射不依赖代表元。模整数化简与加法、乘法及单位元相容,故映射按分量保持这些运算。
核由同时被 整除的代表元所属的类构成。互素性迫使它们被 整除,因此核只有零类,映射为单射。选择子构造为每一对目标剩余类提供整数,故映射为满射。因此它是环同构。
乘积环按分量运算。在模 20 的例子中, 对应 , 对应 。两者之和模 20 是 1,乘积是 0,各自平方不变。它们是商环中的选择子;它们本身不必等于整数 0 或 1。
常见错误
(同构需要互素的模数)
对不互素的模数,同一公式仍定义环同态,但它既不是单射也不是满射。取 ,:映射 把 送到 ,所以核非零( 的倍数给出大小为 2 的核),而像只有 24 个元素。 不可能由任何整数得到,因为第一个分量迫使 为奇数,第二个分量迫使它为偶数。此时不能声称每对剩余类都可达。
练习与解答
快速检查
(解 ,。)
两个模数互素,所以预期得到模 的一个类。
解答 · 答案
19 满足两式;3、5 互素,完整解为 ,亦即 。
快速检查
(解 ,。)
先把余数之差与最大公因数比较。
解答 · 答案
差 4 可被最大公因数 2 整除。14 是解,所有解为 ,。
快速检查
( 和 可以同时成立吗?)
看奇偶性。
解答 · 答案
不可以。余数之差 1 不能被最大公因数 2 整除;两式也要求相反的奇偶性。
快速检查
(验证模 20 的 和 确实是选择子,并用它们重建余数为 、 的类。)
把每个选择子分别模 和模 化简。
解答 · 答案
它们模 的余数对为 ,。而且 ,,,。因此 给出余数 2、3 对应的类。
算术和代数表达相同的结构:选择子构造组合后的类,互素性则使每对分量剩余类恰好对应模乘积的一个类。