[數論] 關於二次剩餘的整理

可參考下面兩篇
[數論] 二次剩餘 (Quadratic Residues)
http://gotonsb-numbertheory.blogspot.tw/2014/04/quadratic-residues.html

[數論] Legengre symbol 和 二次互反律
http://gotonsb-numbertheory.blogspot.tw/2014/05/legengre-symbol.html

隔了一年回去看以前寫的東西，還蠻亂的。這篇是把上兩篇的內容再整理一次，並搭配題目練習。


首先，一個二次同餘式一般形如 $$a_2x^2+a_1x+a_0\equiv 0\; (\textrm{mod}\; m)$$ 其中 $x^2$ 係數 $a\neq 0$。這是高次同餘式中最簡單的情形(因為最高次是兩次)。對於合數模的高次同餘式，我們可以把合數模化為質數模去計算。在這裡，我們的模數皆為奇質數($p>2$, $p$ is a prime number.)。

透過配方法，$a_2x^2+a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$ 可改寫成 $$z^2\equiv a\; (\textrm{mod}\; p)$$ 上式是二次同餘式的最簡表示式。以下我們主要研究形如 $$x^2\equiv a\; (\textrm{mod}\; m),\; \;  (a,m)=1$$ 的同餘式。

---

二次剩餘
[定義] 設 $m>1$，如果 $x^2\equiv a\; (\textrm{mod}\; m)$ 有解，則稱 $a$ 是模 $m$ 的二次剩餘($a$ is a quadratic residue mod $m$.)；反之，則稱 $a$ 為模 $m$ 的二次非剩餘($a$ is a quadratic nonresidue mod $m$)。

---

定理2
若 $p$ 是一個奇質數(odd prime，除了 2 以外的質數)，則在 ${1,2,…,p−1}$ 中，模 $p$ 的二次剩餘與二次非剩餘的數量會相等，即各 $\frac{p-1}{2}$ 個。為什麼？一是模 $i$ 與模 $(p-i)$ 的結果是一樣的，所以我們僅須代入 $\frac{p-1}{2}$ 次；二是這 $\frac{p-1}{2}$ 個數兩兩對模 $p$ 不同餘，所以二次剩餘即有 $\frac{p-1}{2} 個$ 。

根據定理2，我們可以求出模 $p$ 的二次剩餘；不過我們更感興趣的，是如果給你一個數 $a$，能否判別 $a$ 是不是模 $p$ 的二次剩餘。當然，我們可以根據定理2，將模 $p$ 的完全剩餘系的一半依序代入同餘式，找出全部的二次剩餘，再回頭看 $a$ 是否在其中。但如果 $p$ 很大，我們要代入的次數就會增加。

---

定理3 歐拉判別條件(Euler's Criterion)
(1) $a$ 是模 $p$ 的二次剩餘 $\Leftrightarrow$ $a^{\frac{p-1}{2}}\equiv 1\; (\textrm{mod}\; p)$。
(2) $a$ 是模 $p$ 的二次非剩餘 $\Leftrightarrow$ $a^{\frac{p-1}{2}}\equiv -1\; (\textrm{mod}\; p)$。

定理3給了一個判別 $a$ 是否為模 $p$ 的二次剩餘，亦即判別同餘方程 $x^2\equiv a\; (\textrm{mod}\; p)$ 是否有解。

例2 判別 $x^2\equiv 3\; (\textrm{mod}\; 7)$ 是否有解。
解：因為 $3^{\frac{7-1}{2}}\equiv 3^3\equiv 27\equiv -1\; (\textrm{mod}\; 7)$，根據歐拉判別條件，$3$ 不是模 $7$ 的二次剩餘，故原同餘式無解。

---

定義2 Legendre symbol
若 $a$ 是整數，$p$ 是奇質數，則 $a$ 對模 $p$ 的Legendre symbol(the Legendre symbol of $a$ modulo $p$) $$\left ( \frac{a}{p} \right ) = \left\{\begin{array}{32}                  0, & \mbox{if $n\equiv 0$ (mod $p$)} \\                  1, & \mbox{if $a$ is a quadratic residue modulo $p$} \\                  -1,      & \mbox{otherwise.}                 \end{array} \right.$$ 根據歐拉判別條件，若 $(a,p)=1$，則 $$\left ( \frac{a}{p} \right )\equiv a^{\frac{p-1}{2}}\; (\textrm{mod}\; p)$$

Legendre symbol 計算特性
1. $\left ( \frac{a^2}{p} \right )=1$
2. 若 $a_1\equiv a_2\; (\textrm{mod}\; 9)$，則有 $\left ( \frac{a_1}{p} \right )=\left ( \frac{a_2}{p} \right )$
3. $\left ( \frac{a}{p} \right )$ 是積性函數。

---

定理7 高斯引理(Gauss's lemma)
若 $(a,p)=1$，則 $$\left ( \frac{a}{p} \right )=(-1)^n$$ 其中 $n$ 是 $$a,2a,3a,\cdots ,\frac{p-1}{2}a$$ 對模 $p$ 之最小正剩餘中、大於 $\frac{p}{2}$ 的個數。

例3 試用高斯引理判定同餘式 $x^2\equiv 3\; (\textrm{mod}\; 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{17}{2}=8.5$ 的數有三個，因此 $$\left ( \frac{3}{17} \right )=(-1)^3=-1$$ 所以原式無解。

與歐拉判別條件類似，當 $p$ 變大時，計算起來也會變複雜。因此需要二次互反律來減輕計算量。

---

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

---

定義3 Jacobi symbol
計算 Legendre symbol 時，必須先將分母 $a$ 寫成標準分解式才能繼續計算。當 $a$ 變大時，分解的計算量也會變大。關於 Jacobi symbol 的部分，請見維基百科介紹。