動機
像 6 x ≡ 8 ( m o d 14 ) 6x\equiv 8\pmod{14} 6 x ≡ 8 ( mod 14 ) 這樣的同餘式,看來是一條整數方程,但消去時必須小心:六在模十四下沒有乘法逆元。以剩餘類環的角度處理,可以解釋方程何時有解,以及究竟有多少個解;這亦把算術與環論中的零因子、冪零元和冪等元聯繫起來。
定義
固定整數 n ≥ 2 n\ge 2 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 ] [ b ] = 0 [a][b]=0 [ a ] [ b ] = 0 ,則 [ a ] [a] [ a ] 是零因子 。某個正整數次冪為零的元素稱為冪零元 ;平方等於自身的元素稱為冪等元 。零類既是冪零元也是冪等元,但依照我們的慣例,它不是零因子。
把質因數分解寫成 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 ′ 下的逆元,所以滿足此式的 x 0 x_0 x 0 模 n ′ n' n ′ 恰有一個剩餘類。當 n ′ = 1 n'=1 n ′ = 1 時,模一只有一個剩餘類,它也滿足同餘式。模 n n n 下的剩餘類
[ x 0 ] , [ x 0 + n ′ ] , … , [ x 0 + ( d − 1 ) n ′ ] 模 n [x_0], [x_0+n'],\ldots,[x_0+(d-1)n']\quad\text{模 }n [ x 0 ] , [ x 0 + n ′ ] , … , [ x 0 + ( d − 1 ) n ′ ] 模 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 。
冪等元對每個 j j j 的座標在模 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 為零。相比之下,[ 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 p^f p f 整除 a a 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 容許該座標的每個類)
在 CRT 局部方程中,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 無平方因子,則每個整除 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 ,它不是零。