一個整數,兩項資訊
知道一個數模四的餘數,通常不能決定它模五的餘數。不過,兩個相容的餘數要求可共同描述一個較大模數下的剩餘類。我們會構造這個類、確定它何時存在,並解釋其商環意義。
定義 7.1.1
(同餘與剩餘類)
以下 是正整數, 是整數。 意味 ;它描述整個剩餘類,而不只是 0 至 的一個數。最小公倍數 取正值。
互質模數的構造
定理 7.1.2
(兩個互質模數)
若 ,對任何 ,聯立條件
都有解,而且任意兩個解模 同餘。
證明
(由 Bézout 恆等式得到兩個選擇子)
選整數 使 ,令
模 時,,;模 時,,。因此 同時滿足兩個要求:每個選擇子保留一邊的餘數,消去另一邊的餘數。
若 都是解,則 都整除 。由互質性可知 :例如寫 ,由 和 得 。反過來,加上 的任意倍數不改變兩個同餘條件。所以所有解恰好構成模 的一個剩餘類。
證明透視
互質性用在何處
互質性被使用了兩次,各有不同的用途。存在性需要恆等式 :它把 拆成 的一個倍數與 的一個倍數之和,正是這個拆分使每個選擇子在一邊 、在另一邊 。唯一性需要消去律 ,這是唯一把 用在整除而非線性組合上的地方。真正起作用的想法,是 由兩個要求分別構造而成,無需搜尋。沒有互質性便沒有 ,而下一節會說明此時剩下甚麼。
的選法不必唯一;不同選法可能給出不同整數 ,但上述唯一性保證它們代表同一個模 的類。
例題 7.1.3
(構造模二十的解)
解 、。由 ,取 。選擇子是 、,故
驗算:18 模 4 餘 2,模 5 餘 3。所有解是 ,其中 為整數;答案不是單一整數。
模數有共同因數時
定理 7.1.4
(任意正模數的相容條件)
令 。聯立條件有解,當且僅當 。有解時,所有解構成模 的一個剩餘類。
證明
(化為互質的一元線性同餘)
若 同時是解, 既整除 也整除 ,因此整除兩者之差 ,得到必要性。
反過來,假設 。寫 、,則 。令 ,第二個條件化為
由 Bézout 恆等式選 使 。取 ,便有 ,所以 滿足原來兩個條件。此論證亦包括 :模一同餘自動成立。
若 都是解,它們的差同時被 整除。寫成 ,由 得 ;互質性給出 ,故差被 整除。反過來,此最小公倍數的每個倍數都被兩個模數整除,因此它正是解類的模數。
例題 7.1.5
(共同因數可以允許或阻止解)
對 和 ,最大公因數是 2,且整除 。整數 14 滿足兩式,故完整答案為 。
相反, 和 無共同解:第一式要求奇數,第二式要求偶數。等價地,餘數之差 1 不被 整除。
例題 7.1.6
(一個模數整除另一個(邊界情況))
取 和 。這裏 整除 ,所以有解。取 、,則 ,模 的化簡同餘自動成立。解構成模 的一個類,即 :第二個要求沒有增加任何資訊,因為 已經成立。
反例模式
乘積不一定是正確的週期
斷言:相容聯立條件的解構成模 的單一個類。對 、,真正的週期是 ,不是 。14 和 38 都是解,兩者相差 24,卻不是模 48 同餘。若只說 ,便漏掉有效解。模數 恰好在 時才正確。
乘積環的觀點
定理 7.1.7
(中國剩餘同構)
當 互質時,映射
是環同構。
證明
(檢查代表元、運算及雙射)
若 ,則兩者分別模 同餘,所以映射不依賴代表元。模整數化簡與加法、乘法及單位元相容,故映射按分量保留這些運算。
核由同時被 整除的代表元所屬類構成。互質性迫使它們被 整除,因此核只有零類,映射為單射。選擇子構造為每一對目標剩餘類提供整數,故映射為滿射。因此它是環同構。
乘積環按分量運算。在模 20 的例子中, 對應 , 對應 。兩者之和模 20 是 1,乘積是 0,各自平方不變。它們是商環中的選擇子;它們本身不必等於整數 0 或 1。
常見錯誤
(同構需要互質的模數)
對不互質的模數,同一公式仍定義環同態,但它既非單射也非滿射。取 、:映射 把 送到 ,所以核非零( 的倍數給出大小為 2 的核),而像只有 24 個元素。 不可能由任何整數得到,因為第一個分量迫使 為奇數,第二個分量迫使它為偶數。此時不能聲稱每對剩餘類都可達。
練習與解答
快速檢查
(解 、。)
兩個模數互質,所以預期得到模 的一個類。
解答 · 答案
19 滿足兩式;3、5 互質,完整解為 ,亦即 。
快速檢查
(解 、。)
先把餘數之差與最大公因數比較。
解答 · 答案
差 4 可被最大公因數 2 整除。14 是解,所有解為 ,。
快速檢查
( 和 可同時成立嗎?)
看奇偶性。
解答 · 答案
不可。餘數之差 1 不能被最大公因數 2 整除;兩式亦要求相反奇偶性。
快速檢查
(驗證模 20 的 和 確實是選擇子,並用它們重建餘數為 、 的類。)
把每個選擇子分別模 和模 化簡。
解答 · 答案
它們模 的餘數對為 、。而且 、、、。因此 給出餘數 2、3 對應的類。
算術和代數表達相同的結構:選擇子構造組合後的類,互質性則使每對分量剩餘類恰好對應模乘積的一個類。