[數論] Legengre symbol 和 二次互反律

參考資料
李華介 基礎數論 http://math.ntnu.edu.tw/~li/ent-html/node30.html
Squares Modulo p http://www.math.brown.edu/~jhs/MA0042/FRINTNewCh2324.pdf
Proofs of quadratic reciprocity http://en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity
Gauß, Eisenstein, and the "third'' proof of the Quadratic Reciprocity Theorem: Ein kleines Schauspiel
http://math.nmsu.edu/~history/schauspiel/schauspiel.html

在上一篇，我們在文章最後提到了利用 Legendre symbol 去判別二次剩餘的存在性。

二次剩餘定義
For $x,m\neq 0$, $a$ is a quadratic residue mod $m$ if $x^{2}=a$ (mod $m$). Otherwise, $a$ is a quadratic nonresidue.

Legendre symbol定義
令 $p$ 是奇質數，$a$ 是整數，$(a,p)=1$。 Legendre Symbol $\left ( \frac{a}{p} \right )\overset{def}{=} a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$.

我們利用 Legendre symbol 是完全積性函數的特性，「把 $a$ 拆解成較小的數字相乘，再去計算其 Legendre Symbol 的值」。下面將說明完整的拆解及計算流程。

首先，對 $a$ 做質因數分解。為了不失一般性，我們寫成 $a=(-1)2^{k_{0}}\cdot q_{1}^{k_2}q_{2}^{k_2}...q_{n}^{k_n}$，其中 $q_1$ 到 $q_n$ 都是質數。

其次，將 $a$ 代入 Legendre symbol，得到 $\left ( \frac{a}{p} \right )=\left ( \frac{-1}{p} \right )\left ( \frac{2}{p} \right )\left ( \frac{q_{1}^{k_1}}{p} \right ) \left ( \frac{q_{2}^{k_2}}{p} \right )...\left ( \frac{q_{n}^{k_n}}{p} \right )$

對於 $\left ( \frac{q_{i}^{k_i}}{p} \right )$，利用 Legendre symbol 完全積性函數的特性，我們只需計算 $\left ( \frac{q_{i}}{p} \right )$ 的值，將此值乘上 $k_i$ 次，就是 $\left ( \frac{q_{i}^{k_i}}{p} \right )$ 了。 因此對於 $a$ 的計算，底下我們分成三種情況討論，$\left ( \frac{-1}{p} \right )$、$\left ( \frac{2}{p} \right )$、$\left ( \frac{q}{p} \right )$，其中 gcd$(q,p)=1$。

情況一、計算 $\left ( \frac{-1}{p} \right )$
判別 $\left ( \frac{-1}{p} \right )$ 的值是不是 $1$，相當於尋找哪些質數 $p$，能使  $x^{2}\equiv -1\; (\mathbf{mod}\; p)$ 有解。

根據 Euler's Criterion，$a$ 是模 $p$ 的平方剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv 1\: (\mathbf{mod}\; p)$。

這裡我們的 $a=-1$。代入 Euler's Criterion 後，得到 $(-1)^{\frac{p-1}{2}}\equiv 1\: (\mathbf{mod}\; p)$。顯然 $\frac{p-1}{2}$ 必須是偶數，故 $\frac{p-1}{2}=2k$，$k\in \mathbb{Z}$。整理後得到 $p=4k+1$，這就是我們要的結果！

情況二、計算 $\left ( \frac{2}{p} \right )$
這回我們無法用 Euler's Criterion 去證明。為了要製造出 $(-1)$ 的次方，我們會利用之前這篇、證明 Euler's theorem 的技巧。

考慮下面 $\frac{p-1}{2}$ 個同餘式。

$p-1\equiv 1\cdot (-1)\; (\mathbf{mod}\; p)$

       $2\equiv 2\cdot (-1)^{2}\; (\mathbf{mod}\; p)$

 $p-3\equiv 3\cdot (-1)^{3}\; (\mathbf{mod}\; p)$

       $4\equiv 4\cdot (-1)^{4}\; (\mathbf{mod}\; p)$

...

                      $r\equiv \left ( \frac{p-1}{2} \right )\cdot (-1)^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

對於第 $r$ 個，也就是第 $\frac{p-1}{2}$ 個，$\frac{p-1}{2}$ 可能是奇數或偶數。若 $\frac{p-1}{2}$ 是偶數，表示 $\frac{p-1}{2}=2k$，$k\in \mathbb{Z}$，此時 $p=4k+1$；同理，若 $\frac{p-1}{2}$ 是奇數，則 $p=4k+3$。換句話說，

