可參考下面兩篇
[數論] 二次剩餘 (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 的部分，請見維基百科介紹。
