求 $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$

接下來我們要探討 $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$ 的取值情形. 會將 2 和一般的奇質數分開討論的原因是因為 2 是唯一的偶質數, 其表現在很多狀況是和奇質數不同的, 事實上我們在前面已經看到許多在 2 的情況和一般奇質數有很大不同的情形例如 x² $\equiv$ a(mod 2ⁿ) 和 x² $\equiv$ a(mod pⁿ) 這兩種 congruence equation 其解的形態就完全不同.

我們還是要用 Euler's criterion 的精神來求 $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$ 而不是直接探討 x² $\equiv$ 2(mod p) 何時有解. 然而 Euler's criterion 並不能直接套用來求 $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$, 主要原因是我們這裡的 p 是一般的奇質數而不是特定的奇質數, 所以根本無法估計 2^{(p - 1)/2} 在 modulo p 之下為 1 或 -1. 我們必須推導出另外的方法可以幫助我們求 2^{(p - 1)/2} 在 modulo p 之情形.

Lemma 5.4.2 (Gauss's Lemma)   假設 p 是奇質數且 a $\in$ $\mathbb {Z}$ 滿足 p$\nmid$a. 考慮集合 S = {a, 2a,...,${\dfrac{p-1}{2}}$a}. 若 S 中共有 n 個元素其除以 p 的餘數大於 (p - 1)/2, 則

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

証 明. 我們將 S 中的元素除以 p 的餘數分成 r₁,..., r_n 及 s₁,..., s_m 兩部份, 其中 r_i 是大於 (p - 1)/2 的部份, 而 s_j 表小於等於 (p - 1)/2 的部份. 由於 S 中的元素皆與 p 互質, 所以對所有的 i $\in$ {1,..., n} 和 j $\in$ {1,..., m} 依 r_i, s_j 的定義我們知存在 1$\le$n_i$\le$(p - 1)/2 使得 n_ia 除以 p 的餘數為 r_i 且 (p + 1)/2$\le$r_i$\le$p - 1, 另一方面存在 1$\le$m_j$\le$(p - 1)/2 使得 m_ja 除以 p 的餘數為 s_j 且 1$\le$s_j$\le$(p - 1)/2. 要注意此時 n + m = (p - 1)/2, 現考慮 T = {p - r₁,..., p - r_n, s₁,..., s_m}, 我們要證明 T = {1, 2,...,(p - 1)/2}.

要證明 T = {1, 2,...,(p - 1)/2}. 我們先證明 T $\subseteq$ {1, 2,...,(p - 1)/2}. 然而對任意的 i $\in$ {1,..., n} 我們有 p - r_i$\le$p - (p + 1)/2 = (p - 1)/2 且 p - r_i$\ge$p - (p - 1) = 1, 故知 p - r_i $\in$ {1, 2,...,(p - 1)/2}. 另一方面對任意 j $\in$ {1,..., m} 已知 1$\le$s_j$\le$(p - 1)/2 故得證 T $\subseteq$ {1, 2,...,(p - 1)/2}.

接下來我們證明 p - r_i, i $\in$ {1,..., n} 和 s_j, j $\in$ {1,..., m} 這 n + m (即 (p - 1)/2) 個元素皆相異, 便可得證 T = {1, 2,...,(p - 1)/2}. 所以我們要證明 (1): 1$\le$i$\ne$i'$\le$n 時, p - r_i$\ne$p - r_i'; (2): 1$\le$j$\ne$j'$\le$m 時, s_j$\ne$s_j' 以及 (3): 對任意 i $\in$ {1,..., n}, j $\in$ {1,..., m}, p - r_i$\ne$s_j.

當 1$\le$i$\ne$i'$\le$n 時, 若 p - r_i = p - r_i' 表示 r_i = r_i', 依定義即 n_ia 和 n_i'a 除以 p 的餘數相同, 也就是說 n_ia $\equiv$ n_i'a(mod p). 然而已假設 a 和 p 互質故由 Corollary 3.2.4 知 n_i $\equiv$ n_i'(mod p). 但此與 1$\le$n_i$\ne$n_i'$\le$(p - 1)/2 的假設矛盾, 故得證 p - r_i$\ne$p - r_i', 即 (1) 是對的. 同理可證得 (2) 是對的. 至於 (3), 若 p - r_i = s_j, 表示 r_i + s_j = p, 可得 n_ia + m_ja $\equiv$ 0(mod p). 故再由 Corollary 3.2.4 得 n_i + m_j $\equiv$ 0(mod p). 然而 1$\le$n_i, m_j$\le$(p - 1)/2, 得 2$\le$n_i + m_j$\le$p - 1, 不可能滿足 p| n_i + m_j, 故得證 p - r_i$\ne$s_j.

既然 T = {1, 2,...,(p - 1)/2}, 我們得

$${\frac{p-1}{2}}$$! = (p - r₁) ^... (p - r_n) ^. s₁ ^... s_m $$\equiv$$ (- 1)ⁿr₁ ^... r_n ^. s₁ ^... s_m(mod p).

另一方面 S = {a, 2a,...,${\dfrac{p-1}{2}}$a} 中元素除以 p 的餘數所成的集合為 {r₁,..., r_n, s₁,..., s_m}, 故得

r₁ ^... r_n ^. s₁ ^... s_m $$\equiv$$ a ^. 2a ^... $${\frac{p-1}{2}}$$a = $${\frac{p-1}{2}}$$! ^. a^{${\frac{p-1}{2}}$}(mod p).

和上式整理得

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

因為 ${\dfrac{p-1}{2}}$! 和 p 互質, 故由 Corollary 3.2.4 知

1 $$\equiv$$ (- 1)ⁿa^{${\frac{p-1}{2}}$}(mod p),

即

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

$\qedsymbol$

若 {a, 2a,...,${\dfrac{p-1}{2}}$a} 中共有 n 個元素除以 p 的餘數大於 (p - 1)/2, 則由 Corollary 5.3.4 以及 Lemma 5.4.2 知

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

故由 $\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$${\dfrac{{a}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$ 的取值為 ±1, 得

$$\left(\vphantom{\dfrac{{a}}{\,{p}\,}}\right.$$$${\dfrac{{a}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a}}{\,{p}\,}}\right)$$ = (- 1)ⁿ.

Gauss's Lemma 將繁複 a^{(p - 1)/2} 的計算換成計算 {a, 2a,...,${\dfrac{p-1}{2}}$a} 中有多少個除以 p 的餘數大於 (p - 1)/2, 確實將問題簡化了. 我們可以利用它來計算 $\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$${\dfrac{{2}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$.

Theorem 5.4.3   假設 p 是奇質數, 則

$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$$ = $$\left\{\vphantom{ \begin{array}{ll} 1, & \hbox{當 $p\equiv \pm 1... ...};$} \\ -1, & \hbox{當 $p\equiv \pm 3\pmod{8}.$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} 1, & \hbox{當 $p\equiv \pm 1\pmod{8};$} \\ -1, & \hbox{當 $p\equiv \pm 3\pmod{8}.$} \\ \end{array}$$

証 明. 考慮 S = {2, 2×2,...,${\dfrac{p-1}{2}}$×2}, 我們得 S = {2, 4,..., p - 1}. 也就是說 S 中的元數除以 p 所得餘數所成的集合恰為 S, 即小於 p 的正偶數所成之集合. 由於 p 是奇數, 我們將之分成 p $\equiv$ ±1,±3(mod 8) 四種情形來討論. 看看 S 中有多少元素大於 (p - 1)/2.

當 p = 8k + 1 (即 p $\equiv$ 1(mod 8)) 時, (p - 1)/2 = 4k. 因此 S 中大於 (p - 1)/2 的元素個數即為小於等於 p - 1 = 8k 且大於 4k 的偶數之個數. 知其共有 (8k - 4k)/2 = 2k. 故由 Corollary 5.3.4 以及 Lemma 5.4.2 知

$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$$ = (- 1)^2k = 1.

當 p = 8k - 1 (即 p $\equiv$ - 1(mod 8)) 時, (p - 1)/2 = 4k - 1. 因此 S 中大於 (p - 1)/2 的元素個數即為小於等於 p - 1 = 8k - 2 且大於 4k - 1 的偶數之個數. 知其共有 (8k - 2 - (4k - 2))/2 = 2k. 故由 Corollary 5.3.4 以及 Lemma 5.4.2 知

$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$$ = (- 1)^2k = 1.

當 p = 8k + 3 (即 p $\equiv$ 3(mod 8)) 時, (p - 1)/2 = 4k + 1. 因此 S 中大於 (p - 1)/2 的元素個數即為小於等於 p - 1 = 8k + 2 且大於 4k + 1 的偶數之個數. 知其共有 (8k + 2 - 4k)/2 = 2k + 1. 故由 Corollary 5.3.4 以及 Lemma 5.4.2 知

$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$$ = (- 1)^{2k + 1} = - 1.

當 p = 8k - 3 (即 p $\equiv$ - 3(mod 8)) 時, (p - 1)/2 = 4k - 2. 因此 S 中大於 (p - 1)/2 的元素個數即為小於等於 p - 1 = 8k - 4 且大於 4k - 2 的偶數之個數. 知其共有 (8k - 4 - (4k - 2))/2 = 2k - 1. 故由 Corollary 5.3.4 以及 Lemma 5.4.2 知

$$\left(\vphantom{\dfrac{{2}}{\,{p}\,}}\right.$$$${\dfrac{{2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{2}}{\,{p}\,}}\right)$$ = (- 1)^{2k - 1} = - 1.

$\qedsymbol$

有了 Theorem 5.4.3, 給定一奇質數 p, 我們將很容易知道 x² $\equiv$ 2(mod p) 是否有解. 例如因為 101 $\equiv$ 5 $\equiv$ - 3(mod 8), 故知 x² $\equiv$ 2(mod 101) 無解. 而 23 $\equiv$ - 1(mod 8) 故知 x² $\equiv$ 2(mod 23) 有解. 事實上 5² $\equiv$ 2(mod 23), 故知 x $\equiv$ ±5(mod 23) 為 x² $\equiv$ 2(mod 23) 之解.