動機
一個同餘式只記錄一個剩餘類,但把多個同餘式合併起來並不總是可行。當模數有公因數時,兩個給定的餘數可能在兩個模數都保留的資訊上互相矛盾。即使解存在,把各模數相乘也可能高估真正的週期。
正確的不變量是完整解類:處理了若干約束之後,每一個解而且只有解與某個代表元模某個正週期同餘。擴展歐幾里得(Euclid)算法提供相容性檢驗,並給出合併下一個條件所需的修正量。另有一個質數冪的論證說明,對有限方程組而言,檢查所有兩兩組合也是充分的。
這裏的數學是在精確整數上進行的;證明與算法都不依賴於猜測一小段候選解的範圍。
定義
定義 4.2.1
(同餘與完整解類)
對正整數 ,當 整除 時記 。這一關係與加法和乘法相容。模一不施加任何限制,因為任何整數差都能被一整除。
完整解類 (其中 )恰好指整數 ()。其規範代表元滿足 。線性同餘式是 ,其中 可以是負數或零。
的最大公因數指它們絕對值的正的最大公因數。正整數 的最小公倍數是它們最小的正公倍數,等於 。我們使用整數算法筆記中已經證明的貝祖(Bézout)等式及由係數給出的逆元。空族的最小公倍數約定為一,與空方程組沒有任何限制相符。無需調用模一的逆元:對模一的餘數要求只有一個不受限制的類。
定義 4.2.2
(有限餘數方程組的兩兩相容)
有限族 (每個 )稱為兩兩相容,當且僅當對每一對下標都有
兩兩互質會使這些條件自動成立,但相容並不要求模數互質。
定理/命題
定理 4.2.3
(單個線性同餘式的全部解)
設 。同餘式 有解當且僅當 整除 。若有解,其整數解構成模 的一個類,因此恰好構成模 的 個不同的類。
當 時,代表元可由 乘以 模 的逆元得到。當 時,每個整數都是解,取代表元零即可。
定理 4.2.4
(任意兩個正模數的構造性合併)
方程組 , 有解當且僅當 整除 。若有解,則其解類在模 下唯一。
記 。若 ,利用係數的逆元選取滿足 的 。若 ,取 。則 模 約化後是一個規範的解代表元。該過程需要最大公因數和貝祖係數,而不需要對模數做因數分解。
定理 4.2.5
(兩兩相容對每個有限方程組都是充分的)
對正模數而言,有限餘數方程組有解當且僅當它兩兩相容。有解時,其完整解集是模所有模數的最小公倍數的一個類。逐次應用兩模數合併法即可構造出該類,或正確地拒絕不相容的方程組。
這裏的唯一性是指模最小公倍數的剩餘類唯一,並不意味著只有一個整數解;當模數含有公因數時,也不意味著模乘積唯一。
證明思路或證明
證明
(解單個線性同餘式)
若 能被 整除,則 的每個公因數都整除 ,這就證明了線性同餘式的必要性。當 時,兩邊同除即得等價的同餘式 。約化後的係數與模數互質,故當模數大於一時由貝祖等式逆元存在。相乘得到模 的唯一一個類;反之,該類乘以 後滿足原方程。
若約化後的模數為一,則除後的同餘式不施加條件,所有整數都是解。無論哪種情形,都可把解類寫成 。在 個連續剩餘構成的完整區間內,它恰好有 個不同的值,即加上零到 個 所得的值。這些值之間的差不是 的倍數,除非所加的個數相同。這就證明了解的個數,包括 的情形。
證明
(合併兩個同餘式與逐次求解)
對於兩模數合併,第一個條件的每個解都具有形式 。第二個條件變為 。由線性同餘定理,它恰在所述的最大公因數條件下有解。同除以 得到關於 的方程,其中 互質。它模 的唯一類轉化為 模 的一個類。這同時證明了全部解的唯一性,而不僅僅是所構造代表元的正確性。
對於逐次算法,從模一的代表元零開始。保持已處理的約束恰好具有當前的解類這一不變式。由定理,將其與下一個同餘式合併恰好得到它們的交集;合併失敗意味著該交集為空。因此歸納法證明了接受與拒絕兩方面的正確性。若舊代表元已規範化,且修正量滿足 ,則 已經成立;顯式的最終約化同樣可處理未規範化的輸入餘數。
證明透視
合併不變式包含每一個可能的解
檢驗新代表元的餘數只能確立可行性。代換 以及唯一的係數逆元類還證明了沒有丟失任何其他解類。保持這一反向方向,才使得之後合併失敗時能證明整體不相容,而不只是所選的某個候選失敗。
證明
(以質數冪證明兩兩相容的充分性)
對於兩兩判準,必要性成立,因為一個公共解使每個差 都能被兩個模數的最大公因數整除。我們利用質數冪因子證明充分性。質數是至少為二且正因數只有一和自身的整數。這裏的質因子都取正數。所需的因數分解事實是初等的:存在性可由歸納法得到,把任何合數拆成更小的因數;唯一性由質因數引理得到。該引理由貝祖等式推出:若質數整除一個乘積卻不整除其第一個因數,則它與該因數的最大公因數為一,於是把貝祖等式乘以第二個因數即知它整除第二個因數。重複此論證可在任意兩個相互競爭的分解中找出另一側對應的質數,然後約去即證唯一性。整數一的分解為空。
設 為最小公倍數。對每個在各模數中以最大指數出現的質數冪 ,選取達到該指數的一個下標,並規定相應的模 的餘數。這些質數冪兩兩互質,故反覆使用已證的合併法,可得到模它們乘積 的一個類。
對任一原模數及其每個質數冪 ,它與所選最大指數下標的相容性使其餘數與所選餘數模 一致。因此構造出的整數滿足該原模數的每個質數冪因子,從而滿足它們互質的乘積。它滿足所有原同餘式。若 ,則所有模數均為一,每個整數都成立,結論一致。
最後,兩個公共解之差是每個模數的倍數,從而是每個最大質數冪及其乘積 的倍數。反之,加上 的任意倍數不改變所有同餘式。這就證明了完整解類和有限方程組定理。質因數分解解釋了該判準,但逐次實現並不需要它。
例題詳解
例題 4.2.6
(不可逆的係數仍可能有解)
解 。最大公因數為二,且整除八。兩邊同除得 。由於三是七模十的逆元,。因此模二十的兩個類是二和十二。代入後兩種情形的餘數都是八。試圖求十四模二十的逆元會失敗,但這並不能證明原同餘式無解。
例題 4.2.7
(公因數使週期縮短)
解 與 。它們的最大公因數是三,餘數之差是三,故相容。代入 得 ,因此 。完整解為 。相反,若把五換成四,則餘數之差為二,不能被三整除,因而無解。
例題 4.2.8
(第三個條件改變週期,卻不改變最小代表元)
在這個相容的一對上加入 。把 與它合併。最大公因數是二,差為負十;約化後的修正方程是 ,其解類為零。因此代表元仍為十四,週期變為九十。
三個原模數的乘積是 ,並不是真正的週期。模該乘積有六個解,即 ()。僅有一個正確的代表元並不足以斷言模 唯一。
算法規模與因數分解的作用
先把每個輸入餘數按其正模數規範化。每次合併時,週期是一個最小公倍數,且至多等於已處理模數的乘積。因此其二進制長度至多是這些模數二進制長度之和,至多相差一個常數。修正餘數也可取在其約化模數之內,使所構造的代表元落在新週期之內。
擴展歐幾里得算法與精確算術因此作用於位長受多項式控制的數。逐次相容性求解器不需要枚舉直到週期的整數,而大週期的數值大小並不等於其書寫的輸入長度。兩兩充分性的因數分解證明不應被誤認為在應用基於最大公因數的算法之前必須對每個輸入做因數分解。
概念視角代數
相容性比較的是兩個模數共同保留的資訊
共有的質數冪對未知餘數的同一部分約束了兩次。兩個規定必須在它們共同的解析度上一致。最小公倍數把每個所需的質數指數只保留一次,這解釋了最終的週期。最大公因數能檢測重疊,而無需計算其質因數。
常見錯誤
常見錯誤
(只除係數而不除模數)
不能由 推到 。後者只有一個類 ,因為 是 模 的逆元;它丟失了解 :,但 。在已證的條件 之下,應把係數、右端與模數一起除以 ,得到 ,從而得到模 的兩個類 與 。
常見錯誤
(模數之積不是週期)
對 與 ,解為 ,所以 與 都是解,雖然它們模 不同。互質情形的週期 只在 時正確;一般情形的週期是 。
常見錯誤
(相容不等於互質)
模數 與 有公因數 ,但同一方程組有解,因為 。互質的模數使每一對都相容,但反過來不成立;因此只要 就拒絕方程組,會丟掉有解的方程組。在模一的分支中,約束本已是空約束,不應在那裏選取模逆元。
反例模式
沒有逆元不等於沒有解
同餘式 的係數在模四下沒有逆元,但它的解是全部奇數。除以最大公因數得 。逆元檢驗失敗只說明乘法不是四個剩餘類上的雙射,並不說明其像集不包含所要求的右端。
總結
最大公因數刻劃了單個線性同餘式的可解性,並給出所有剩餘解的個數。同一定理給出非互質餘數的精確合併,保持已處理的完整解類。質數冪相容性證明了所有兩兩一致性檢驗已經足夠,而實際的逐次算法只用最大公因數和逆元,並返回以最小公倍數為週期的結果。
練習
快速檢查
(對正整數 ,分類 的解。包括 的情形,並在有解時數出模 的類的個數。)
應用最大公因數條件,而不要虛構零的逆元。
解答 · 答案
此時 。可解性意味著 。若成立,則每個整數都是解,即模一的單個類,也即模 的恰好 個類。若不成立,則無解。當 時,每個 都能被它整除,每個整數都是解。定理中約化後的模數為一,故直接適用其顯式的空約束分支,無需任何求逆計算。
快速檢查
(解 且 。模乘積 有多少個解類?)
先給出最小週期的完整解類。
解答 · 答案
記 。第二個條件給出 ,從而 。於是 ,。模乘積的兩個類是九和二十一。兩者都滿足兩個原約束,它們共同的十二步週期正是四與六的最小公倍數。
快速檢查
(解 、、。檢查兩兩相容性並驗證一個規範代表元。)
合併兩次,並給出最終的最小公倍數。
解答
兩兩的最大公因數是四、二、六,對應的餘數之差為四、十、六,均按要求可被整除。先合併模八餘三與模十二餘七:代入 得 ,故 。
現令 。最後一個同餘式給出 ,從而 ,。因此 。它模八、十二、十八的餘數分別是三、七、十三。週期七十二是它們的最小公倍數,而六十七落在其規範區間內。