第十三冊 v0.2 · 網站閱讀版

第10章 數論綜合與證明比較

本章小節
  1. 10.1 同一題先判斷要構造、排除,還是推出矛盾
  2. 10.2 四個例題
  3. 10.3 練習
  4. 10.4 完整解答

10.1 同一題先判斷要構造、排除,還是推出矛盾

要證明有解,可直接構造一個並代回,再用週期或公因數說明是否已列完。要證明無解,可先取模,檢查假定的整數解會不會產生不可能的餘數。餘數矛盾足以排除;沒有矛盾只表示通過這一關,不能當作已有原題的解。

反證也常從『假設有解』出發,但要說清矛盾在哪個量出現。例如,若非零整數 a、b 滿足 a²=2b²,便要求同一整數的 2 賦值同時為奇數和偶數,矛盾不依賴先試多少組 a、b。又如假設所有質數已列完,構造乘積加 1 迫使出現新的質因數。構造和反證可以在同一份證明中合作。

習慣留下三項東西:假設(數的範圍、模數與可逆性)、驗證(把構造的值代回,或找出確切矛盾)、邊界(只證必要或已證充分)。前九章的最小回返、平方配對和因數格都依賴各自前提;不要把有限試驗、證明了的定理與未測的猜想寫成同一件事。

平方模 4 只能是 0、1,兩平方相加只能是 0、1、2,無法得到 3。
圖19|平方模 4 只能是 0、1,兩平方相加只能是 0、1、2,無法得到 3。

10.2 四個例題

例題1 用餘數排除整數解

偶數平方是 4 的倍數;奇數 (2k+1) 的平方為 4k(k+1)+1。因此兩個平方的和模 4 只可能是 0、1、2。2027=4×506+3,不可能是兩個整數平方的和。

例題2 乘積加一保證新質因數,不保證質數

假設全部質數只有 p₁,…,pᵣ。令 N=p₁⋯pᵣ+1>1,N 有質因數,但每個 pᵢ 對 N 都餘 1,故 N 的任何質因數不在原清單,矛盾。方法不要求 N 本身是質數;例如從 2、5、11 得 111=3×37。

例題3 用構造和週期證明全解

求 x≡1(mod 4)、x≡2(mod 9)。令 x=1+4t,需 4t≡1(mod 9)。4×7=28≡1,故 t≡7,得 x=29+36k。29 除以 4、9 分別餘 1、2;週期 36 給全部解。

要證存在可構造並代回;要證不可能可找同餘或賦值矛盾;通過一個模數只表示尚未被排除。
圖20|要證存在可構造並代回;要證不可能可找同餘或賦值矛盾;通過一個模數只表示尚未被排除。

例題4 同一質因數的指數不能同時奇偶

若 √2=a/b,a、b 可取正整數,故 a²=2b²。左側 v₂ 值是 2v₂(a),偶數;右側是 1+2v₂(b),奇數。相等就要求同一個整數有兩個不同奇偶性的賦值,故 √2 不可能是有理數。

10.3 練習

  1. B13-C10-Q01 只用模 4 判斷 79 能否寫成兩平方和。
  2. B13-C10-Q02 6 通過模 4 的必要條件,是否真的可以寫成兩平方和?
  3. B13-C10-Q03 列出 2、3、5,取乘積加一;所得數能被它們整除嗎?
  4. B13-C10-Q04 例題中的 111 是合數,會破壞新質數的論證嗎?
  5. B13-C10-Q05 構造 x≡−1(mod 3)、x≡1(mod 5)的全解。
  6. B13-C10-Q06 證明 x≡1(mod 2)和 x≡0(mod 4)無共同解。
  7. B13-C10-Q07 證明 n²≡1(mod 4)與 n 是奇數互相推出。
  8. B13-C10-Q08 用 3 賦值證明 √3 不是有理數。
  9. B13-C10-Q09 ax≡0 可以直接推出 x≡0 嗎?附條件或反例。
  10. B13-C10-Q10 前幾個 n 令 n²+n+41 都是質數。用一個反例檢查『所有非負整數 n 都如此』。

10.4 完整解答

Q01

79=4×19+3,餘 3;兩平方和的可能餘數只有 0、1、2,因此不能。

Q02

不能。6 模 4 餘 2,沒有被此測試排除;但兩平方都不得超過 6,只能取 0、1、4,沒有兩個能加成 6。這說明通過只是一項必要條件。

Q03

2×3×5+1=31。每個清單內的質數皆整除 30,故 31 除以每一個都餘 1。

Q04

不會。論證需要的是它的一個質因數不在清單,而不是 111 自己是質數。3 和 37 都不在當時列出的 2、5、11。

Q05

令 x=1+5t;模 3 得 1+2t≡2,所以 2t≡1,t≡2。故 x=11+15k;11 確實模 3 餘 2、模 5 餘 1。

Q06

模 4 餘 0 的整數一定被 2 整除,模 2 只能餘 0,與餘 1 矛盾。直接用範圍比試數更快。

Q07

奇數帶入 (2k+1)² 餘 1;偶數 2k 的平方餘 0。整數非奇即偶,所以若平方餘 1 必為奇數。

Q08

若 √3=a/b,正整數 a、b 滿足 a²=3b²。取 v₃ 得 2v₃(a)=1+2v₃(b),一偶一奇,不能相等。

Q09

若 gcd(a,m)=1,兩側乘反元素便可。若條件缺失不行,例如 2×3≡0(mod 6),3 卻不同餘 0。

Q10

取 n=40,得 40²+40+41=1681=41²。它有正因數 41,且 1<41<1681,故原命題為假。