[數論] 二次剩餘 (Quadratic Residues)

參考資料
Chapter 4: Quadratic residues http://www.math.uiuc.edu/~hildebr/453.spring11/nt-notes4.pdf
中文數學百科Wiki http://zh.math.wikia.com/wiki/二次剩餘?variant=zh-tw
Number of Quadratic Residues of a Prime
http://www.proofwiki.org/wiki/Number_of_Quadratic_Residues_of_a_Prime
Euler's Criterion http://www.proofwiki.org/wiki/Euler's_Criterion
第五講 二次剩餘 http://wenku.baidu.com/view/0c908d0dba1aa8114431d942

如果對同餘的的概念不熟悉，可以先看這一段影片：

「二次剩餘」定義
任意非零平方整數除以某個數後可能的餘數，我們稱之為「二次剩餘」。用數學式表達如下：

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

例如對模$10$而言，可能的餘數集合為$\left \{ 0,1,4,5,6,9 \right \}$：

$\left\{\begin{matrix}0^{2}\equiv 0 & \\1^{2}\equiv 1 & \\2^{2}\equiv 4 & \\3^{2}\equiv 9 & \\4^{2}\equiv 6 & \\5^{2}\equiv 5 & \mathbf{(mod\; 10)}\\6^{2}\equiv 6 & \\7^{2}\equiv 9 & \\8^{2}\equiv 4 & \\9^{2}\equiv 1 &\end{matrix}\right.$

一般來說，因為 $x^{2}=0$ (mod $m$)總是有解，所以通常不會把 $0$ 考慮進去。這也是一開始定義 $x$ 時會強調是「非零整數」的原因。在此例中，模 $10$ 的二次剩餘是 $\left \{1,4,5,6,9 \right \}$。

若 $p$ 是一個奇質數(odd prime，除了 $2$ 以外的質數)，則在 $\{1, 2, \ldots, p - 1\}$ 中，模 $p$ 的二次剩餘與二次非剩餘的數量會是相等的。 換句話說，對一奇質數 $p$ 而言，模 $p$ 的二次剩餘數量 = 二次非剩餘數量 = $\frac{p-1}{2}$。

欲看證明可看參考資料第三個連結：Proof Wiki。簡單來說，就是要證明 $(p-i)^{2}\equiv i^{2}\; (\mathbf{mod}\; p)$。把 $(p-i)^{2}$ 展開，得到 $(p-i)^{2}=p^2-2pi+i^2\equiv i^2\; (\mathbf{mod}\; p)$，證明完畢。

例如以模 $11$ 為例，在 $1,2,...,10$ 中有一半為平方剩餘，他們分別與 $1^{2},2^{2},3^{2},4^{2},5^{2}$ 同餘。由於

$\left\{\begin{matrix}1^{2}\equiv 1 &\mathbf{mod}\: 11 \\2^{2}\equiv 4 &\mathbf{mod}\: 11 \\3^{2}\equiv 9 &\mathbf{mod}\: 11 \\4^{2}\equiv 5 &\mathbf{mod}\: 11 \\5^{2}\equiv 3 &\mathbf{mod}\: 11\end{matrix}\right.$

所以 $1,4,9,5,3$ 是模 $11$ 的平方剩餘。

現在我們知道對於某奇質數 $p$，求出模 $p$ 之二次剩餘的方法。反過來看，現在我給你一個數 $a$，有沒有辦法判別 $a$ 是不是模 $p$ 的二次剩餘呢？當然，我們可以照著上面的步驟，先將模 $p$ 的二次剩餘全部找出來，再看 $a$ 是不是在剩餘集合裡面。但對於數字較大的 $p$，這樣顯得很沒效率。因此我們要介紹一種判別法，可以幫助我們快速判別一個數是否為模 $p$ 之二次剩餘。

Euler's Criterion(歐拉準則)：判定給定的整數是否是一個質數的二次剩餘
定義：若 $(a,p)=1$，$p$ 是奇質數，則
(1) $a$ 是模 $p$ 的平方剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$
(1) $a$ 是模 $p$ 的平方非剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv -1\; (\mathbf{mod}\; p)$

注意上式給的是"充分必要"條件，因此有必要去證明。證明可參考 Euler's Criterion 網頁，過程中會用到 Euler's Totient Theorem。

充分性：若 $a$ 是模 $p$ 的平方剩餘，則  $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$。
<pf> Assume $a$ is a quadratic residue modulo $p$. $\exists \; k\in \mathbb{Z}$ s.t. $k^{2}\equiv a\; (\mathbf{mod\; }p)$. $(k^{2})^{\frac{p-1}{2}}\equiv k^{p-1}\equiv a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod\; }p)$ by Congruence of Powers and Fermat's Little Theorem.

