动机
把模 7 的所有非零剩余类相乘,得到 6!=720,而 720=7⋅102+6。因此余数为 6,它与 −1 属于同一个剩余类。模 13 时也有类似结果:12!=479001600=13⋅36846276+12。但是模 9 时,8!=40320=9⋅4480 的余数为 0。
本节解释这些结果。关键是一个结构性观察:在每个元素都有逆元的乘法系统中,可以将所有元素配成逆元对,每对的乘积都是 1。只有自身等于逆元的元素会留下。因此问题化为寻找方程 x2=1 的解。解是否只有 ±1 取决于模 n 的算术能否使用消去性质;这正是素数与合数出现差别的地方。
以下 n≥2 为整数。模 n 运算在交换环 Z/nZ 中进行,但它未必是域。记 a≡b(modn) 表示二者的剩余类相等。称一个整数的剩余数为 6 等具体数字时,指的是其最小非负剩余数:满足 0≤r≤n−1 且 r≡a(modn) 的唯一整数 r。所以 720 是整数,6 是它模 7 的最小非负剩余数,而 −1 表示相同的剩余类。这些对象各不相同,不应混淆。
定义
剩余类 a∈Z/nZ 称为可逆元,如果存在 b 使 ab≡1(modn)。这样的 b 称为 a 的逆元。所有可逆元在乘法下构成的集合记为 (Z/nZ)× 或 U(n);它是有限阿贝尔(Abel)群。a 是可逆元当且仅当 gcd(a,n)=1。
逆元唯一。如果 ab≡1 且 ab′≡1,那么 b≡b(ab′)≡(ba)b′≡b′。正因为唯一,“把每个元素与其逆元配对”才有确定含义。
若可逆元 a 满足 a2≡1(modn),称它自身为逆元。若非零剩余类 a 存在某个非零剩余类 c 使 ac≡0(modn),则称 a 为零因子。
若 p 是素数,Z/pZ 没有零因子。这由欧几里得(Euclid)引理得到:若 p∣xy,则 p∣x 或 p∣y。此外,模 p 的每个非零剩余类都是可逆元:对 gcd(a,p)=1 应用贝祖(Bézout)等式即可。相比之下,模 8 有 2⋅4≡0,因此 2 和 4 都是零因子。
一般配对原理
设 G 是以乘法记号表示的有限阿贝尔群,则 G 的所有元素之积等于其中所有自身为逆元的元素之积。
映射 g↦g−1 是 G 到自身的双射,而且再次应用它会回到原元素。因此 G 分成互不相交的集合 {g,g−1}。若 g=g−1,该集合有两个元素;若 g2=1,则只有一个元素。
由于 G 是阿贝尔群,整个乘积可以任意调整顺序。因此我们按这些集合分组。每个双元素集合贡献 g⋅g−1=1,每个单元素集合贡献其唯一的自身为逆元的元素。于是全部元素的乘积等于所有自身为逆元的元素之积。
这里本质上用到了交换律:没有交换律,就不能随意重新排列因子。
将此原理用于 G=U(n),计算 a∈U(n)∏a 就归结为了解 x2≡1(modn) 的解。原理本身并不说明解有多少个;这取决于 n 的算术性质。
设 p 是素数。x2≡1(modp) 的解恰好是 x≡1 和 x≡−1。当 p=2 时两者相同,因此只有一个解;当 p 为奇素数时两者不同,因此恰有两个解。
若 x2≡1,则 (x−1)(x+1)≡0(modp)。由于 Z/pZ 没有零因子,必有一个因子为零,即 x≡1 或 x≡−1。这两个值确实都满足方程。
比较两个根:1≡−1(modp) 当且仅当 p∣2,即 p=2。因此 p=2 时唯一的根是 1;p 为奇数时,根 1 和 p−1 不同。
威尔逊定理
对整数 n≥2,
n 是素数⟺(n−1)!≡−1(modn).
设 n=p 是素数。此时 U(p)={1,2,…,p−1},故 (p−1)! 就是 U(p) 所有元素的乘积。
根据配对原理,该乘积等于所有自身为逆元的元素之积;这些元素正是 x2≡1 的根。
- 若 p 为奇数,根为 1 和 −1,其乘积为 −1,所以 (p−1)!≡−1。
- 若 p=2,唯一的根为 1。此时 (p−1)!=1!=1,而 1≡−1(mod2)。
两种情况下都有 (p−1)!≡−1(modp)。
设 n 为合数,故有因子 d 满足 1<d<n。因为 d≤n−1,整数 d 是 (n−1)! 的一个因子,所以 d∣(n−1)!。
反设 (n−1)!≡−1(modn)。由 d∣n,模 n 同余蕴含模 d 同余,故 (n−1)!≡−1(modd)。但同时 (n−1)!≡0(modd),于是 0≡−1(modd),即 d∣1。这与 d>1 矛盾。
证明透视
威尔逊定理两个方向各自用了什么
两个方向依赖不同的事实。正向把素数性用了两次。第一,每个剩余 1,…,p−1 都是可逆元,所以 (p−1)! 恰好是 U(p) 所有元素的乘积,配对原理才适用。第二,没有零因子,自逆元便只有 1 和 −1,剩下的乘积是 1⋅(−1)=−1;当 p=2 时,唯一剩下的 1 恰好等于 −1。缺少任何一个事实,结论都会改变。对 n=15,四个可逆元 1,4,11,14 都是自逆元,所有可逆元之积为 1,正如例题所算。此外 14! 还含有不可逆元 3,5,6,9,10,12,事实上 14!≡0(mod15)。
逆向完全不用群论。它唯一的一步是:n 的真因子 d 是 (n−1)! 的一个因子;把假设的同余式化为模 d,便得 0≡−1。换言之,当 n 是合数时,阶乘与 n 有公因子 d,所以它模 n 不可逆,而 −1 可逆。这解释了为什么逆向一行便可完成,也解释了为什么下一个定理能准确求出合数情形的剩余。
逆向证明只需要一个真因子,并未用到单位群。事实上还可以得到更精确的结论。
若 n>4 是合数,则 (n−1)!≡0(modn)。若 n=4,则 (n−1)!=6≡2(mod4)。
n=4 时直接计算:3!=6=4+2。
现设 n>4 是合数。令 q 是它的最小素因子,写作 n=q⋅r,其中 r=n/q。则 r≥q≥2。
情形一:r=q。 此时 q<r,且二者都严格介于 1 和 n 之间。它们是 {1,…,n−1} 中不同的整数,因此作为两个不同因子出现在 (n−1)! 中。所以 qr=n 整除 (n−1)!。
情形二:r=q,即 n=q2。 不能将 q 使用两次,因为它在 1,…,n−1 中只出现一次。由于 n>4,有 q≥3,所以 2q<q⋅q=n。因此 q 和 2q 是 {1,…,n−1} 中不同的整数。它们的乘积 2q2=2n 整除 (n−1)!,因而 n∣(n−1)!。
n=4 恰是此论证失效的情形:q=2 时 2q=4=n,不再小于 n。
证明透视
为什么素数平方需要第二个倍数
目标是把 n 或 n 的某个倍数写成 1,…,n−1 中若干个不同整数的乘积,因为每个这样的整数在 (n−1)! 中只出现一次。当 n=qr 且 q=r 时,这两个因子本身已经做到。取 q 为最小素因子只是把它们排好次序,q≤r,于是 r=q 已经意味着 q<r。真正的困难是素数平方 n=q2,这时因子 q 只能用一次。证明以 2q 代替第二个 q。它是另一个小于 n 的因子,当且仅当 2q<q2,即 q≥3;而乘积 q⋅2q=2n 是 n 的倍数。
假设 n>4 只在这里用到:形如 q2 且 q=2 的合数只有 4。这个界限是精确的,因为 3!=6≡2(mod4)。相比之下,8=2⋅4 不是平方数,属于第一种情形,用到的是两个不同因子 2 和 4。
因此对每个 n≥2,(n−1)! 模 n 的剩余类:n 为素数时是 −1,n=4 时是 2,其余情况为 0。
一个刻画,而非高效算法
威尔逊定理给出准确的素性判据,但并非高效算法。算术复杂度用位运算计量,作为输入长度 k≈log2n 的函数。直接计算 (n−1)!modn 需要约 n−2 次乘法。每步对 n 取模后,用学校算法做一次 k 位数乘法至多需要 O(k2) 次位运算,得到的上界是 O(nk2)。仅仅 n−2 次单独的乘法步骤,就已使这一直接方法对 k 而言是指数级的。如果不在每步取模,整数 (n−1)! 本身约有 nlog2n 位,仅写出它便对 k 是指数级的工作。
对于 2048 位的 n,仅步骤数就约为 22048。因此威尔逊定理是对素数的结构性刻画,适合用于证明,而不是实用的素性检验。
半阶乘与负一的平方根
设 p 是奇素数,m=(p−1)/2。那么
(m!)2≡(−1)m+1(modp).
剩余类 1,…,p−1 分成 {j,p−j} 这些对,其中 1≤j≤m,并且 p−j≡−j。因此
(p−1)!=j=1∏mj(p−j)≡j=1∏m(−j2)=(−1)m(m!)2(modp).由威尔逊定理,−1≡(−1)m(m!)2。两边同乘 (−1)m,并利用 (−1)2m=1,得到 (m!)2≡(−1)m+1。
这一结论说明的是 (m!)2,而不是 m! 本身。若 p≡1(mod4),则 m 为偶数,(m!)2≡−1。因此 m! 是 −1 的一个明确平方根;当 p≥5 时,它既不是 1 也不是 −1。若 p≡3(mod4),则 m 为奇数,所以 (m!)2≡1,从而 m!≡±1。两个符号都确实会出现。例如 3!=6≡−1(mod7),而 11!=39916800=23⋅1735513+1,故 11!≡1(mod23)。
为了证明 p≡3(mod4) 时 −1 没有平方根,我们先证明费马(Fermat)小定理,而不把它当作已知结论。
若 p 是素数且 p∤a,则 ap−1≡1(modp)。
考虑 U(p) 上的映射 x↦ax。它将可逆元映到可逆元;它也是单射,因为若 ax≡ay,两边乘 a−1 便得到 x≡y。有限集合到自身的单射必为双射,故该映射置换 U(p)。
因此两个乘积相等:
x=1∏p−1(ax)≡x=1∏p−1x,即ap−1(p−1)!≡(p−1)!(modp).(p−1)! 是可逆元之积,故自身也是可逆元,可以消去,得到 ap−1≡1。此证明不需要使用威尔逊定理。
设 p 为奇素数。若 p≡1(mod4),则 x=((p−1)/2)! 满足 x2≡−1。若 p≡3(mod4),则同余式 x2≡−1(modp) 无解。
第一项是 m 为偶数时的半阶乘平方定理。
对第二项,假设 x2≡−1。则 x≡0,因此可用费马小定理。由于 m 为奇数,得到 1≡xp−1=(x2)m≡(−1)m=−1。于是 1≡−1,即 p∣2;这与 p 为奇素数矛盾。
合数模数:一的更多平方根
n 为合数时,配对原理仍适用于 U(n);失效的是域上的论证。模 8 时,四个可逆元 1,3,5,7 全部自身为逆元:32=9、52=25、72=49 均 ≡1(mod8)。U(12)={1,5,7,11} 的元素也都有这一性质。在 U(24) 中,八个可逆元 1,5,7,11,13,17,19,23 都自身为逆元;例如 52=25、112=121=5⋅24+1、132=169=7⋅24+1。还应注意,n 为合数时,U(n) 所有可逆元之积与 (n−1)! 是不同的量,因为后者包含非可逆元。
例题
例题 2.2.10
(p=7 时的威尔逊定理)
模 7 的逆元对为 2⋅4=8≡1 与 3⋅5=15≡1;自身为逆元的元素是 1 和 6。所以
6!≡1⋅6⋅(2⋅4)(3⋅5)≡6≡−1(mod7).这与整数计算 720=7⋅102+6 一致。
例题 2.2.11
(p=13 时的威尔逊定理与负一的平方根)
逆元对为:
2⋅7=14,3⋅9=27,4⋅10=40,5⋅8=40,6⋅11=66.它们都 ≡1(mod13),因为 14=13+1、27=26+1、40=39+1、66=65+1。再乘自身为逆元的元素 1 和 12,得 12!≡12≡−1,与动机中的余数 12 一致。
这里 m=6,且 6!=720=13⋅55+5,所以 6!≡5。于是 52=25=26−1≡−1。因此 5 和 13−5=8 都是模 13 时 −1 的平方根。
例题 2.2.12
(合数模数 n=4,9,15)
n=4 时:3!=6≡2(mod4)。剩余类既不是 0,也不是 −1≡3,所以 n=4 是例外。
n=9=32 时:平方情形使用 8! 中不同的两个因子 3 和 6。它们的乘积是 18=2⋅9,故 9∣8!。事实上 40320=9⋅4480。
n=15=3⋅5 时:不同的因子 3 和 5 都出现在 14! 中,因此 14!≡0(mod15)。
U(15)={1,2,4,7,8,11,13,14}。计算平方:
- 42=16≡1;
- 112=121=8⋅15+1;
- 142≡(−1)2=1。
所以自身为逆元的可逆元有四个:1,4,11,14。其余可逆元配对为 2⋅8=16≡1 及 7⋅13=91=6⋅15+1。
根据配对原理,所有可逆元的乘积是
1⋅4⋅11⋅14=616=41⋅15+1≡1(mod15).结果是 1,而非 −1。
常见错误
反例模式
穿过零因子消去
错误断言。“由 (x−1)(x+1)≡0(modn) 可得 x≡±1。”
为什么错误。 在整环中可用没有零因子的性质证明这一步;在有零因子的环中,通常不能使用这一论证。模 15 取 x=4,则 (x−1)(x+1)=3⋅5=15≡0,但 4≡±1。模 8 取 x=3,则 2⋅4≡0。两个非零剩余类的乘积可以为零,因此两个因子都不一定为零。
修正。 当 n 是素数时,这个推论成立,因为 Z/pZ 没有零因子。对合数 n,必须用别的方法求 x2≡1 的根,例如分别在每个素数幂因子的模下求解,再把结果组合起来。
其余两个误区与消去无关,而是关乎所计算的对象:是半阶乘还是它的平方,是整数还是它的剩余类。
反例模式
认为半阶乘总是 $\pm1$
错误断言。“模 p 时半阶乘 m! 总是 ±1。”
为什么错误。 模 13 时 6!≡5,既不是 1 也不是 12。总是 ±1 的只有 (m!)2。
错误断言。“因为 6!≡−1(mod7),所以 6!=−1。”
为什么错误。 整数 6! 等于 720。剩余数 6,或者等价地 −1,只描述它模 7 的剩余类。
练习
快速检查
(设 p=5。计算 m!,并验证 (m!)2≡(−1)m+1(mod5)。)
先计算 m=(p−1)/2。
解答 · 答案
这里 m=2 且 2!=2。于是 22=4≡−1(mod5)。由于 m+1=3,公式预言的值是 (−1)3=−1,两者一致。因为 5≡1(mod4),剩余类 2 是 −1 的平方根;3 也是,因为 32=9≡−1。
快速检查
(对 p=11 用逆元配对验证威尔逊定理,然后计算 5!mod11。)
求出模 11 下从 2 到 9 每个剩余的逆元。
解答
模 11 的逆元对为:
2⋅6=12,3⋅4=12,5⋅9=45,7⋅8=56.它们都 ≡1(mod11),因为 12=11+1、45=44+1、56=55+1。连同自身为逆元的元素 1 和 10,得到 10!≡10≡−1。
对于半阶乘,m=5 且 5!=120=110+10,故 5!≡−1。这与 (m!)2≡(−1)6=1 一致。这里 m! 恰好是 −1;p=23 时它是 +1。
快速检查
(利用分类中的平方情形证明 24!≡0(mod25),并指出使用的两个因子。)
使用 n=q2 且 q≥3 的情形。
解答
25=52,其最小素因子是 5≥3。因子 5 与 10 不同且均小于 25,所以都出现在 24! 中。它们的乘积为 50=2⋅25,故 25∣24!,即 24!≡0(mod25)。
仅有因子 5 本身不够,因为它在 1,…,24 中只出现一次。
快速检查
(计算 U(8) 的所有元素之积,并解释它为什么不是 −1。)
解答
U(8)={1,3,5,7},每个元素都自身为逆元。乘积为 1⋅3⋅5⋅7=105=13⋅8+1≡1(mod8)。
素数情形的论证失效,因为这里 x2≡1 有四个根,而非两个。另外,分类结果预言 7!=5040=8⋅630≡0。
快速检查
(解释威尔逊定理为什么需要约定 n≥2。)
解答 · 答案
n=1 时任意两个整数都模 1 同余。因此 0!=1≡−1(mod1) 成立,但 1 不是素数。环 Z/1Z 是零环,其中 1=0。正向论证所需的条件(1=−1 或 p=2)与“素数”的意义均不适用。排除 n=1 才能使等价命题成立。
快速检查
(用置换法证明费马小定理。检查边界情形 p=2,并解释证明 −1 无平方根的论证为什么需要 p 为奇数。)
先证明乘以 a 在 U(p) 上是单射。
解答
一般证明。 设 p∤a。则 x↦ax 在 U(p) 上是单射,因为可以乘 a−1 消去;故它是 U(p) 的一个置换。比较乘积,得到 ap−1(p−1)!≡(p−1)!;消去可逆元 (p−1)! 即得 ap−1≡1。
边界情形 p=2。 此时 U(2)={1},置换是恒等映射;当 a 为奇数时,a1≡1。定理仍成立。
无根论证为何需要奇素数。 该论证推出 1≡−1 并以此为矛盾。然而模 2 时 1≡−1 成立,而且 12≡−1(mod2)。因此模 2 时 −1 确有平方根,矛盾消失。
快速检查
(利用半阶乘找出模 13 时 −1 的一个平方根,并找出所有平方根。)
先计算 6! 模 13,再利用 13 是素数。
解答
这里 m=6,且 6!=720=13⋅55+5≡5。于是 52=25≡−1。
若 y2≡−1≡52,则 (y−5)(y+5)≡0。因为 13 是素数,没有零因子,故 y≡5 或 y≡8。验证:82=64=65−1≡−1。所以模 13 时 −1 的平方根恰为 5 和 8。