The Legendre Symbol

我們已經把解一般的二次 congruence equation 一步一步的化簡到解 x² $\equiv$ a(mod p), 其中 p 為奇質數且 p$\nmid$a 的情形. 這裡我們將探討何時 x² $\equiv$ a(mod p) 有解. 至於若有解如何找解, 我們留待下一章學習更多方法後再處理.

由於我們只關注 x² $\equiv$ a(mod p) 何時有解, 何時無解, 我們介紹一個符號稱 (Legendre symbol) 來表示其有解或無解.

Definition 5.3.1   給定奇質數 p 以及 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a. 若 x² $\equiv$ a(mod p) 有解, 我們稱 a 是一個 quadratic residue modulo p 並以 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = 1 表示之. 反之, 若 x² $\equiv$ a(mod p) 無解, 我們稱 a 是一個 quadratic nonresidue modulo p 並以 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$=-1 表示之.

首先要注意的是 Legendre symbol 不要和分數搞混. 在本講義中的分數如三分之二的平方我們會用 (${\dfrac{2}{3}}$)² 或 (2/3)² 這兩種方法表示, 括號比較小. 而 Legendre symbol $\left(\vphantom{\dfrac{{2}}{\,{3}\,}}\right.$${\dfrac{{2}}{\,{3}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{3}\,}}\right)$ 的括號比較大. 另外依定義 Legendre symbol 的分母一定是一個奇質數且分子一定和分母互質 (有的書規定不同, 這裡為了不讓同學搞混我們嚴格如此規定). 例如在本講義中 $\left(\vphantom{\dfrac{{5}}{\,{6}\,}}\right.$${\dfrac{{5}}{\,{6}\,}}$$\left.\vphantom{\dfrac{{5}}{\,{6}\,}}\right)$ 或 $\left(\vphantom{\dfrac{{6}}{\,{3}\,}}\right.$${\dfrac{{6}}{\,{3}\,}}$$\left.\vphantom{\dfrac{{6}}{\,{3}\,}}\right)$ 這樣的符號是沒意義的 .

接下來我們來看 Legedre symbol 直接依定義所得之性質.

Lemma 5.3.2   假設 p 是一個奇質數且 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a.

