动机
同余式 6 x ≡ 8 ( m o d 14 ) 6x\equiv8\pmod{14} 6 x ≡ 8 ( mod 14 ) 看起来像整数方程,但消去因子时必须小心:六模十四没有逆元。在剩余类环中计算,可以解释方程何时有解、解有多少个,也能把算术与零因子、幂零元和幂等元联系起来。
定义
固定整数 n ≥ 2 n\ge2 n ≥ 2 ,记 R = Z / n Z R=\mathbb Z/n\mathbb Z R = Z / n Z 。模数明确时,用 [ a ] [a] [ a ] 表示 a a a 的剩余类。单位是有乘法逆元的元素。若非零元素 [ a ] [a] [ a ] 与某个非零 [ b ] [b] [ b ] 的乘积为零,就称 [ a ] [a] [ a ] 为零因子。某个正整数次幂为零的元素称为幂零元;平方等于自身的元素称为幂等元。零类既是幂零元也是幂等元,但按本节约定不是零因子。
将 n n n 的素因数分解写为 n = ∏ j = 1 t p j e j n=\prod\limits_{j=1}^{t}p_j^{e_j} n = j = 1 ∏ t p j e j ,其中素数互不相同且 e j ≥ 1 e_j\ge1 e j ≥ 1 。中国剩余定理(CRT)给出环同构
R ⟶ ∏ j = 1 t Z / p j e j Z , [ a ] ⟼ ( [ a ] p j e j ) j . R\longrightarrow\prod_{j=1}^{t}\mathbb Z/p_j^{e_j}\mathbb Z,
\qquad [a]\longmapsto ([a]_{p_j^{e_j}})_j. R ⟶ j = 1 ∏ t Z / p j e j Z , [ a ] ⟼ ([ a ] p j e j ) j .
它将 R R R 中的方程转化为每个素数幂坐标中的方程。反向映射把各坐标中的一个解合成为模 n n n 的唯一一个剩余类。
定理
令 d = gcd ( a , n ) d=\gcd(a,n) d = g cd( a , n ) 。方程 a x ≡ b ( m o d n ) ax\equiv b\pmod n a x ≡ b ( mod n ) 有解当且仅当 d ∣ b d\mid b d ∣ b ;有解时模 n n n 恰有 d d d 个不同的解。
证明思路
若 a x − b ax-b a x − b 能被 n n n 整除,则 d d d 同时整除 a x ax a x 和 n n n ,故 d ∣ b d\mid b d ∣ b 。反过来,若 d ∣ b d\mid b d ∣ b ,写作 a = d a ′ a=da' a = d a ′ 、b = d b ′ b=db' b = d b ′ 、n = d n ′ n=dn' n = d n ′ 。将整数整除式两边除以 d d d ,得到等价同余 a ′ x ≡ b ′ ( m o d n ′ ) a'x\equiv b'\pmod{n'} a ′ x ≡ b ′ ( mod n ′ ) 。若 n ′ > 1 n'>1 n ′ > 1 ,由 gcd ( a ′ , n ′ ) = 1 \gcd(a',n')=1 g cd( a ′ , n ′ ) = 1 和贝祖(Bézout)等式知 a ′ a' a ′ 有模 n ′ n' n ′ 逆元,故此同余模 n ′ n' n ′ 恰有一个解类 x 0 x_0 x 0 。若 n ′ = 1 n'=1 n ′ = 1 ,也恰有一个剩余类,而且同余自动成立。模 n n n 的类
[ x 0 ] , [ x 0 + n ′ ] , … , [ x 0 + ( d − 1 ) n ′ ] [x_0], [x_0+n'],\ldots,[x_0+(d-1)n'] [ x 0 ] , [ x 0 + n ′ ] , … , [ x 0 + ( d − 1 ) n ′ ] 两两不同,而且每个解都在其中。确实,两个这样的数模 d n ′ dn' d n ′ 同余,当且仅当它们的下标模 d d d 同余。
反例模式
消去需要单位 人们很容易想把非零因子消去:由 6 x ≡ 6 y ( m o d 14 ) 6x\equiv6y\pmod{14} 6 x ≡ 6 y ( mod 14 ) 推出 x ≡ y ( m o d 14 ) x\equiv y\pmod{14} x ≡ y ( mod 14 ) 。取 x = 1 x=1 x = 1 、y = 8 y=8 y = 8 ,则 6 ⋅ 1 = 6 6\cdot1=6 6 ⋅ 1 = 6 ,而 6 ⋅ 8 = 48 = 3 ⋅ 14 + 6 6\cdot8=48=3\cdot14+6 6 ⋅ 8 = 48 = 3 ⋅ 14 + 6 ,所以 6 x ≡ 6 y ( m o d 14 ) 6x\equiv6y\pmod{14} 6 x ≡ 6 y ( mod 14 ) ,但 1 ≢ 8 ( m o d 14 ) 1\not\equiv8\pmod{14} 1 ≡ 8 ( mod 14 ) 。类 [ 6 ] [6] [ 6 ] 是零因子,因为 [ 6 ] [ 7 ] = 0 [6][7]=0 [ 6 ] [ 7 ] = 0 ;差 [ x − y ] = [ − 7 ] [x-y]=[-7] [ x − y ] = [ − 7 ] 与 [ 6 ] [6] [ 6 ] 相乘得零。把上面的证明应用于 a ( x − y ) ≡ 0 ( m o d n ) a(x-y)\equiv0\pmod n a ( x − y ) ≡ 0 ( mod n ) ,便得到修正后的命题:a x ≡ a y ( m o d n ) ax\equiv ay\pmod n a x ≡ a y ( mod n ) 当且仅当 x ≡ y ( m o d n / gcd ( a , n ) ) x\equiv y\pmod{n/\gcd(a,n)} x ≡ y ( mod n / g cd( a , n )) 。这里 n / gcd ( 6 , 14 ) = 7 n/\gcd(6,14)=7 n / g cd( 6 , 14 ) = 7 ,而确实 1 ≡ 8 ( m o d 7 ) 1\equiv8\pmod7 1 ≡ 8 ( mod 7 ) 。在模 n n n 本身之下消去,恰好在 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 时才成立。
对于 [ a ] ∈ R [a]\in R [ a ] ∈ R :
[ a ] [a] [ a ] 是单位当且仅当 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ;它是非零零因子当且仅当 [ a ] ≠ 0 [a]\ne0 [ a ] = 0 且 gcd ( a , n ) > 1 \gcd(a,n)>1 g cd( a , n ) > 1 。
[ a ] [a] [ a ] 是幂零元当且仅当 n n n 的每个素因子都整除 a a a 。
幂等元在每个模 p j e j p_j^{e_j} p j e j 的坐标中可独立取 0 0 0 或 1 1 1 。因此 R R R 恰有 2 t 2^t 2 t 个幂等元。
若最大公因数为一,贝祖等式给出 u a + v n = 1 ua+vn=1 u a + v n = 1 ,因此 [ u ] [u] [ u ] 是逆元;反过来由 a u ≡ 1 ( m o d n ) au\equiv1\pmod n a u ≡ 1 ( mod n ) 可知最大公因数必为一。若 d = gcd ( a , n ) > 1 d=\gcd(a,n)>1 d = g cd( a , n ) > 1 且 [ a ] ≠ 0 [a]\ne0 [ a ] = 0 ,则 [ n / d ] [n/d] [ n / d ] 非零并且与 [ a ] [a] [ a ] 相乘得零。单位不能把非零元素乘成零,故零因子判别法成立。
若 [ a ] k = 0 [a]^k=0 [ a ] k = 0 ,每个 p j p_j p j 都整除 a k a^k a k ,因此整除 a a a 。反过来,若每个 p j p_j p j 都整除 a a a ,取 k ≥ max j e j k\ge\max\limits_j e_j k ≥ j max e j ,则每个 p j e j p_j^{e_j} p j e j 都整除 a k a^k a k ,所以它们的乘积也整除 a k a^k a k 。这证明了幂零性,但没有声称所得指数最小。
对于模 p e p^e p e 的幂等坐标,有 p e ∣ a ( a − 1 ) p^e\mid a(a-1) p e ∣ a ( a − 1 ) 。由于素数 p p p 不可能同时整除连续的两个整数,e e e 个素因子 p p p 必全部出现在其中一个因子中。因此 a ≡ 0 a\equiv0 a ≡ 0 或 1 ( m o d p e ) 1\pmod{p^e} 1 ( mod p e ) ;这两种情况确实都是幂等元。CRT 将这些独立选择唯一合并。
证明透视
为什么幂等元要逐个素数幂判断 单位判别只用贝祖等式,不需要素因子分解。另外两部分各在一个明确位置用到素数性。幂零性方面,p j ∣ a k p_j\mid a^k p j ∣ a k 推出 p j ∣ a p_j\mid a p j ∣ a ,是因为 p j p_j p j 是素数;反方向把各素数幂的整除关系相乘,这之所以合法,是因为不同素数的幂互素。幂等元方面,关键一步是 a a a 与 a − 1 a-1 a − 1 互素,所以整除 a ( a − 1 ) a(a-1) a ( a − 1 ) 的素数幂必定整个整除其中一个因子。对合数模数,这一步会失效:模 12 12 12 时,类 [ 4 ] [4] [ 4 ] 满足 12 ∣ 4 ⋅ 3 12\mid4\cdot3 12 ∣ 4 ⋅ 3 ,但 12 12 12 既不整除 4 4 4 ,也不整除 3 3 3 。因此论证要先在每个素数幂坐标中进行,然后才由 CRT 把 t t t 个互相独立的“取 0 0 0 或 1 1 1 ”选择合并成 2 t 2^t 2 t 个幂等元。
例题
求解 6 x ≡ 8 ( m o d 14 ) 6x\equiv8\pmod{14} 6 x ≡ 8 ( mod 14 ) 。最大公因数是 2 2 2 ,它整除 8 8 8 。同余式除以 2 2 2 时模数也改变,得到 3 x ≡ 4 ( m o d 7 ) 3x\equiv4\pmod7 3 x ≡ 4 ( mod 7 ) 。因为 3 − 1 ≡ 5 ( m o d 7 ) 3^{-1}\equiv5\pmod7 3 − 1 ≡ 5 ( mod 7 ) ,故 x ≡ 20 ≡ 6 ( m o d 7 ) x\equiv20\equiv6\pmod7 x ≡ 20 ≡ 6 ( mod 7 ) 。模十四有两个解 [ 6 ] [6] [ 6 ] 和 [ 13 ] [13] [ 13 ] ;代入可验得 36 ≡ 78 ≡ 8 ( m o d 14 ) 36\equiv78\equiv8\pmod{14} 36 ≡ 78 ≡ 8 ( mod 14 ) 。
由于 72 = 2 3 ⋅ 3 2 72=2^3\cdot3^2 72 = 2 3 ⋅ 3 2 ,幂零元恰为十二个被 6 6 6 整除的类:[ 0 ] , [ 6 ] , … , [ 66 ] [0],[6],\ldots,[66] [ 0 ] , [ 6 ] , … , [ 66 ] 。[ 6 ] [6] [ 6 ] 的幂零指数是三:6 2 = 36 6^2=36 6 2 = 36 模 72 72 72 不为零,而 6 3 = 216 6^3=216 6 3 = 216 模 72 72 72 为零。相反,[ 2 ] [2] [ 2 ] 是非零零因子,因为 [ 2 ] [ 36 ] = 0 [2][36]=0 [ 2 ] [ 36 ] = 0 ,但它不是幂零元,因为 3 3 3 不整除 2 2 2 的任何次幂。
这里 12 = 4 ⋅ 3 12=4\cdot3 12 = 4 ⋅ 3 。CRT 坐标 ( 0 , 0 ) , ( 1 , 1 ) (0,0),(1,1) ( 0 , 0 ) , ( 1 , 1 ) 给出 [ 0 ] , [ 1 ] [0],[1] [ 0 ] , [ 1 ] 。坐标 ( 1 , 0 ) (1,0) ( 1 , 0 ) 要求一个三的倍数同时模四余一,可取 [ 9 ] [9] [ 9 ] 。坐标 ( 0 , 1 ) (0,1) ( 0 , 1 ) 可取 [ 4 ] [4] [ 4 ] 。所以完整列表为 [ 0 ] , [ 1 ] , [ 4 ] , [ 9 ] [0],[1],[4],[9] [ 0 ] , [ 1 ] , [ 4 ] , [ 9 ] 。检验可得 4 2 ≡ 4 4^2\equiv4 4 2 ≡ 4 、9 2 ≡ 9 9^2\equiv9 9 2 ≡ 9 ,且 [ 4 ] + [ 9 ] = [ 1 ] [4]+[9]=[1] [ 4 ] + [ 9 ] = [ 1 ] 、[ 4 ] [ 9 ] = 0 [4][9]=0 [ 4 ] [ 9 ] = 0 。
乘法映射:核与像
固定 a , n a,n a , n 时,所有有解的同余式 a x ≡ b ( m o d n ) ax\equiv b\pmod n a x ≡ b ( mod n ) 都有相同数量的解,这有一个结构上的原因。把 R R R 看作加法群,定义 T a : R → R T_a:R\to R T a : R → R ,T a ( [ x ] ) = [ a x ] T_a([x])=[ax] T a ([ x ]) = [ a x ] 。它良定:将 x x x 改变一个 n n n 的倍数只会将 a x ax a x 改变一个 n n n 的倍数;分配律说明它是加法群同态。这里不要求它是保单位元的环同态;乘以 a a a 一般既不保持乘积,也不保持单位元。
令 d = gcd ( a , n ) d=\gcd(a,n) d = g cd( a , n ) ,n ′ = n / d n'=n/d n ′ = n / d 。核恰由 [ k n ′ ] [kn'] [ k n ′ ] 构成,其中 0 ≤ k < d 0\le k<d 0 ≤ k < d 。因为同余 a x ≡ 0 ( m o d n ) ax\equiv0\pmod n a x ≡ 0 ( mod n ) 约化为 a ′ x ≡ 0 ( m o d n ′ ) a'x\equiv0\pmod{n'} a ′ x ≡ 0 ( mod n ′ ) ,故 n ′ ∣ x n'\mid x n ′ ∣ x ;不同提升便给出这些核元素。像是所有 [ d ] [d] [ d ] 的倍数组成的子群 ⟨ [ d ] ⟩ \langle[d]\rangle ⟨[ d ]⟩ 。因为 d ∣ a d\mid a d ∣ a ,像包含于此子群;反过来贝祖等式给出 d = u a + v n d=ua+vn d = u a + v n ,因此 [ d ] = T a ( [ u ] ) [d]=T_a([u]) [ d ] = T a ([ u ]) 。它的元素为 [ 0 ] , [ d ] , … , [ ( n ′ − 1 ) d ] [0],[d],\ldots,[(n'-1)d] [ 0 ] , [ d ] , … , [( n ′ − 1 ) d ] ,阶为 n ′ n' n ′ 。
因此第一同构定理给出以下加法群同构 :
( R , + ) / ker T a ≅ im T a = ⟨ [ d ] ⟩ , [ x ] + ker T a ⟼ [ a x ] . (R,+)/\ker T_a\cong\operatorname{im}T_a=\langle[d]\rangle,\qquad [x]+\ker T_a\longmapsto[ax]. ( R , + ) / ker T a ≅ im T a = ⟨[ d ]⟩ , [ x ] + ker T a ⟼ [ a x ] .
这个映射良定,因为同一核陪集的代表元有相同像;它满射到像中,而且只有核陪集映到零,所以它是单射。
若 [ x 0 ] [x_0] [ x 0 ] 是 T a ( [ x ] ) = [ b ] T_a([x])=[b] T a ([ x ]) = [ b ] 的一个解,全部解恰是陪集 [ x 0 ] + ker T a [x_0]+\ker T_a [ x 0 ] + ker T a :从任一解减去 x 0 x_0 x 0 得到核元素,反过来加上任意核元素仍是解。因此非空的原像恰有 d d d 个元素;若 [ b ] [b] [ b ] 不在像中,原像为空。这说明存在条件与解数为什么相互关联。
局部方程与整体答案
在 CRT 下,模 n n n 的等式 [ a ] [ x ] = [ b ] [a][x]=[b] [ a ] [ x ] = [ b ] 成立,当且仅当它在每个模 p j e j p_j^{e_j} p j e j 的坐标中成立。固定一个素数幂 p e p^e p e ,令 f f f 为 0 0 0 到 e e e 之间使 p f ∣ a p^f\mid a p f ∣ a 的最大整数;当 a = 0 a=0 a = 0 时取 f = e f=e f = e 。等价地,p f = gcd ( a , p e ) p^f=\gcd(a,p^e) p f = g cd( a , p e ) 。线性同余定理说明,局部方程有解当且仅当 p f ∣ b p^f\mid b p f ∣ b ,有解时模 p e p^e p e 恰有 p f p^f p f 个解。
所有局部条件合起来等价于 gcd ( a , n ) ∣ b \gcd(a,n)\mid b g cd( a , n ) ∣ b 。如果它们都成立,就在每个素数幂坐标中选一个局部解;CRT 给出唯一的整体剩余类,而每个整体解都来自唯一一个这样的坐标组。将局部解数相乘得到 ∏ j p j f j = gcd ( a , n ) \prod\limits_j p_j^{f_j}=\gcd(a,n) j ∏ p j f j = g cd( a , n ) 。这与核的论证给出相同结论,但这里分解的是环,而不是加法映射。
求解 12 x ≡ 18 ( m o d 30 ) 12x\equiv18\pmod{30} 12 x ≡ 18 ( mod 30 ) 。这里 d = 6 d=6 d = 6 ,故方程有解且恰有六解。把整个同余式连同模数除以六,得 2 x ≡ 3 ( m o d 5 ) 2x\equiv3\pmod5 2 x ≡ 3 ( mod 5 ) ;由于 2 − 1 ≡ 3 ( m o d 5 ) 2^{-1}\equiv3\pmod5 2 − 1 ≡ 3 ( mod 5 ) ,所以 x ≡ 4 ( m o d 5 ) x\equiv4\pmod5 x ≡ 4 ( mod 5 ) 。模三十的六个解是
[ 4 ] , [ 9 ] , [ 14 ] , [ 19 ] , [ 24 ] , [ 29 ] . [4], [9], [14], [19], [24], [29]. [ 4 ] , [ 9 ] , [ 14 ] , [ 19 ] , [ 24 ] , [ 29 ] . 局部计算得到同一答案。因为 30 = 2 ⋅ 3 ⋅ 5 30=2\cdot3\cdot5 30 = 2 ⋅ 3 ⋅ 5 ,模二和模三时方程都是 0 = 0 0=0 0 = 0 ,因此分别允许全部两个及三个局部剩余类。模五时方程是 2 x = 3 2x=3 2 x = 3 ,唯一解为 [ 4 ] [4] [ 4 ] 。CRT 将 2 ⋅ 3 ⋅ 1 = 6 2\cdot3\cdot1=6 2 ⋅ 3 ⋅ 1 = 6 个坐标组组合成上列六个类。在加法映射 T 12 T_{12} T 12 中,核为 { [ 0 ] , [ 5 ] , [ 10 ] , [ 15 ] , [ 20 ] , [ 25 ] } \{[0],[5],[10],[15],[20],[25]\} {[ 0 ] , [ 5 ] , [ 10 ] , [ 15 ] , [ 20 ] , [ 25 ]} ,解集就是陪集 [ 4 ] + ker T 12 [4]+\ker T_{12} [ 4 ] + ker T 12 。
现在把右边换成 15 15 15 。模二时方程变成 0 = 1 0=1 0 = 1 ,所以没有整体解。只需一个不相容的局部方程就可否定解的存在;只检查一个相容的坐标则不足以证明有解。
求首次为零的幂
幂零判别法告诉我们某个幂是否会变为零;素因子的指数还能告诉我们第一次 何时变为零。设 [ a ] [a] [ a ] 是幂零元且 a ≠ 0 a\ne0 a = 0 。对每个 p j ∣ n p_j\mid n p j ∣ n ,令 s j s_j s j 为 a a a 中 p j p_j p j 的指数,则 s j ≥ 1 s_j\ge1 s j ≥ 1 。在 a k a^k a k 中,该指数为 k s j ks_j k s j ;因此 [ a ] k = 0 [a]^k=0 [ a ] k = 0 等价于对所有 j j j 同时有 k s j ≥ e j ks_j\ge e_j k s j ≥ e j 。满足条件的最小正整数为
max 1 ≤ j ≤ t ⌈ e j s j ⌉ . \max_{1\le j\le t}\left\lceil\frac{e_j}{s_j}\right\rceil. 1 ≤ j ≤ t max ⌈ s j e j ⌉ .
必须取最大值:只有每个素数幂坐标都变为零,整个类才为零。若选用代表元 a = 0 a=0 a = 0 ,首次为零的正整数指数直接是 1 1 1 ;上式只对非零代表元陈述,以保证各指数有限。
取 n = 360 = 2 3 ⋅ 3 2 ⋅ 5 n=360=2^3\cdot3^2\cdot5 n = 360 = 2 3 ⋅ 3 2 ⋅ 5 和 a = 30 = 2 ⋅ 3 ⋅ 5 a=30=2\cdot3\cdot5 a = 30 = 2 ⋅ 3 ⋅ 5 。所需的三个素数都整除 30 30 30 ,故其类是幂零元。三个指数均为一,公式给出 max { 3 , 2 , 1 } = 3 \max\{3,2,1\}=3 max { 3 , 2 , 1 } = 3 。实际上 30 2 = 900 30^2=900 3 0 2 = 900 不能被 360 360 360 整除(它只有两个因子 2 2 2 ),而 30 3 = 27000 = 75 ⋅ 360 30^3=27000=75\cdot360 3 0 3 = 27000 = 75 ⋅ 360 。故 [ 30 ] 2 ≠ 0 [30]^2\ne0 [ 30 ] 2 = 0 ,但 [ 30 ] 3 = 0 [30]^3=0 [ 30 ] 3 = 0 。这里上界 max e j \max e_j max e j 恰好达到;当 a a a 含有更高的素数幂时,上界未必是最小指数。
构造互补的幂等元
CRT 不只给出数量,也提供构造方法。设 n = u v n=uv n = uv ,其中 u , v > 1 u,v>1 u , v > 1 且互素。要找模 ( u , v ) (u,v) ( u , v ) 坐标为 ( 1 , 0 ) (1,0) ( 1 , 0 ) 的幂等元,可从 v k vk v k 出发并求解 v k ≡ 1 ( m o d u ) vk\equiv1\pmod u v k ≡ 1 ( mod u ) 。贝祖等式保证 v v v 模 u u u 有逆元,因而得到模 n n n 的唯一类 e e e 。类 1 − e 1-e 1 − e 的坐标是 ( 0 , 1 ) (0,1) ( 0 , 1 ) 。逐坐标计算可知两者都等于自身的平方,而乘积为零。每个 [ x ] [x] [ x ] 都分解为 [ x ] = e [ x ] + ( 1 − e ) [ x ] [x]=e[x]+(1-e)[x] [ x ] = e [ x ] + ( 1 − e ) [ x ] :第一项的 v v v 坐标为零,第二项的 u u u 坐标为零。这是环中的分解,不依赖整数代表元的选择。
这两个部分还说明了环如何分解。集合 e R = { e r : r ∈ R } eR=\{er:r\in R\} e R = { er : r ∈ R } 和 ( 1 − e ) R = { ( 1 − e ) r : r ∈ R } (1-e)R=\{(1-e)r:r\in R\} ( 1 − e ) R = {( 1 − e ) r : r ∈ R } 在继承的运算下都是环,单位元分别为 e e e 和 1 − e 1-e 1 − e ;一般来说,它们都不是 1 R 1_R 1 R 。映射 r ↦ ( e r , ( 1 − e ) r ) r\mapsto(er,(1-e)r) r ↦ ( er , ( 1 − e ) r ) 保持加法和乘法,因为 e ( 1 − e ) = 0 e(1-e)=0 e ( 1 − e ) = 0 使交叉乘积为零。其逆映射将 ( a , b ) (a,b) ( a , b ) 送到 a + b a+b a + b :确实,e a = a ea=a e a = a 、( 1 − e ) b = b (1-e)b=b ( 1 − e ) b = b ,交叉项均为零。因此 R ≅ e R × ( 1 − e ) R R\cong eR\times(1-e)R R ≅ e R × ( 1 − e ) R 。在 CRT 下,这两个因子分别对应 Z / u Z \mathbb Z/u\mathbb Z Z / u Z 与 Z / v Z \mathbb Z/v\mathbb Z Z / v Z 。例如,乘以 e e e 恰好保留第一个坐标,因此它是投影,而非可逆的坐标变换。
这里 u = 8 u=8 u = 8 、v = 9 v=9 v = 9 。因为 9 ≡ 1 ( m o d 8 ) 9\equiv1\pmod8 9 ≡ 1 ( mod 8 ) ,可取 k = 1 k=1 k = 1 ,得到 e = [ 9 ] e=[9] e = [ 9 ] ,于是 1 − e = [ − 8 ] = [ 64 ] 1-e=[-8]=[64] 1 − e = [ − 8 ] = [ 64 ] 。模 ( 8 , 9 ) (8,9) ( 8 , 9 ) 的坐标分别为 ( 1 , 0 ) (1,0) ( 1 , 0 ) 和 ( 0 , 1 ) (0,1) ( 0 , 1 ) 。例如 [ 13 ] = [ 9 ] [ 13 ] + [ 64 ] [ 13 ] = [ 45 ] + [ 40 ] [13]=[9][13]+[64][13]=[45]+[40] [ 13 ] = [ 9 ] [ 13 ] + [ 64 ] [ 13 ] = [ 45 ] + [ 40 ] ,因为 85 ≡ 13 ( m o d 72 ) 85\equiv13\pmod{72} 85 ≡ 13 ( mod 72 ) 。两项各自保留一个坐标。连同 [ 0 ] [0] [ 0 ] 和 [ 1 ] [1] [ 1 ] ,它们就是模 72 72 72 的全部四个幂等元。
快速检查
([ 12 ] [12] [ 12 ] 模 72 72 72 的首次为零的幂是多少?)
比较每个素数在 12 12 12 与在 72 72 72 中的指数。
解答 · 答案 由于 12 = 2 2 ⋅ 3 12=2^2\cdot3 12 = 2 2 ⋅ 3 而 72 = 2 3 ⋅ 3 2 72=2^3\cdot3^2 72 = 2 3 ⋅ 3 2 ,答案为 max { ⌈ 3 / 2 ⌉ , ⌈ 2 / 1 ⌉ } = 2 \max\{\lceil3/2\rceil,\lceil2/1\rceil\}=2 max {⌈ 3/2 ⌉ , ⌈ 2/1 ⌉} = 2 :确实,12 2 = 144 12^2=144 1 2 2 = 144 能被 72 72 72 整除,而 [ 12 ] ≠ 0 [12]\ne0 [ 12 ] = 0 。
常见错误
把 6 x ≡ 8 ( m o d 14 ) 6x\equiv8\pmod{14} 6 x ≡ 8 ( mod 14 ) 两边除以二却仍保留模数十四,会得到另一个条件。模数也要除以二,然后再数回到原模数下的解。
常见错误
(0 x = 0 0x=0 0 x = 0 允许该坐标的每个类)
局部方程 0 x = 0 0x=0 0 x = 0 允许该坐标中的每个类作为解,而非仅允许零。相反,0 x = c 0x=c 0 x = c 且 c ≠ 0 c\ne0 c = 0 没有局部解,因此也没有整体解。
零因子未必是幂零元:模六的 [ 3 ] [3] [ 3 ] 是非零幂等元,却把 [ 2 ] [2] [ 2 ] 乘成零。另一方面,一个剩余类可以幂零,即使它的整数代表元不是零;定义只要求某次幂能被模数整除。当模数还有其他素因子时,仅被其中一个素因子整除是不够的。
可选 剩余类环有多少个单位? 在每个素数幂坐标中数单位,再把各个数目相乘。
自然的下一个问题
剩余类环有多少个单位? 在每个素数幂坐标中数单位,再把各个数目相乘。
由于 CRT 映射是环同构,而乘法逐坐标计算,一个剩余类是单位当且仅当它的每个 CRT 坐标都是单位。模 p e p^e p e 时,单位判别法恰好排除 p p p 的 p e − 1 p^{e-1} p e − 1 个倍数,剩下 p e − p e − 1 p^e-p^{e-1} p e − p e − 1 个单位。因此 R R R 共有 ∏ j = 1 t ( p j e j − p j e j − 1 ) \prod\limits_{j=1}^{t}\bigl(p_j^{e_j}-p_j^{e_j-1}\bigr) j = 1 ∏ t ( p j e j − p j e j − 1 ) 个单位。对 n = 72 n=72 n = 72 ,得 ( 8 − 4 ) ( 9 − 3 ) = 24 (8-4)(9-3)=24 ( 8 − 4 ) ( 9 − 3 ) = 24 个单位;其余 48 48 48 个剩余类中,十二个是幂零元(包括零),三十六个是非幂零的零因子。
关闭
总结
用最大公因数求线性方程并识别单位;用模数的素因子判断幂零性;用每个素数幂坐标中独立的零或一选择求幂等元。CRT 把局部答案合并,但它不表示任意两个非互素模数的同余条件都相容。
练习
快速检查
(求解 8 x ≡ 12 ( m o d 20 ) 8x\equiv12\pmod{20} 8 x ≡ 12 ( mod 20 ) ,并说明解的列表完整。求加法群映射 [ x ] ↦ [ 8 x ] [x]\mapsto[8x] [ x ] ↦ [ 8 x ] 的核与像,并将解集写成核的陪集。)
解答 · 答案 此时 d = 4 d=4 d = 4 整除 12 12 12 。两边及模数除以四得到 2 x ≡ 3 ( m o d 5 ) 2x\equiv3\pmod5 2 x ≡ 3 ( mod 5 ) ,所以 x ≡ 4 ( m o d 5 ) x\equiv4\pmod5 x ≡ 4 ( mod 5 ) 。模二十的四个解是 [ 4 ] , [ 9 ] , [ 14 ] , [ 19 ] [4],[9],[14],[19] [ 4 ] , [ 9 ] , [ 14 ] , [ 19 ] 。核为 { [ 0 ] , [ 5 ] , [ 10 ] , [ 15 ] } \{[0],[5],[10],[15]\} {[ 0 ] , [ 5 ] , [ 10 ] , [ 15 ]} ,像为 { [ 0 ] , [ 4 ] , [ 8 ] , [ 12 ] , [ 16 ] } \{[0],[4],[8],[12],[16]\} {[ 0 ] , [ 4 ] , [ 8 ] , [ 12 ] , [ 16 ]} ,解集是 [ 4 ] + ker T 8 [4]+\ker T_8 [ 4 ] + ker T 8 。
快速检查
(求模 18 18 18 的所有幂零元,以及使 [ 6 ] [6] [ 6 ] 变成零的最小正整数次幂。)
解答 · 答案 因为 18 = 2 ⋅ 3 2 18=2\cdot3^2 18 = 2 ⋅ 3 2 ,幂零元是 [ 0 ] , [ 6 ] , [ 12 ] [0],[6],[12] [ 0 ] , [ 6 ] , [ 12 ] 。6 6 6 非零且 6 2 = 36 ≡ 0 ( m o d 18 ) 6^2=36\equiv0\pmod{18} 6 2 = 36 ≡ 0 ( mod 18 ) ,故 [ 6 ] [6] [ 6 ] 的最小正指数为二。
解答 · 答案 对 15 = 3 ⋅ 5 15=3\cdot5 15 = 3 ⋅ 5 应用 CRT,有四种选择。坐标 ( 0 , 0 ) , ( 1 , 1 ) , ( 1 , 0 ) , ( 0 , 1 ) (0,0),(1,1),(1,0),(0,1) ( 0 , 0 ) , ( 1 , 1 ) , ( 1 , 0 ) , ( 0 , 1 ) 分别对应 [ 0 ] , [ 1 ] , [ 10 ] , [ 6 ] [0],[1],[10],[6] [ 0 ] , [ 1 ] , [ 10 ] , [ 6 ] 。
快速检查
(证明 Z / n Z \mathbb Z/n\mathbb Z Z / n Z 没有非零幂零元,当且仅当 n n n 无平方因子。)
解答 · 答案 若 n n n 无平方因子,则每个素因子都整除 a a a 蕴含 n ∣ a n\mid a n ∣ a ,故所有幂零类都为零。若某个指数 e j ≥ 2 e_j\ge2 e j ≥ 2 ,令 a a a 为 n n n 的所有不同素因子之积,则 [ a ] [a] [ a ] 按判别法是幂零元,但因 n ∤ a n\nmid a n ∤ a 而非零。