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

第8章 二次剩餘與Legendre符號

本章小節
  1. 8.1 把平方的配對和判準都放在奇質數模下
  2. 8.2 四個例題
  3. 8.3 練習
  4. 8.4 完整解答

8.1 把平方的配對和判準都放在奇質數模下

取奇質數 p。本冊把不為 0 且可寫成 x² 模 p 的類稱為非零二次剩餘;0 也有平方根,但另外算。若 a≢0(mod p),x²≡y²≡a 則 p∣(x−y)(x+y),所以 x≡y 或 x≡−y。兩者不同,因 p 為奇數而 x 非零。非零類的平方因此恰成 (p−1)/2 種。

Legendre 符號記作 (a/p):p∣a 記 0,非零二次剩餘記 1,其餘記 −1。這是三種判定值,不是把 a 除以 p。Euler 判準為 a^((p−1)/2)≡(a/p)(mod p)。要證明非零情形,先平方並用 Fermat,得這個冪的平方同餘 1,故只能是 ±1。若 a=x²,冪是 x^(p−1)≡1。

為何非剩餘必給 −1?在模質數 p 的運算中,每個非零類可逆,乘積為零時至少一因子為零。若多項式有根 r,可用因子定理提出 X−r。對任何另一個根 s,s−r 可逆,因此 s 必是剩下那個多項式的根。反覆提出線性因子便得到,非零多項式的相異根數至多其度數。X^((p−1)/2)−1 已被 (p−1)/2 個非零平方類填滿,不能再有其他根。a≡0 時冪為 0。模合數會出現非零因子的乘積為零,不能搬用配對或根數結論。

模 7 的非零類分成三對相反數;平方結果分別是 1、4、2。
圖15|模 7 的非零類分成三對相反數;平方結果分別是 1、4、2。

8.2 四個例題

例題1 模 7:用三對就列完

(1,6)、(2,5)、(3,4) 是相反的非零配對,平方餘數依次為 1、4、2。故 2 的根是 3 與 4,且 3²−7=2。剩餘 3、5、6 不在非零平方的清單內。

例題2 用判準而不逐次試根

判斷 5 在模 11 是否為二次剩餘。5²≡3,5⁴≡9,5⁵≡9×5=45≡1;(11−1)/2=5,故符號為 1。需要一個根時,可再驗 4²=16≡5,但符號本身不輸出根。

例題3 負號判定和零情形不同

p=5、a=2,判準冪為 2²=4≡−1,故符號 −1,沒有根。若 a=10,則先看 5∣10,符號為 0;這並非非剩餘,而是對應零類。

例題4 模 8 有四個平方根

1²、3²、5²、7² 都同餘 1。偶數平方模 8 只能是 0 或 4,故模 8 的解恰四個。不能用奇質數下的「只有 ±一對」排除其餘兩根。

模 8 中 1、3、5、7 全是 1 的平方根,顯示模合數不受兩根結論限制。
圖16|模 8 中 1、3、5、7 全是 1 的平方根,顯示模合數不受兩根結論限制。

8.3 練習

  1. B13-C08-Q01 列出模 5 的非零二次剩餘。
  2. B13-C08-Q02 (22/11) 的 Legendre 符號是多少?
  3. B13-C08-Q03 用 Euler 判準算 (3/7)。
  4. B13-C08-Q04 算 (2/7),再驗一個平方根。
  5. B13-C08-Q05 判斷 −1 在模 13 是否是二次剩餘。
  6. B13-C08-Q06 判斷 −1 在模 7 是否是二次剩餘。
  7. B13-C08-Q07 解 x²≡9(mod 11)。
  8. B13-C08-Q08 模 9 解 x²≡0。為什麼根數不受二次式度數限制?
  9. B13-C08-Q09 能將本章 Legendre 判準直接用在 p=2 嗎?
  10. B13-C08-Q10 不列出每個平方值,說明模 11 的非零平方類有幾個。

8.4 完整解答

Q01

兩對相反類 1、4 與 2、3,平方同餘 1、4。這已列完 4 個非零類。

Q02

11∣22,所以 22 是零類,依定義符號 0。不是因 22/11 的普通除法得 2 而用 2 判定。

Q03

指數 (7−1)/2=3,3³=27=4×7−1,所以冪同餘 −1,符號 −1。

Q04

2³=8≡1,所以符號是 1。3²=9≡2,故 3 是根;其相反類 4 也是。

Q05

指數 (13−1)/2=6 為偶數,(−1)⁶=1,故 Legendre 符號為 1。

Q06

指數 (7−1)/2=3 為奇數,(−1)³=−1,所以符號 −1、無根。

Q07

先驗 3;其相反類 −3≡8 也是根。因 11 為奇質數、9 非零,不再有第三個根。

Q08

0、3、6 皆是解,其餘類不被 3 整除、平方也不會被 9 整除。模 9 存在非零類 3×3≡0,破壞模質數的根數論證。

Q09

不能。這裡定義限奇質數,(p−1)/2 在 p=2 不是整數,且相反類可能相同。小模數 2 可直接列 0、1 的平方。

Q10

十個非零類每兩個相反類一組,各組有一個平方值。若兩組平方相同,質數引理會讓它們其實是同組,故恰 10/2=5 個。