同餘式保留了部分資訊: 表示 屬於理想 。當同時施加多條同餘式時,是否存在一個元素同時滿足全部條件?這個元素又是否唯一?答案取決於各理想之間如何配合。本節以 MATH2076 筆記中的理想與貝祖(Bézout)工具,推導中國剩餘定理,然後把它應用於整數和多項式。我們考慮的是有單位元的交換環;商環可以是零環。
兩個理想的重構定理
設 為 的理想。它們的和 是一個理想。
定義 5.1.1
(互質理想)
若 ,則稱 的理想 互質(comaximal)。這等價於存在 及 ,使得 。
把和的定義應用於元素 ,便得到這個等價關係:若這個和包含 ,則它包含每個 。以 表示由所有乘積 (其中 、)的有限和所組成的理想;我們總有 。
定理 5.1.2
(兩個理想的中國剩餘定理)
設 為有單位元的交換環 的互質理想。則對任意 ,都存在 使得 且 ,而任何兩個這樣的 之差屬於 。等價地說,映射
是環同構。此外 。
證明
(用貝祖恆等式挑選原像)
考慮映射
由於兩個座標都保持加法、乘法和單位元,所以這個映射亦保持它們。它的核是 :像為 ,當且僅當 同時屬於兩個理想。若 ,這個映射亦是滿射。事實上,選取 、 使得 。那麼 且 ,而 的表現正好相反。對任何所需的配對 ,設
它模 變成 ,模 變成 。只要我們有 的貝祖恆等式,這條公式就是一個算法。
核描述了唯一性:任何兩個解的差都是 的元素。因此 上的誘導映射是定義良好的,因為 的元素在兩個座標中都變成零;由核的計算可知它是單射;由上述構造可知它是滿射。
最後一項:設 如上,且 ,則 。由於 且 ,第一項屬於 ;由於 且 ,第二項亦屬於 。因此 ,配合 ,在互質的條件下便有 。
證明透視
互質性用在哪裏,而且只用在哪裏
互質性恰好在兩處進入。映射 、它的核 ,以及由此得出的唯一性,對任意理想都成立,不需要恆等式 。這個恆等式用來構造選擇器: 模 為 、模 為 , 則相反,於是 在第一個座標讀作 、在第二個座標讀作 ,兩項互不干擾。
最後一段中不顯然的一步是 。它把每一項送進必須包含該乘積的理想: 中 、, 中 、。兩個加項都屬於 ,證明便告完成。乘積公式是由假設推導出來的結果,並非對任意理想都成立的恆等式。下面的反例顯示沒有這個假設時哪裏出錯:唯一性的模是交集而不是乘積,而存在性需要相容條件。
反例模式
互質這個條件不能刪去
斷言:對交換環的任意理想 ,都有 ,且每一對餘數都能取到。取 、。則 ,但 只含 的倍數,所以 ,即 。至於第二部分,取 、,此時 。這裏 ,所以 的像有 個元素,而目標有 個。配對 取不到: 迫使 為偶數,而 迫使 為奇數。補救辦法是假設 ;沒有它時,結論只對相容的配對成立,見理想不互質時的一節。
例題:整數
例題 5.1.3
(模數互質的兩條同餘式)
求所有滿足以下條件的整數 :
由於 ,理想 與 互質。我們可以選取 及 。於是
是一個解。直接驗算得 。其他每個解與 17 的差都是一個同時被 5 和 7 整除的整數,因此被 35 整除;完整答案是 ,。負數代表元,例如 ,描述的是同一個剩餘類。
常見錯誤
(把兩個選擇器調轉)
係數 和 是選擇器,很容易不小心調轉: 必須模 5 等於 1,因為它乘的是所需的餘數 2;而 必須模 7 等於 1,因為它乘的是 3。若角色對調,就會算出 ,它模 是 、模 是 ,兩個餘數正好互換。
例題:多項式
例題 5.1.4
(有理數上模互質的多項式)
在 中,求次數低於 3 並滿足以下條件的多項式:
兩個模互質:。取 及 ,得 。因此
乘積模為 。利用 化簡,得到次數低於 3 的代表元 。驗算兩項要求:它的常數項是 1,而模 時它變成 。所有解都是 ,其中 。多項式除法給出恰好一個次數小於 3 的代表元。
同樣的推理適用於域上互質的多項式 :貝祖恆等式給出 ,而乘積模為 。域這個條件保證了多項式除法和貝祖恆等式成立;引用這個證明時不應略去此條件。
理想不互質時會有甚麼改變?
命題 5.1.5
(兩條同餘式的可解性)
設 為 的理想,。同餘式 與 有解,當且僅當 。若有解存在,所有解之間的差都屬於 。
證明
(把差拆成兩部分)
把 與 相加,得 ,這就是必要性。至於充分性,把 寫成 ,其中 、,並選取 。那麼 且 。兩個解 滿足 且 ,所以 。
因此,互質保證了每一對餘數都相容;但即使理想不互質,個別相容的配對仍然可以存在。
例題 5.1.6
(模 4 與模 6 的相容與不相容配對)
條件 與 是相容的:。整數 9 同時滿足兩者;由於 ,完整的解集是 。相反, 與 是不可能同時成立的:它們的差 不是偶數,所以不在 之中。
練習及完整題解
練習 5.1.7
(解 、,並寫出整數解的完整集合。)
基礎
解答(4)
- 1
寫出模數的貝祖恆等式
由於 ,一個方便的恆等式是 。取 及 ,則 。
- 2
用選擇器組合出解
關鍵一步
。
依據: 模 為 、模 為 ,而 正好相反。
- 3
化簡並驗算
,而 、,所以 且 。另一種做法:由 得 ,4 模 9 的逆元是 7,從而 ,同樣得到 。
- 4
寫出所有解
解之間的差屬於 ,所以所有解為 ,。
練習 5.1.8
(在 中,求所有滿足 及 的 。)
核心
解答(4)
- 1
檢驗相容性
所需餘數的差為 ,由於 ,它屬於 。因此兩條同餘式相容。
依據: 兩個模有公因式 ,所以不互質,須用可解性命題。
- 2
找出一個解
取 。它模 同餘於 1,而 ,所以它滿足第二條同餘式。
- 3
求唯一性理想
關鍵一步
與 的公倍式必須同時被 和 整除,而兩者互質。因此 。
依據: 兩個解之差屬於交集,而不是乘積。
- 4
寫出所有解
練習 5.1.9
(判斷 與 是否有公共解;若有,求出全部解。)
核心
解答(4)
- 1
計算和理想
。
依據: 可解性取決於 ,而 由 生成。
- 2
檢驗相容性
餘數之差為 ,所以有解。
- 3
找出一個解
設 。由 得 ,故 ,即 。取 得 ,而 。
- 4
寫出所有解
由於 ,所有解為 ,。