將上面 $\frac{p-1}{2}$ 個同餘式兩端相乘。得到 $2\cdot 4\cdots (p-3)\cdot (p-1)\equiv \left ( \frac{p-1}{2} \right )!\left ( -1 \right )^{1+2+\cdots +\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

左端重新整理，得到 $2\cdot 4\cdots (p-3)\cdot (p-1)=2^{\frac{p-1}{2}}\cdot \left ( \frac{p-1}{2} \right )!$。

右端 $(-1)$ 的次方數 $1+2+\cdots +\frac{p-1}{2}=\frac{\left ( 1+\frac{p-1}{2} \right )\cdot \left ( \frac{p-1}{2} \right )}{2}=\frac{p^{2}-1}{8}$。

把整理後的項目代入上面相乘後的同餘式，得到 $2^{\frac{p-1}{2}}\cdot \left ( \frac{p-1}{2} \right )!\equiv \left ( \frac{p-1}{2} \right )!\cdot (-1)^{\frac{p^{2}-1}{8}}\; (\mathbf{mod}\; p)$。

因為 $\left ( \frac{p-1}{2} \right )!$ 是偶數，gcd$(\left ( \frac{p-1}{2} \right )!,p)=1$，所以兩端可以消去 $\left ( \frac{p-1}{2} \right )!$，得到 $2^{\frac{p-1}{2}}\equiv (-1)^{\frac{p^{2}-1}{8}}\; (\mathbf{mod}\; p)$。根據 Euler's Criterion，$\left ( \frac{2}{p} \right )\equiv 2^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$。因為兩端的絕對值等於 $1$，且 $p$ 是奇質數，故同餘的符號可改為等號，也就是說，$\left ( \frac{2}{p} \right )= (-1)^{\frac{p^{2}-1}{8}}$。

當 $p$ 等於多少時，$\frac{p^{2}-1}{8}$ 會是偶數呢？答案有兩個：$p=8k+1$ 及 $p=8k-1$，解 $p$ 過程可用奇偶數性質去判斷，建議一定要自己練習去解出 $p=8k\pm 1$。

情況三、計算 $\left ( \frac{q}{p} \right )$，其中 gcd$(q,p)=1$
根據 Gauss's Lemma(文末會證明)，我們可以有 $\left ( \frac{q}{p} \right )=(-1)^n$，其中 $n$ 是數列 $q,2q,\cdots ,\left ( \frac{p-1}{2} \right )q$ 中、對模 $p$ 的最小正剩餘裡大於 $\frac{p}{2}$ 的個數。當 $n$ 是奇數時，$(-1)^{n}=-1$；當 $n$ 是偶數時，$(-1)^{n}=1$。Gauss's Lemma 的重要性在於我們不用去算 $a^{\frac{p-1}{2}}$，而是改算最小正剩餘裡大於 $\frac{p}{2}$ 的個數，降低了計算的工作量。

要如何找出 $n$？或者說，如何判別 $n$ 是奇數或偶數？目前看過最多人用的是 Eisenstein 的方法，又稱 Eisenstein's Lemma，因為較為直覺且可用幾何圖形表示。

Eisenstein's Lemma：假設 $q$ 是奇數，$p$ 是奇質數，$gcd(q,p)=1$，對於 $\left ( \frac{q}{p} \right )=(-1)^n$ 中的 $n$，有 $n=\sum_{k=1}^{\frac{p-1}{2}}\left \lfloor \frac{qk}{p} \right \rfloor$。這裡 $\left \lfloor \;  \right \rfloor$ 是 floor function 符號，例如 $\left \lfloor 4.7 \right \rfloor=4$，$\left \lfloor -3.7 \right \rfloor=-4$。

這裡不證明 Eisenstein's Lemma，我們直接用例子了解。例如我們要計算 $\left ( \frac{7}{11} \right )$，先求出 $n=\sum_{k=1}^{\frac{11-1}{2}}\left \lfloor \frac{7k}{11} \right \rfloor=\sum_{1}^{5}\left \lfloor \frac{7k}{11} \right \rfloor$。

計算五個 floor function 的值，分別得到 $0,1,1,2,3$，於是 $n=0+1+1+2+3=7$。最後得到 $\left ( \frac{7}{11} \right )=(-1)^7=-1$。

但如果 $n$ 很大，計算 $n$ 個 floor function 的值就很頭痛了。此時有一個很重要的定律就派上用場了，叫做「二次互反律(Quadratic Reciprocity Law)」。

 二次互反律(Quadratic Reciprocity Law)
定義：若 $p,q$ 都是奇質數，$p\neq q$，則 $\left ( \frac{q}{p} \right )\left ( \frac{p}{q} \right )=(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$。或者說，

在網路和書籍可以找到很多證明二次互反律的說明，礙於篇幅就不在這裡贅述，有興趣的可以看這篇最底下的補充。透過二次互反律，可以把較大的分母($p$)替換成較小的($q$)，計算時更為快速。

分析完上述三種情況：計算 $\left ( \frac{-1}{p} \right )$、計算 $\left ( \frac{2}{p} \right )$、計算 $\left ( \frac{q}{p} \right )$，計算 $\left ( \frac{a}{p} \right )$ 就簡單多了。

Gauss's Lemma(高斯引理)
Gauss's Lemma 定義：
設 $a\in \mathbb{Z}$，$p$ 是奇質數，$gcd(a,p)=1$。則 $\left ( \frac{a}{p} \right )=(-1)^n$，其中 $n$ 是數列 $a,2a,\cdots ,\left ( \frac{p-1}{2} \right )a$ 中、對模 $p$ 的最小正剩餘裡大於 $\frac{p}{2}$ 的個數。

從 $(-1)^{n}$ 來看，當 $n$ 是奇數時，$(-1)^{n}=-1$；當 $n$ 是偶數時，$(-1)^{n}=1$。

例如我們要判別 $\left ( \frac{3}{17} \right )$ 的值，也就是 $x^{2}\equiv 3\; (\mathbf{mod }17)$ 是否有解。這裡的 $a=3$，$p=17$，而 $\frac{p-1}{2}=\frac{17-1}{2}=8$。數列 $3,6,9,12,15,18,21,24$ ，對模 $17$ 的最小正剩餘依序為 $3,6,9,12,15,1,4,7$，大於 $\frac{p}{2}$，也就是大於 $\frac{17}{2}$ 的個數有三個：$9,12,15$，因此 $n=3$。$\left ( \frac{3}{17} \right )=(-1)^3=-1$，$3$ 是模 $17$ 的二次非剩餘，所以同餘式 $x^{2}\equiv 3\; (\mathbf{mod }17)$ 無解。

Gauss's Lemma 證明
已知 $(a,p)=1$，令 $k\in \left \{ 1,2,\cdots ,\frac{p-1}{2} \right \}$，有 $(ka,p)=1$。

設 $a,2a,3a,\cdots ,\frac{p-1}{2}a$ 對模 $p$ 的最小正剩餘為 $r_{1},r_{2},\cdots ,r_{\frac{p-1}{2}}$，且 $0<r_{1}<r_{2}<\cdots <r_{\frac{p-1}{2}}<p$。假設大於 $\frac{p}{2}$ 的最小正剩餘有 $n$ 個，小於 $\frac{p}{2}$ 的有 $m$ 個，其中 $m+n=\frac{p-1}{2}$，於是我們把原本的  $r_{1},r_{2},\cdots ,r_{\frac{p-1}{2}}$ 改寫為

 $\underset{<\frac{p}{2}}{\underbrace{r_{1},r_{2},\cdots ,r_{m}}},\underset{>\frac{p}{2}}{\underbrace{r_{m+1},\cdots ,r_{\frac{p-1}{2}}}}$。

對於 $\underset{>\frac{p}{2}}{\underbrace{r_{m+1},\cdots ,r_{\frac{p-1}{2}}}}$，為了使每一項都小於 $\frac{p}{2}$，我們對每一項都減去 $p$，變成  $p-r_{m+1},p-r_{m+2},\cdots ,p-r_{m+n}$。

對於下面的數列

$r_{1},r_{2},\cdots ,r_{m},p-r_{m+1},p-r_{m+2},\cdots ,p-r_{m+n}$，

我們接著要證明，這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。這樣他們相乘時剛好會是 $\left ( \frac{p-1}{2} \right )!$。

前面已經說明這 $\frac{p-1}{2}$ 個數都小於 $\frac{p}{2}$。只要證明這 $\frac{p-1}{2}$ 個數皆不相同，就相當於證明了這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。

我們用反證法。假設有 $r_{s}=p-r_{t}$，移項得到 $r_{s}+r_{t}=p$，也就是 $x_{s}a+y_{t}a=(x_{s}+y_{t})a\equiv 0\; (\mathbf{mod}\; p)$。因為 $(a,p)=1$，所以得到 $x_{s}+y_{t}\equiv 0\; (\mathbf{mod}\; p)$。但是 $1\leq x_{s}\leq \frac{p-1}{2}$，$1\leq y_{t}\leq \frac{p-1}{2}$，相加後的範圍是 $2\leq x_{s}+y_{t}\leq p-1$，而 $\left \{ 2,3,\cdots ,p-1 \right \}$ 中的每個元素都無法被 $p$ 整除，故原本的假設是錯誤的。因此這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。

所以 $\left ( \frac{p-1}{2} \right )!=r_{1}r_{2}\cdots r_{m}(p-r_{m+1})\cdots (p-r_{m+n})$

                     $\equiv (-1)^{n}r_{1}r_{2}\cdots r_{\frac{p-1}{2}}$

                     $\equiv (-1)^{n}a\cdot 2a\cdot \cdots \frac{p-1}{2}a$

                     $\equiv (-1)^{n}\left ( \frac{p-1}{2} \right )!a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

因為 $\left ( \left ( \frac{p-1}{2} \right )!,p \right )=1$，故同餘式兩端除以 $\left ( \frac{p-1}{2} \right )!$，得到 $1\equiv (-1)^{n}a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$。於是有

$a^{\frac{p-1}{2}}\equiv (-1)^n\; (\mathbf{mod}\; p)$。

根據 Legengre symbol 定義，$\left ( \frac{a}{p} \right )\equiv a^{\frac{p-1}{2}}\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )$，也就是 $\left ( \frac{a}{p} \right )\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )$。

對於 $\left ( \frac{a}{p} \right )\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )，$因為 $p$ 是奇質數，所以 $\left ( \frac{a}{p} \right )=(-1)^n$，證明完畢。