带余除法与贝祖(Bézout)等式(3.2 与 3.5 单元)用整除描述整数。同余把这些信息重新整理,使有关余数的问题可以用普通代数解决。本单元说明模 同余与加法、乘法相容,准确判断一个剩余类何时可逆,完整求解每个线性同余式 ,并证明两个经典结果:中国剩余定理和费马(Fermat)小定理。全文中 表示正整数。
同余是等价关系
定义 3.6.1
(模 n 同余)
对整数 ,若 ,记 。等价地, 与 除以 的余数相同。等价类称为剩余类 。
命题 3.6.2
(同余与加法、乘法相容)
模 同余是 上的等价关系;并且若 且 ,则 且 。
证明
(把差明确写出来)
自反性、对称性、传递性分别来自:; 蕴含 ; 且 蕴含 。对运算,写 、。则 ,而 。
上述结果说明剩余类的加法与乘法是良定义的。因此任何整系数多项式表达式,都可以先把每一项化为模 的余数再计算。
常见错误
(消去不可逆的因子)
消去律不一定成立。由 ,只有在 时才能推出 ;一般只能得到 。例如 (因为 ),但 ;这里 ,正确的结论是 。
逆元与消去
定义 3.6.3
(模 n 可逆)
若存在整数 使 ,称整数 模 可逆。
定理 3.6.4
(与 n 互素的剩余类恰好可逆)
整数 模 可逆当且仅当 。若 都是逆元,则 。若 且 ,则 。
证明
(贝祖等式给出逆元)
若 ,则对某个 有 ,所以 与 的任何公因数都整除 。反过来,若 ,贝祖等式给出整数 使 ,因此 。唯一性:。消去律只需把 乘以 的逆元。
证明是构造性的:扩展欧几里得(Euclid)算法能给出 。
线性同余式
定理 3.6.5
(求解线性同余式)
设 。同余式 有解当且仅当 。若 ,写 、、。则解恰为满足 的整数,其中 是 的任一解;模 时恰有 个解类:。
证明
(化为互素的同余式)
若 是解,则 ,所以 被 整除。反过来设 。把 除以 可知 等价于 。此时 ,因为若有公因数 ,则 是 与 的公因数且大于 。由逆元定理, 有模 的逆元 ,而 当且仅当 。与 模 同余的整数,在模 下恰分成 个类。
常见错误
(算错解的个数)
可解的线性同余式在模 下有 个解类,不是一个。只有 时才恰有一个。
中国剩余定理
定理 3.6.6
(两个模数的中国剩余定理)
设 为正整数且 , 为整数。则方程组
有解,而且任何两个解模 同余。
证明
(由贝祖等式构造解)
贝祖等式给出 。令 。由于 且 ,得 ;对称地 。若 与 是两个解,则 且 。记 。则 而 ,所以 (由贝祖等式, 被 整除),因此 。
没有互素性,论证的两半都会失败;下面的错误说明,连解的存在性也可能不成立。
常见错误
(模数不互素时使用中国剩余定理)
方程组可能无解: 与 互相矛盾,因为前者迫使 为奇数,后者迫使 为偶数。
费马小定理
定理 3.6.7
(费马小定理)
若 是素数且 ,则 。因此对每个整数 都有 。
证明
(乘以 a 会置换非零余数)
考虑 个整数 。其中没有一个被 整除,因为对 有 。它们模 两两不同余:若 ,消去 (由逆元定理)得 ,故 。因此它们的余数恰好是 的某个排列,从而
与 互素,因为每个因子都是,故消去它得 。若 ,则 与 都 。
证明透视
为何非零余数的乘积可以消去
关键一步是用两种方式计算同一个乘积 :一次直接计算,一次把每个因子都乘以 之后计算,而后者只是重新排列了余数。重排的断言有两半:倍数 仍在非零余数之中,因为 是素数,既不整除 也不整除 ;它们两两不同,因为 可逆。 是素数用来使 全部可逆;合数模数会有不可逆的余数,论证便到此为止。最后消去 也是同一原因。结尾关于 的一句是独立的,因为置换需要假设 。
模数是素数这个假设不能随便去掉。
反例模式
费马小定理需要素数模
命题:若 ,则对每个 都有 。取 、,两者互素。则 ,所以 ,不是 。上面的证明在“使 全部可逆”一步失效: 和 模 不可逆。对合数 ,指数 一般并不适用。
常见错误
(对错误的数约简指数)
的指数可以模 约简(当 时),而不是模 。
例题
例题 3.6.8
(有多个解的线性同余式)
解 。这里 整除 ,故有解。除以 :。由于 , 的逆元是 ,所以 。模 的解是 。验算:,,。
例题 3.6.9
(用欧几里得算法求逆元)
求 模 的逆元。欧几里得算法:,,。回代:。故 ,逆元是 。验算:。除以 的余数落在 内; 与 模 同余,但只有 是标准代表。
例题 3.6.10
(中国剩余定理)
解 、。贝祖等式:,故 、。则 。验算:,。解为 。
例题 3.6.11
(用费马小定理计算幂)
计算 。由费马小定理,。由于 ,得 。
练习
快速检查
(解 。)
除以 ,模也要一并约简。
解答 · 引导解答
整除 。除以 得 ,其解为 (因 )。模 的解是 和 。验算:,。
快速检查
(证明 无解。)
比较 与右边的数。
解答 · 引导解答
不整除 ,由线性同余式定理知无解。直接看, 会给出 被 整除,这不成立。
快速检查
(求 模 的逆元。)
对 和 做欧几里得算法并回代。
解答 · 引导解答
欧几里得算法:,,。则 。所以 ,逆元是 。验算:。
快速检查
(解 、。)
找 使 ,再用 。
解答 · 引导解答
这里 、、、。贝祖等式:,故 ( 的系数)、( 的系数)。则 。解为 。验算:,。
快速检查
(求 除以 的余数。)
用 的费马小定理。
解答 · 引导解答
,所以 (这就是 的费马小定理)。因此 ,余数是 。