能否指定質數的餘數?
證明質數有無窮多個時,我們可假設有一份有限清單,再構造一個不被清單上任何質數整除的數。更細緻的問題是:除以四有指定餘數的質數,是否也有無窮多個?這裏證明餘數為三的情況。
論證只用整除、質因數分解和模四餘數;它是這些方法的應用,並非證明每個等差數列都含有無窮多個質數。
定義
(模四同餘)
對整數 ,若 整除 ,寫作 。每個整數都恰與 其中一個模四同餘,那個數就是它的餘數。同餘式可以相乘:若 且 ,則 ,因為 。
奇數除以四的餘數是一或三。下面的引理提供構造所需的質因數。
引理
(大於一的整數必有質因數)
若整數 ,則必有某個質數整除 。
證明
(大於一的最小因數是質數)
的大於一的因數所成的集合非空,因為 屬於其中,所以有最小元 。若 不是質數,可寫 ,其中 。於是 整除 ,因而整除 ,且 ,與 的最小性矛盾。所以 是 的質因數。
把引理反覆用於餘下的因子,可知每個 都是質數的乘積,重複的因數也計算在內。
為甚麼餘數三能保證所需的質因數?
定理
(餘三的奇數有餘三的質因數)
若 且 ,則 至少有一個質因數 滿足 。
證明
(餘一因數的乘積仍餘一)
由 知 是奇數,所以其質因數都不是 2。每個質因數都是奇數,模四餘一或餘三。把 分解為質數乘積,重複因數也計算在內。若所有質因數都模四餘一,逐個因數把同餘式相乘,可知它們的乘積也模四餘一。這個乘積就是 ,與 矛盾,因為 不整除 。因此至少一個質因數餘三。
證明透視
餘數定理的每個假設用在哪裏
這個論證其實是逆否命題:質因數全都模四餘一的數,本身也模四餘一,所以模四餘三的數不可能只有這樣的因數。有三個假設承擔了重量。第一, 已迫使 為奇數,排除了質數 2;2 是唯一餘數既非一也非三的質數,若不排除,二分的情形就會多出第三個餘數類。第二,同餘式可相乘是推動論證的機制:它把因數的性質傳給乘積,並要求分解是有限的,這就是要計算重複因數的原因。第三, 保證存在至少含一個質數的分解;整數 模四餘三,卻沒有質因數。
結論只是存在性的:證明說明了並非所有因數都餘一,對其餘因數則沒有任何說明。
常見錯誤
(餘三的數,其質因數未必全都餘三)
定理沒有說 的每個質因數都餘三。例如 ,但質因數 13 模四餘一;它也沒有說餘三的數本身必為質數:39 就是合數。能保留下來的只是較弱的結論:至少有一個質因數餘三。
排除每一份有限清單
定理
(模四餘三的質數有無窮多個)
滿足 的質數 有無窮多個。
證明
(同時保留所需餘數並排除清單上的因數)
反設這種質數只有有限多個,全部列為 。清單非空,因為 3 已是其中一個。令
此時 且 。根據上一個定理, 有質因數 。對每個清單上的 ,由於 ,
因此 不整除 ,特別地 不等於任何已列質數。但 是模四餘三的質數,與清單已列盡所有此類質數矛盾。所以任何有限清單都不可能列盡它們。
的兩個作用不同,缺一不可: 保證有一個所需種類的質因數; 排除每個已列質數。證明沒有預先算出 ,也沒有假設 是質數。
證明透視
為甚麼構造中的因數四和符號都不能少
這個證明的形狀和證明質數有無窮多個的常見論證相似,卻不能照搬。那個論證中的數 模四的餘數不受控制,而上面的餘數定理只在 時才有用。因數 4 解決了這一點:不論 是甚麼, 都是四的倍數,所以 。在樣本 中,,所以光用 本身得不到餘數三。
減一的負號還有第二個作用:它使 模每個已列質數都餘 ,這是非零餘數,因此沒有已列質數整除 。使矛盾成立的一步是兩者的結合:質數 由餘數定理保證存在,又因為每個已列質數都使 餘 ,所以 不在清單上。單靠其中一個都不夠。
例題
(構造出的數可以是合數)
以樣本質數 構造
其中 、;71 是不在樣本清單上的質數。因為 ,只需檢查可能的質因數 ,便知 71 是質數。雖然 923 是合數,它仍有新的所需質因數 71。
有限樣本不等於假設這些就是所有此類質數。一般反證法假設有一份完整的有限清單,再對那份假設清單使用構造。
例題
(找出餘三的質因數)
取 。由 知 。分解得 ,三個質因數模四的餘數依次為 。餘數之積 ,與定理相符,而 就是定理所說的那個質因數。這裏三個質因數中只有一個餘三。
最小的情形是 :它本身是質數,所以 ,無需再找別的質因數。
例題
(構造出的數本身是質數)
取樣本清單 ,則 ,。因為 ,只需試 :83 是奇數,數字和 不是 3 的倍數,個位不是 0 或 5,而 。所以 83 是質數。又 ,且 83 不在清單 上。
這時新的質數就是 本身,定理中的質因數 就是 。這一情形與合數的情形 由同一個證明處理;證明從不判斷究竟屬於哪一種。
反例模式
改變符號會失去餘數保證
命題:把 改為 ,同一論證仍能得到不在清單上、模四餘三的質數。用樣本清單 檢驗,此時 ,。兩個質因數都模四餘一(,),而且 。兩者都不餘三,所以命題不成立:這個數得不到所需種類的質數,無論在不在清單上。
這不與定理矛盾。85 模四餘一,不在餘數定理的假設之內。補救方法是回到原來的構造:同一清單下, 是質數,且餘三。
常見錯誤
(假設構造出的數是質數)
很容易寫出「 是不在清單上、模四餘三的質數」。 的例子說明這一般不成立。證明只需要 有一個餘數合適的質因數,這由餘數定理提供,無需把它算出來。
練習與解答
快速檢查
(樣本清單只有 3 時,計算 ,找一個新的模四餘三質數。)
取 。
解答 · 答案
,故 。11 是質數,模四餘三,且不等於 3。
快速檢查
(為甚麼任何清單上的 都不能整除 ?)
把 與 比較。
解答 · 答案
整除 ;若也整除 ,便整除兩者之差 ,不可能。等價地,構造出的數模 餘 。
快速檢查
( 是否表示每個質因數都餘三?)
試一個較小的合數。
解答 · 答案
否。 模四餘三,但 13 模四餘一;至少一個所需質因數已足夠。
快速檢查
(為甚麼此證明不能直接改用 ?)
計算它模四的餘數。
解答 · 答案
它模四餘一,所有質因數可以都餘一。取 得 ,兩個因數均非模四餘三。
有效的反證構造要同時具備兩點:產生所需種類的對象,並排除假設清單上的每個對象。