帶餘除法與貝祖(Bézout)等式(3.2 與 3.5 單元)用整除描述整數。同餘把這些資訊重新整理,使有關餘數的問題可以用普通代數解決。本單元說明模 同餘與加法、乘法相容,準確判斷一個剩餘類何時可逆,完整求解每個線性同餘式 ,並證明兩個經典結果:中國剩餘定理和費馬(Fermat)小定理。全文中 代表正整數。
同餘是等價關係
定義 3.6.1
(模 n 同餘)
對整數 ,若 ,記 。等價地, 與 除以 的餘數相同。等價類稱為剩餘類 。
命題 3.6.2
(同餘與加法、乘法相容)
模 同餘是 上的等價關係;並且若 且 ,則 且 。
證明
(把差明確寫出來)
自反性、對稱性、傳遞性分別來自:; 蘊含 ; 且 蘊含 。對運算,寫 、。則 ,而 。
上述結果說明剩餘類的加法與乘法是良定義的。因此任何整係數多項式表達式,都可以先把每一項化為模 的餘數再計算。
常見錯誤
(消去不可逆的因子)
消去律不一定成立。由 ,只有在 時才能推出 ;一般只能得到 。例如 (因為 ),但 ;這裏 ,正確的結論是 。
逆元與消去
定義 3.6.3
(模 n 可逆)
若存在整數 使 ,稱整數 模 可逆。
定理 3.6.4
(與 n 互質的剩餘類恰好可逆)
整數 模 可逆當且僅當 。若 都是逆元,則 。若 且 ,則 。
證明
(貝祖等式給出逆元)
若 ,則對某個 有 ,所以 與 的任何公因數都整除 。反過來,若 ,貝祖等式給出整數 使 ,因此 。唯一性:。消去律只需把 乘以 的逆元。
證明是構造性的:擴展歐幾里得(Euclid)算法能給出 。
線性同餘式
定理 3.6.5
(求解線性同餘式)
設 。同餘式 有解當且僅當 。若 ,寫 、、。則解恰為滿足 的整數,其中 是 的任一解;模 時恰有 個解類:。
證明
(化為互質的同餘式)
若 是解,則 ,所以 被 整除。反過來設 。把 除以 可知 等價於 。此時 ,因為若有公因數 ,則 是 與 的公因數且大於 。由逆元定理, 有模 的逆元 ,而 當且僅當 。與 模 同餘的整數,在模 下恰分成 個類。
常見錯誤
(算錯解的個數)
可解的線性同餘式在模 下有 個解類,不是一個。只有 時才恰有一個。
中國剩餘定理
定理 3.6.6
(兩個模數的中國剩餘定理)
設 為正整數且 , 為整數。則方程組
有解,而且任何兩個解模 同餘。
證明
(由貝祖等式構造解)
貝祖等式給出 。令 。由於 且 ,得 ;對稱地 。若 與 是兩個解,則 且 。寫 。則 而 ,所以 (由貝祖等式, 被 整除),因此 。
沒有互質性,論證的兩半都會失敗;下面的錯誤說明,連解的存在性也可能不成立。
常見錯誤
(模數不互質時使用中國剩餘定理)
方程組可能無解: 與 互相矛盾,因為前者迫使 為奇數,後者迫使 為偶數。
費馬小定理
定理 3.6.7
(費馬小定理)
若 是質數且 ,則 。因此對每個整數 都有 。
證明
(乘以 a 會置換非零餘數)
考慮 個整數 。其中沒有一個被 整除,因為對 有 。它們模 兩兩不同餘:若 ,消去 (由逆元定理)得 ,故 。因此它們的餘數恰好是 的某個排列,從而
與 互質,因為每個因子都是,故消去它得 。若 ,則 與 都 。
證明透視
為何非零餘數的乘積可以消去
關鍵一步是用兩種方式計算同一個乘積 :一次直接計算,一次把每個因子都乘以 之後計算,而後者只是重新排列了餘數。重排的斷言有兩半:倍數 仍在非零餘數之中,因為 是質數,既不整除 也不整除 ;它們兩兩不同,因為 可逆。 是質數用來使 全部可逆;合數模數會有不可逆的餘數,論證便到此為止。最後消去 也是同一原因。結尾關於 的一句是獨立的,因為置換需要假設 。
模數是質數這個假設不能隨便去掉。
反例模式
費馬小定理需要質數模
命題:若 ,則對每個 都有 。取 、,兩者互質。則 ,所以 ,不是 。上面的證明在「使 全部可逆」一步失效: 和 模 不可逆。對合數 ,指數 一般並不適用。
常見錯誤
(對錯誤的數約簡指數)
的指數可以模 約簡(當 時),而不是模 。
例題
例題 3.6.8
(有多個解的線性同餘式)
解 。這裏 整除 ,故有解。除以 :。由於 , 的逆元是 ,所以 。模 的解是 。驗算:,,。
例題 3.6.9
(以歐幾里得算法求逆元)
求 模 的逆元。歐幾里得算法:,,。回代:。故 ,逆元是 。驗算:。除以 的餘數落在 內; 與 模 同餘,但只有 是標準代表。
例題 3.6.10
(中國剩餘定理)
解 、。貝祖等式:,故 、。則 。驗算:,。解為 。
例題 3.6.11
(用費馬小定理計算冪)
計算 。由費馬小定理,。由於 ,得 。
練習
快速檢查
(解 。)
除以 ,模也要一併約簡。
解答 · 引導解答
整除 。除以 得 ,其解為 (因 )。模 的解是 和 。驗算:,。
快速檢查
(證明 無解。)
比較 與右邊的數。
解答 · 引導解答
不整除 ,由線性同餘式定理知無解。直接看, 會給出 被 整除,這不成立。
快速檢查
(求 模 的逆元。)
對 和 做歐幾里得算法並回代。
解答 · 引導解答
歐幾里得算法:,,。則 。所以 ,逆元是 。驗算:。
快速檢查
(解 、。)
找 使 ,再用 。
解答 · 引導解答
這裏 、、、。貝祖等式:,故 ( 的係數)、( 的係數)。則 。解為 。驗算:,。
快速檢查
(求 除以 的餘數。)
用 的費馬小定理。
解答 · 引導解答
,所以 (這就是 的費馬小定理)。因此 ,餘數是 。