動機
像 這樣的方程要求係數為整數的解,因此普通的除法無法解決它。在有理數範圍內有無窮多個解;在整數範圍內,整除性造成了一種障礙。最大公因數恰好量度了這一障礙。其計算過程亦給出相應的係數,使這一障礙同時成為充分條件。
定義
定義 1.1.1
(整除、最大公因數與質數)
對於整數 ,若存在整數 使得 ,則記 。對於不全為零的 , 是它們的最大正公因數。若兩個整數的 gcd 為 ,則稱它們互質。質數是滿足 且只有正因數 與 的整數 ;大於 而不是質數的整數稱為合數。
要求正性使得 gcd 是唯一的;輸入的正負號無關宏旨。特別地,對於非零的 ,有 。我們把 排除在此處使用的定義之外。整除關係具有遞移性,而 的公因數能整除每一個整數組合 。這一初等觀察正是連繫算術與方程的橋樑。
對於帶正負號的輸入,先取絕對值;若其中一個輸入為零,則另一個的絕對值就是 gcd,並且已經給出了貝祖(Bézout)等式。否則,在開始做除法之前,先把兩個正的絕對值排好次序,並在最後的係數中還原正負號。對於 與 ,帶餘除法給出唯一的整數 ,使得 且 。存在性可取不超過 的 的最大倍數得到。若存在兩個這樣的表達式,相減後會得到 的一個絕對值小於 的倍數,這迫使兩個餘數相等,進而兩個商也相等。
定理/命題
定理 1.1.2
(歐幾里得(Euclid)算法與貝祖等式)
設 為不全為零的整數,並設 。反覆做除法會終止,其最後一個非零餘數等於 。存在整數 使得 。因此,方程 有整數解,當且僅當 。
定理 1.1.3
(歐幾里得引理與唯一分解)
若質數 整除 ,則 或 。每個整數 都是若干質數的乘積,並且其質因數構成的多重集是唯一的。
證明思路
證明
(每次除法保留公因數)
若 ,則一個數同時整除 ,當且僅當它同時整除 。因此每一次歐幾里得除法都保持公因數的集合不變。正的餘數嚴格遞減,所以這一過程會終止。在最後的數對 處,正的公因數恰好是 本身的因數。透過回代,每個餘數、從而 ,都可以表示為原有輸入的整數組合。方程的必要性成立,是因為 整除每一個組合;充分性成立,是因為把 乘以 即可。
證明
(由貝祖等式得歐幾里得引理,再以遞降與約去得唯一分解)
要證明歐幾里得引理,設 。由於 是質數,故 。寫出 並乘以 。若 ,則 與 都能被 整除,所以 。
分解的存在性由強歸納法得到:若 是合數,則寫 ,其中 ,再對這兩個較小的整數做分解。至於唯一性,則比較兩個質數乘積。一側的第一個質數整除另一側的乘積,因此反覆使用歐幾里得引理可知,它等於另一側的某個質數。在整數中約去這個質數,然後重複這一步驟。由於非空的質數乘積大於 ,這一過程會同時耗盡兩個列表。
證明透視
各個假設在唯一分解中的作用位置
正性使得對大小做歸納成為可能。合數的輸入分裂為嚴格更小的正因數,從而給出存在性。質數性與貝祖等式一起給出歐幾里得引理,使得相互競爭的兩個乘積中的因數可以配對。隨後的約去把比較化歸為更短的比較。結論與試除因數被找到的次序無關,因為每一種有效的分解都具有相同的質數重數。
例題詳解
例題 1.1.4
(計算障礙並求出一個解)
以下除法 ,,, 給出 gcd 為 。回代得到
因此 是 的一個解。相反,同一個左端不可能等於 ,因為 。
例題 1.1.5
(描述全部整數解)
由前一個解可得 。兩邊除以 ,得到 。由 互質,推出 。於是每個解都形如
代入即可驗證所有這些數對都是解。這一論證同時證明了不存在其他的解。
例題 1.1.6
(賦值把 gcd 與 lcm 變成逐座標的運算)
對於質數 與正整數 ,令 為 在 的分解中的指數。由於 且 ,它們的 gcd 為 ,它們的最小正公倍數為 。取最小指數得到 gcd;取最大指數得到 lcm。因此,對於正整數 ,有 。
把 gcd 理解為完整的障礙
在「gcd 控制著方程」這句話裏,隱含著兩個斷言。第一,每個可取到的右端都能被 gcd 整除。這是一個必要條件,在運行任何算法之前就已成立。第二,gcd 的每個倍數都是可取到的。這是一個充分性的陳述,需要用到貝祖等式。把這兩個方向分開,可以避免一個常見的邏輯漏洞:找到一個障礙本身並不能證明不存在其他的障礙。
考慮所有能寫成兩個輸入的組合的整數。這個集合包含零,對加法封閉,對取相反數亦封閉。若兩個輸入不全為零,它就包含一個正整數。取其中最小的正元素,記為 。用 去除任何可取到的整數,所得餘數仍是可取到的;由最小性,該餘數必為零。因此,全體可取到的整數恰好就是 的倍數。由於輸入本身是可取到的, 整除這兩個輸入。又由於每個公因數都整除每一個組合,不可能有更大的正公因數。這就給出了貝祖等式的第二個證明,它強調的是全體組合的結構,而不是某個具體的計算。
概念視角結構
用兩種描述看同一個 gcd
按大小關係的定義,是選取最大的正公因數。按組合的描述,是選取可取到的最小正線性組合。上面的論證證明了這兩種描述一致。其中「最大」與「最小」所指的是不同的集合。混淆這兩個集合會使結論聽起來自相矛盾;分清這兩個集合,則能說明這一等價為何有用。
這第二個證明還說明了為甚麼整數在這裏很關鍵。由正有理數組合構成的非空集合不一定有最小元素。在有理數範圍內,把係數除以另一個正整數,就會產生更小的正組合。整數的離散序在這裏起著真正的作用,即使初等的計算掩蓋了這一點。
從一個解到全部解
一個特解固然有用,但它很少是整數方程問題的終點。設兩個係數均非零,gcd 為正,並且已經找到了一個解。把它所滿足的方程與任意第二個解所滿足的方程相減,右端互相抵消,剩下一個齊次方程。兩個係數同除以 gcd,它們就互質了。其中一個約化後的係數必須整除另一個變量的改變量。引入由此得到的整數參數,再代回去。這就是為甚麼例題中的參數是係數除以其 gcd,而不是原來的係數本身。
這些參數的正負號是互相關連的。第一個變量增加約化後的第二個係數時,第二個變量必須減少約化後的第一個係數;否則左端會發生變化,而不是保持不變。因此,快速代入是檢驗所提出的參數化的一個有用方法。它驗證充分性,而互質性的論證則驗證完備性。兩者不可互相取代。
隨後還可以對參數施加額外的約束。例如,若問題要求非負解,則它變成關於單一整數參數的一對線性不等式。如果下界大於上界,那麼即使不加限制的整數解有無窮多個,也不存在非負解。整除性回答的是一條直線是否與整數格點相交;符號約束問的則是這些格點中哪些落在指定的區域內。這兩個問題相關,但並不相同。
為甚麼唯一分解是一個定理
人們很容易把分解看成一種毫無歧義的記法,因為熟悉的計算總是給出同樣的結果。是證明為這種做法提供了依據。存在性用到的是下降到更小的正因數。唯一性用到的則是另一個要素:整除乘積的質數必須整除其中一個因數。沒有這一蘊含,把一個列表中的質數與另一個列表中的質數對應起來的那一步就沒有依據。
還要留意,一個列表中的質數如果整除另一側的某個質數,它就必須等於那個質數。二者都是正質數,所以第二個質數的正因數只有 與它本身。當把分解的論證推廣到不可約元與質元可能不同的情形時,這一小步就很重要。這裏並不假定任何這樣的推廣;整數情形下的證明在其所述的範圍內是完整的。
一個實際的推論是用指數來判斷整除。對於正整數,一個數整除另一個數,當且僅當第一個數中每個質數的指數都不大於第二個數中對應質數的指數。正向的推導由對商做分解得到。反向的推導則透過指數相減來構造商,而所有這些差都仍然非負。這樣便是證明,而不只是暗示了 gcd 與 lcm 的取最小與取最大法則。
驗證證書比發現證書更容易
設某個計算報告了一個正的 gcd 候選值,以及把它表示為輸入組合的兩個係數。要驗證這個答案,需檢查候選值整除每個輸入,並檢查線性組合的等式。第一項檢查說明候選值是一個公因數。第二項檢查說明每個公因數都整除候選值。二者合起來就推出它是最大的。僅僅給出一個公因數,或者僅僅給出一個組合,都只提供了證書的一半。
即使算法是由軟件實現的,這種驗證方式也同樣有用。餘數表中的抄寫錯誤,也許很難透過逐個檢查商而發現,但最終的證書只有兩個整除性檢查和一個精確的等式。數學證明解釋了為甚麼這些小小的檢查就足夠了;它不要求我們信任整個計算的過程。
思想史
同一化歸的較早表述
在《幾何原本》第七卷命題 2 中,歐幾里得透過反覆相減來處理最大公度,並透過餘數來追蹤公度。現代的商與餘數記法把反覆的相減歸併為一步。這是與現存的一種書面表述所作的比較,而不是關於首次發現的斷言。
常見錯誤
常見錯誤
(公因數不一定是最大公因數)
gcd 不是隨便某個公因數: 同時整除 與 ,但它不是它們的 gcd。 也並不意味著 有唯一的解;它保證的是解的存在。必須保留整數參數,才能描述全部的解。
常見錯誤
(互質不等於質數)
另一個似是而非的說法是, 互質就使得它們各自是質數。互質只是說它們的質因數集合不相交: 與 就是互質的合數。使用唯一分解時,要指明是正整數,或者先把符號分離出去; 除了其正的質因數之外,還需要一個因子 。
反例模式
歐幾里得引理需要質數除數
命題:若 ,則 或 。取 、、: 被 整除,但 且 。證明在第一步便失效: 並不推出 ,事實上 。若把合數除數當作質數來處理,引理和唯一性的論證都會失效。修正後的敍述是對質數 成立的歐幾里得引理,以及它的互質版本:若 且 ,則 。
總結
歐幾里得算法在縮小輸入的同時保持公因數不變。回代給出 gcd 的證書,並求解相應的整數方程。貝祖等式證明了歐幾里得引理,從而使質因數分解唯一,並把整除性問題轉化為指數的比較。
練習
快速檢查
(求 的全部整數解。)
在引入參數之前,先計算 gcd 並求出一個解。
解答 · 答案
由於 且 ,故 。一個解為 。把齊次的差方程除以 ,得到 。於是對 ,有 ,。每一個數對都是解,而 互質則證明了完備性。
快速檢查
(證明:若 且 ,則 。並在去掉互質條件時給出一個反例。)
這裏 是整數,且 。
解答 · 答案
取 使得 。乘以 得 。假設 ,則右端兩項都能被 整除,因此 。若沒有互質條件,取 :,但 。
快速檢查
( 有整數解嗎? 呢?在有解的情況下給出一個解。)
利用第一個例題算出的 gcd。
解答 · 答案
gcd 為 。由於 ,第一條方程沒有整數解。由於 ,把 乘以 ,便得到第二條方程的解 ;驗算:。