動機
剩餘恰好記錄了一個整數除以固定模數之後所能看到的那部分資訊。運用剩餘可以縮短計算,但它會改變消去律的規則。方程 有解,儘管 在模 之下沒有逆元。弄清楚這個例子,便能引出一般的可解性定理,進而引出由若干個餘數重構整數的方法。
定義
定義 2.1.1
(同餘與單位)
固定整數 。關係 表示 。剩餘類 是所有與 同餘的整數所組成的集合。剩餘類的加法與乘法由整數的運算誘導而來。單位是具有乘法逆元的剩餘類; 是單位,當且僅當 。
這些運算是良定的,因為把 換成 時,它們的和與積只會改變 的倍數。逆元判準源自貝祖(Bézout)定理:由 得 ;反過來,逆元等式表示對某些整數 有 。同餘是一個等價關係,因此由 所代表的這 個剩餘類把整數集劃分開來。
定理/命題
定理 2.1.2
(線性同餘定理)
設 。同餘式 有解,當且僅當 。若有解,則模 恰有 個不同的解。若 是其中一個解,則所有解為 ,其中 。
定理 2.1.3
(中國剩餘定理與相容性)
對於兩兩互質的整數 ,任何方程組 模 恰有一個解類。對於任意兩個模數 ,餘數為 的方程組有解,當且僅當 ;有解時,解模 唯一。
證明思路
證明
(貝祖定理,然後約化模數)
線性同餘式就是整數方程 ,因此可以用貝祖定理證明可解性判準。除以 之後,係數 在模 之下可逆。於是模 有唯一的解類,而它在模 之下恰好分成 個類。所列出的兩個代表元相差 ;它能被 整除,當且僅當 ,這便證明了這些解兩兩不同。
證明
(互質模數的選擇子;兩個模數的代入)
至於互質情形的定理,設 ,並選取 使 。那麼 滿足每一個指定的餘數:除第 項以外,所有加項在模 之下都等於零。兩個解之差是能被每個 整除的整數,因此(利用兩兩互質與質因數分解)能被 整除。
對於兩個一般的模數,設 。第二個方程變為 ,它有解恰好在所述的最大公因數條件成立時。任意兩個解之差同時被 整除,這恰好等價於被它們的最小公倍數整除。這也以正確的模數證明了唯一性。
證明透視
兩兩互質用在哪裏
互質情形的證明把這個假設用了兩次,目的各不相同。存在性需要每個 在模 下是單位;由於 與其他任何 沒有公共質因數,。於是選擇子 在模 下為 ,在其他每個模數下為 ,而解不過是組合 。唯一性需要由「被每個 整除」推到「被 整除」,這同樣恰好是兩兩互質。
對模數 和 ,兩步都明顯失效: 滿足 ,所以模 的選擇子不存在;而 同時被 和 整除,卻不被 整除。兩個模數的論證把它歸結為第一個定理,一併修補這兩點。代入 得 ,這是 的線性同餘式。它的可解性判準正是相容條件,而它的解 組成模 的一個類,所以 在模 下唯一確定。
例題詳解
例題 2.1.4
(非單位係數)
對於 , 整除 。把整個整除關係式除以 ,得 ,因而 。模 的三個解為 。若在除以 的同時保持模數為 ,便會改變原來的問題。
例題 2.1.5
(由互質的餘數重構整數)
解 ,,。取 ,用 ,相應的逆元分別為 。此構造給出 。確實, 具備所要求的三個餘數。
例題 2.1.6
(先判斷相容性,再作重構)
方程組 , 是相容的,因為 。代入 得 ,故 ,從而 。若把第二個餘數改為 ,方程組便不可能有解:一個方程要求整數為奇數,另一個則要求為偶數。
同餘保持運算,但不保持所有推論
同餘容許我們把整數換成較簡單的代表元,因為加法與乘法都尊重這個等價關係。減法也包括在內,因為負數與同餘相容。除法則有所不同:只有當除數有逆元,或者調整模數以補償所失去的資訊時,這種運算才可能是良定的。這個分別解釋了為甚麼模運算在一長串計算中可以與一般算術相似,卻會在某一個看似無害的消去步驟上失效。
為了直接推導調整後的規則,設某個乘積之差能被模數整除。把係數與模數同時除以它們的最大公因數。此時約化後的係數與約化後的模數互質,因此貝祖定理容許在這裏作消去。結論是一個以約化後的模數為模的同餘式。所以消去並不神秘:它只是一般的整除性,加上一個仔細表述的互質事實。模數的縮小恰好記錄了非單位係數所帶來的不確定性。
反例模式
消去非單位會丟失資訊
錯誤的論斷是:每個非零係數都可以在保持模數不變的情況下被消去。模六時,把剩餘一與四分別乘以二,得到相同的剩餘,儘管原來的兩個剩餘並不相同。修正後的說法只消去單位,或者把模數除以它與係數的最大公因數。當模數是合數時,非零是比可逆更弱的條件。
因此,線性同餘式的最大公因數條件起著兩種不同的作用。它決定目標是否落在「乘以該係數」這個映射的像之中,同時也計算有多少個源剩餘類共享這個像。一個像類恰好被齊次方程的解的個數那麼多個元素所達到。把一個解平移一個齊次解,目標保持不變;而任意兩個解相減,便得到一個齊次解。這從概念上解釋了為甚麼每個可解的目標都有相同數目的原像。
既數像,也數解
可達到的目標類的個數等於模數除以最大公因數。事實上,可達到的目標必須被該最大公因數整除,而可解性定理說明每個這樣的目標都能被達到。每個可達到的目標恰有等於該最大公因數的個數的原像。把像的大小乘以這個共同的纖維大小,便得回源剩餘類的總數。這為定理中的解數提供了一個有用的獨立檢驗。
例如,模十五時乘以六,恰好能達到由零、三、六、九、十二所代表的五個類。每個類有三個原像。於是十五個源剩餘類被劃分成五個大小相等的纖維。要求這個映射的逆是不可能的:三個不同的輸入給出同一個輸出。把模數約化為五、係數約化為二之後,這個映射便成為雙射,而這正是第一個例題的計算所用到的。
重構項起著選擇器的作用
在計算任何目標餘數之前,已可理解中國剩餘定理的構造。對每個模數,構造一個數,它模該模數為一,模所有其他模數為零。這樣的數選出剩餘元組的其中一個座標。把它乘以所需的座標值,再把所有這些貢獻相加,便得到所要求的整數。該構造對剩餘數據是線性的,所以同樣的選擇器項可以在模數相同的許多不同方程組中重複使用。
這個觀點也解釋了唯一性。如果一個整數的所有座標都等於零,它便能被每個模數整除。兩兩互質則使它能被這些模數的乘積整除。因此,映到零元組的類只有模乘積的零類。存在性為每個元組構造出一個類;唯一性說明不同的類不可能代表同一個元組。兩者合起來描述了一個精確的對應,而不僅僅是一個碰巧產生解的做法。
概念視角結構
把一個剩餘看作局部剩餘的元組
對於兩兩互質的模數,約化把模乘積的剩餘映為它模各因數的剩餘所組成的元組。該映射逐座標地保持加法與乘法。中國剩餘定理證明這個映射是雙射。因此,一個很大的模計算可以在較小的模數下分別進行,之後再重構,沒有任何近似。
一個推論是,對互質的模數,單位的個數可以分解。一個整數與若干互質因數之積互質,當且僅當它與每個因數都互質。在剩餘元組的對應之下,單位因此恰好就是由單位組成的元組。數算這些元組,便得到歐拉(Euler)函數在互質情形下的積性。這把一個重構定理與一個起初看來只是計數定義的算術函數聯繫起來。
相容性是共享的資訊,而不是技術上的麻煩
當兩個模數有公因數時,兩個同餘式都已經規定了模該公因數的餘數。這些規定必須一致。這無須任何代數運算,便證明了相容性條件的必要性。線性同餘式的約化隨後證明其逆命題:對於兩個模數,在共享資訊上一致已經足夠。最小公倍數是正確的唯一性模數,因為它綜合了任何一個模數所要求的全部質數冪,而不會把重疊的要求重複計算兩次。
為了具體看清這個分別,取一個模數整除另一個模數的情形。模較大模數的剩餘已經決定了它模較小模數的剩餘。較小的同餘式要麼與之一致而不提供新的資訊,要麼與之矛盾而令方程組不相容。在這種情形下把兩個模數相乘,會引入人為多出來的類。最小公倍數則恰好保留較大的模數,正如資訊詮釋所預言的那樣。
對於若干個並非兩兩互質的模數,可以每次合併兩個同餘式。一次合併成功之後,記下所得的餘數和最小公倍數模數,再用兩個模數的定理合併下一個條件。在每一個階段,所記錄的同餘式恰好代表迄今已處理的所有條件的解。若相容性不成立,原方程組便無解。這個過程無須任何沒有根據的乘積公式,並且能自然地處理多餘的條件。
是的:方程組有解,當且僅當其中任何兩個同餘式都相容。
自然延伸的下一個問題
對多個模數,兩兩相容是否足夠?
是的:方程組有解,當且僅當其中任何兩個同餘式都相容。
必要性就是兩個模數的情形。至於充分性,把每個條件 分拆為各質數冪部分。對固定的質數 ,保留一個來自 、指數最大的模 條件。任何其他來自 的模 部分滿足 ,因此已被推出。保留下來的條件涉及互不相同的質數,由互質情形的定理求解。
檢驗重構所得的答案
一個完整的解答應當包含一個代表元及其唯一性模數。把代表元代入每一個原有的同餘式。這驗證了構造在算術化簡之後依然成立。然後,透過考察兩個解之差來論證模數。單靠代入檢驗並不能說明完備性;許多個別的整數都可能滿足該方程組。反過來,只有正確的唯一性模數而沒有代表元,也不能確立存在性。定理同時提供這兩者,書面的解答應當讓它們各自的作用清楚顯現。
非線性的計算也可以分解為各個座標
剩餘對應保持乘法,所以它也可以用來整理多項式方程。例如,求解模兩個不同奇質數之積時平方等於一的方程,相當於在每個質數模數之下求解同一個方程。在每個域中恰有兩種選擇,一和負一:把平方差因式分解並利用沒有零因子,即可證明這一點。中國剩餘定理把每一對選擇結合成模乘積的恰好一個剩餘。於是,儘管這個多項式的次數是二,模該乘積卻有四個根。域上根的個數上界只在每個質數座標中使用,在那裏它的假設成立。這個例子既顯示了重構的威力,也顯示了把域上的定理原封不動搬到合數模數上的危險。它還區分了計數解與列出解:四種座標選擇確立了解的個數,而重構公式則計算出它們的實際代表元。
常見錯誤
常見錯誤
(消去不是單位的係數)
由 ,只有當 是單位時,才可以消去 並保持模數 不變。一般情況下,有效的結論是 。例如 ,但 。
常見錯誤
(乘積模數需要兩兩互質)
中國剩餘定理中的乘積模數同樣要求兩兩互質。對於模數 ,自然的唯一性模數是 ,而不是 :一個模 的解類在模 下分成兩個類。要說明你的答案是一個整數代表元,還是整個剩餘類。
常見錯誤
(二次同餘式可以有多於兩個根)
「二次多項式至多有兩個根」是關於域的定理,所以它適用於質數模,卻不適用於合數模。模 時,剩餘 的平方都是 :例如 ,。應在每個質數座標上使用根的個數上界,再用中國剩餘定理組合。
總結
最大公因數掌管著同餘式中的除法。互質的模數容許任意的局部剩餘;有重疊的模數則施加相容性條件。重構公式提供存在性,而差的整除性給出唯一性。
練習
快速檢查
(求同餘式 14x 同餘於 8(模 30)的所有解。)
把係數與模數一併約化。
解答 · 答案
最大公因數為 ,故兩邊除以 得 。由於 ,得 。因此 ;直接相乘可知兩種情形的餘數都是 。
快速檢查
(解 同餘於 2(模 9)且 同餘於 5(模 12),或證明無解。)
在代入之前先檢查最大公因數。
解答 · 答案
由於 整除 ,寫 。則 ,即 ,故 。因此 。它的餘數是 和 ,而唯一性模數是最小公倍數 。
快速檢查
(求所有滿足 的模 剩餘 。)
先分別在模 和模 下求解,再組合。
解答 · 答案
由於 與 是質數, 在質數模下迫使其中一個因子為零,所以 在每個座標上都迫使 。中國剩餘定理把四種符號選擇組合成模 的四個類:、、、。驗算:,。答案是 。