必要性：若 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$，則 $a$ 是模 $p$ 的平方剩餘。
<pf> $(a^{\frac{p-1}{2}})^{2}\equiv a^{p-1}\equiv 1^{2}\equiv 1\; (\mathbf{mod}\; p)$. Let $b$ is a *primitive root for $p$. $\exists k\in \mathbb{Z}$ s.t. $a=b^{k}$.

$a^{\frac{p-1}{2}}=(b^{k})^{\frac{p-1}{2}}=b^{\frac{k(p-1)}{2}}\equiv 1\; (\mathbf{mod}\; p)$. $\frac{k(p-1)}{2}$must be a multiple of $(p-1)$, so $\frac{k}{2}$ is an integer, which means $k$ is even. $a=b^{k}$ is the square of $b^{\frac{k}{2}}.$

*何謂原根？Let $p$ be a prime. Then $b$ is a primitive root for $p$ if the powers of $b$, $1$, $b$, $b^2$, $b^3$, ...
include all of the residue classes mod $p$ (except $0$).

歐拉準則給了我們另一種判別 $a$ 是否為 $p$ 的二次剩餘的方法，這顯然比列出剩餘系、然後一個一個慢慢檢驗來的方便。但是，一旦 $p$ 很大的時候，計算 $a^{\frac{p-1}{2}}$ 絕非易事！因此數學家又想到另一種方式去檢驗二次剩餘。這種方式其實和歐拉準則有點像，但表達的方式略有差異。

Legendre Symbol(勒讓得符號，二次特徵)
定義：令 $p$ 是奇質數，$a$ 是整數，$(a,p)=1$。 Legendre Symbol $\left ( \frac{a}{p} \right )\overset{def}{=} a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$

在歐拉準則中我們已經看過 $a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$ 了。Legendre Symbol 則是改用另一種符號來表示：$\left ( \frac{a}{p} \right )$。我們可以進一步改寫上面的定義，使其看起來更簡潔。

Legendre Symbol 其實是 Jacobi Symbol 的特例(當分母是質數 $p$ 的特例)。使用 Legendre Symbol 時別忘了分子與分母的限制(分母是質數，分子與分母互質)。有些書會寫 $\left ( \frac{a}{p} \right )=0$ if $p\mid a$，也就是說當 $a$ 是 $p$ 的倍數，$(a,p)=p$，則 $\left ( \frac{a}{p} \right )=0$。因為我們一般只討論當 $a$ 與 $p$ 互質的情形，所以沒有把 $0$ 寫在定義裡。

Legendre Symbol 有下列性質。想看證明的可以參考這個網頁，或是看 YouTube 這段影片。
1. $\left ( \frac{a^2}{p} \right )=1$。
2. 若 $a_{1}\equiv a_{2}\; (\mathbf{mod}\; p)$，有 $\left ( \frac{a_{1}}{p} \right )=\left ( \frac{a_{2}}{p} \right )$。
3. $\left ( \frac{a}{p} \right )$ 是完全積性函數，即 $a=a_{1}a_{2}...a_{n}$ 時，有 $\left ( \frac{a}{p} \right )=\left ( \frac{a_{1}}{p} \right )\left ( \frac{a_{2}}{p} \right )...\left ( \frac{a_{n}}{p} \right )$。

透過第三個性質，把 $a$ 拆解成較小的數字相乘，再去計算其 Legendre Symbol 的值，會比直接用 $a$ 去計算來的方便多了。最後總結一下這篇文章介紹的三種判別二次剩餘的方法。
1. 逐項代入法，亦即逐項檢驗 $p$ 的剩餘系。
2. 歐拉準則
3. 利用 Legendre Symbol