1. $\left(\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right.$${\dfrac{{a^2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right)$ = 1.
2. 若 b $\in$ $\mathbb {Z}$ 滿足 b $\equiv$ a(mod p), 則 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = $\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$${\dfrac{{b}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$.

証 明. (1) 要判斷 a² 是否為 quadratic residue modulo p, 也就是要判斷 x² $\equiv$ a²(mod p) 是否有解. 然而很容易知道 x = a 是 x² $\equiv$ a²(mod p) 的解, 故知 $\left(\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right.$${\dfrac{{a^2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right)$ = 1.

(2) 要判斷 b 是否為 quadratic residue modulo p, 也就是要判斷 x² $\equiv$ b(mod p) 是否有解. 然而依假設 b $\equiv$ a(mod p) 故要解 x² $\equiv$ b(mod p) 就等同於解 x² $\equiv$ a(mod p). 故知 $\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$${\dfrac{{b}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$ = $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$. $\qedsymbol$

其實 x² $\equiv$ a(mod p) 要不然有解要不然就無解. 所以若僅將 Legendre symbol 看成只是一個符號表示有解無解就太小看它了. 若要定符號, 我們也可以將有解定為 1 無解定為 0, 或其他相異的兩個數, 為何要將有解定為 1 無解定為 -1 呢? 說實話若僅想用兩個數字來表示有解或無解的情況, 那真的是怎麼定值都可以, 然而如此一來這樣的符號頂多僅讓我們方便表達有解或無解的情況, 沒有什麼太大的意義. Legendre symbol 之所以要將有解定為 1 無解定為 -1, 主要是我們可以將它們看成整數的 1 和 -1 來做乘法運算. 其原因就是下面這一個定理.

Theorem 5.3.3 (Euler's Criterion)   假設 p 是一個奇質數且 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a.

1. 若 x² $\equiv$ a(mod p) 有解, 則 a^{(p - 1)/2} $\equiv$ 1(mod p).
2. 若 x² $\equiv$ a(mod p) 無解, 則 a^{(p - 1)/2} $\equiv$ - 1(mod p).

証 明. (1) 若 x² $\equiv$ a(mod p) 有解且 x = c 為其一解, 即 c² $\equiv$ a(mod p). 此時

a^{${\frac{p-1}{2}}$} $$\equiv$$ (c²)^{${\frac{p-1}{2}}$} $$\equiv$$ c^{p - 1}(mod p).

由於 a 和 p 互質, 所以 x² $\equiv$ a(mod p) 之解 c 亦與 p 互質. 因此利用 Fermat's Little Theorem (3.3.4) 知 c^{p - 1} $\equiv$ 1(mod p), 故得證 a^{(p - 1)/2} $\equiv$ 1(mod p).

(2) 考慮 S = {1, 2,..., p - 1} 這一個 reduced residue system modulo p. 對任意 i $\in$ S, 由於 i 和 p 互質, 故由 Theorem 4.3.3 知 ix $\equiv$ a(mod p) 在 modulo p 之下有唯一解. 由於 a 和 p 互質, 故知其解必也與 p 互質. 換句話說, 給定 i $\in$ S 必存在唯一的 j $\in$ S 滿足 ij $\equiv$ a(mod p). 要注意此時 j$\ne$i, 否則會得到 i² $\equiv$ a(mod p), 也就是說 x = i 是 x² $\equiv$ a(mod p) 的一個解, 此與 x² $\equiv$ a(mod p) 無解的假設相矛盾. 另一方面也要注意因為 jx $\equiv$ a(mod p) 在 modulo p 之下其解唯一且已知 x = i 為其一解, 所以不可能找到另一個 i' $\in$ S 使得 i'j $\equiv$ a(mod p). 因此對於 S 中的元素, 我們可以將之兩兩配對, 也就是對任意 i $\in$ S 將 i 和滿足 ij $\equiv$ a(mod p) 唯一的 j $\in$ S 相配對. 如此一來我們共有 (p - 1)/2 對. 由於每一對相乘在 modulo p 之下和 a congruent, 故可得

(p - 1)! = 1 ^. 2 ^... p - 1 $$\equiv$$ a^{${\frac{p-1}{2}}$}(mod p).

不過 Wilson's Theorem (3.4.3) 告訴我們 (p - 1)! $\equiv$ - 1(mod p), 故得證 a^{(p - 1)/2} $\equiv$ - 1(mod p). $\qedsymbol$

如果大家不健忘的話, 當初在證明 Wilson's Theorem 我們是將 S = {1,..., p - 1} 中之元素依 ij $\equiv$ 1(mod p) 來配對. 所以 Wilson's Theorem 和 Euler's Criterion 的證明有異曲同工之妙.

當 p$\nmid$a 時 a^{(p - 1)/2} 在 modulo p 之下之值不是 1 就是 -1. 這是因為若令 b = a^{(p - 1)/2}, 則 b² = a^{p - 1} $\equiv$ 1(mod p), 也就是說 x = b 為 x² $\equiv$ 1(mod p) 之一根. 因此由 Lemma 3.4.2 知 b $\equiv$ ±1(mod p). 因此, 給定 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a, 我們可以由 a^{(p - 1)/2} modulo p 為 1 或 -1 來判斷 x² $\equiv$ a(mod p) 是否有解. 例如, 若 a^{(p - 1)/2} $\equiv$ 1(mod p) 而又 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = - 1, 則因 x² $\equiv$ a(mod p) 無解由 Theorem 5.3.3 知 a^{(p - 1)/2} $\equiv$ - 1(mod p). 這會造成 1 $\equiv$ - 1(mod p) 即 p| 2 的矛盾. 因此我們知, 若 a^{(p - 1)/2} $\equiv$ 1(mod p), 則 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = 1. 同理, 若 a^{(p - 1)/2} $\equiv$ - 1(mod p), 則 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = - 1. 這就是 Legendre symbol 取 1 和 -1 為值的理由. 我們有以下之結論.

Corollary 5.3.4   假設 p 是一個奇質數且 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a. 則

$$\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$$$${\dfrac{{a}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$ $$\equiv$$ a^{${\frac{p-1}{2}}$}(mod p).

所以今後我們要知道 x² $\equiv$ a(mod p) 有解或無解, 只要去算 a^{(p - 1)/2} 除以 p 的餘數是 1 或 p - 1. 若餘數是 1 則有解, 若餘數是 p - 1 則無解. 不過這個方法在實際狀況下仍很費事, 因為要計算 a^{(p - 1)/2} 一般來說當 p 很大時仍很很麻煩. 不過這個 criterion 在證明一般抽象的定理時就很管用了. 我們有以下有關 Legendre symbol 的重要性質.

Proposition 5.3.5   假設 p 是一個奇質數且 a, b $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a 且 p$\nmid$b. 則

$$\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$$$${\dfrac{{ab}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$$ = $$\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$$$${\dfrac{{a}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$$$\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$$$${\dfrac{{b}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$$.

証 明. 由 Corollary 5.3.4 知

$$\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$$$${\dfrac{{ab}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$$ $$\equiv$$ (ab)^{${\frac{p-1}{2}}$} = a^{${\frac{p-1}{2}}$}b^{${\frac{p-1}{2}}$} $$\equiv$$ $$\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$$$${\dfrac{{a}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$$$\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$$$${\dfrac{{b}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$$(mod p).

由於 $\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$${\dfrac{{ab}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$ 和 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$${\dfrac{{b}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$ 之值要不是 1 就是 -1, 所以他們在 modulo p 之下同餘表示必相等(否則又會得 p| 2 之矛盾). 故得 $\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$${\dfrac{{ab}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$ = $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$${\dfrac{{b}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$. $\qedsymbol$

Proposition 5.3.5 可以推出很令人吃驚的結果. 例如假設 x² $\equiv$ a(mod a) 和 x² $\equiv$ b(mod p) 皆有解且設 x = c 和 x = c' 分別為其一解. 那麼我們很容易推得 x² $\equiv$ ab(mod p) 必有解. 因為 x = cc' 就是其中之一解. 不過若 x² $\equiv$ a(mod a) 和 x² $\equiv$ b(mod p) 其中有一個無解或是皆無解, 那們我們就很難利用解方程式的方法來處理 x² $\equiv$ ab(mod p) 是否有解了. 不過若利用 Proposition 5.3.5, 我們很快的便知若 x² $\equiv$ a(mod p) 有解但 x² $\equiv$ b(mod p) 無解 (即 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ = 1, $\left(\vphantom{\dfrac{{b}}{\,{p}\,}}\right.$${\dfrac{{b}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{b}}{\,{p}\,}}\right)$ = - 1), 則 x² $\equiv$ ab(mod p) 便無解 (因為此時 $\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$${\dfrac{{ab}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$ = 1×(- 1) = - 1). 更令人訝異的是若 x² $\equiv$ a(mod p) 和 x² $\equiv$ b(mod p) 皆無解, 我們可以知 x² $\equiv$ ab(mod p) 必有解 (因為此時 $\left(\vphantom{\dfrac{{ab}}{\,{p}\,}}\right.$${\dfrac{{ab}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{ab}}{\,{p}\,}}\right)$ = (- 1)×(- 1) = 1). 這個結果是很難用有解無解這樣的角度來判斷的.

Proposition 5.3.5 另一個好處是對任意整數 a 我們可以分解成 a = (- 1)^m2^n₀q₁^{n₁ ...} q_r^n_r, 其中 q_i 為奇質數 (且 p$\ne$q_i 因 p$\nmid$a), m $\in$ {0, 1}, n_i$\ge$ 0. 因此可得

$$\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$$$${\dfrac{{a}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$ = $$\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$$$${\dfrac{{-1}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)^{m}_{}$$$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)^{n_0}_{}$$$$\left(\vphantom{\dfrac{{q_1}}{\,{p}\,}}\right.$$$${\dfrac{{q_1}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{q_1}}{\,{p}\,}}\right)^{n_1}_{}$$ ^... $$\left(\vphantom{\dfrac{{q_r}}{\,{p}\,}}\right.$$$${\dfrac{{q_r}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{q_r}}{\,{p}\,}}\right)^{n_r}_{}$$.

也就是說給定一奇質數 p, 我們只要知道 $\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$${\dfrac{{-1}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)$, $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$ 和 $\left(\vphantom{\dfrac{{q}}{\,{p}\,}}\right.$${\dfrac{{q}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{q}}{\,{p}\,}}\right)$ (q 為任意與 p 相異的奇質數) 之值, 那麼對任意與 p 互質的整數 a, 就可以算出 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ 之值了.

我們從原來要了解一般二次的 congruence equation 解的情形, 一路化簡到現在只要了解 x² $\equiv$ - 1(mod p), x² $\equiv$ 2(mod p) 和 x² $\equiv$ q(mod p) (其中 q 是與 p 相異的奇質數), 這三種簡單形式的情形. 這就是解決數學問題常遇到的由繁化簡的過程, 值得大家細細體會其中的演化. 另一件有趣的是 Legendre symbol 和 Euler's Criterion 幫助我們將一個原本解二次 congruence equation 的問題換成另外一個和解方程式完全無關的方法來處理. 接下來我們就是要利用這樣的方式來處理 $\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$${\dfrac{{-1}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)$, $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$ 和 $\left(\vphantom{\dfrac{{q}}{\,{p}\,}}\right.$${\dfrac{{q}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{q}}{\,{p}\,}}\right)$, 而不再直接探討 x² $\equiv$ - 1, 2, q(mod p) 有解或是無解.