p = 2 的情形

當 n = 2 時, 因為 a $\equiv$ 1, 3(mod 4), 我們僅要考慮 x² $\equiv$ 1(mod 4) 以及 x² $\equiv$ 3(mod 4) 兩種 congruence equations. 由於解必為奇數我們可以假設 2k + 1 為一解. 因此由 (2k + 1)² = 4k(k + 1) + 1 $\equiv$ 1(mod 8), 我們知 x² $\equiv$ 3(mod 4) 無解. 而 x² $\equiv$ 1(mod 4) 之解為 x $\equiv$ ±1(mod 4) (即所有奇數).

由上面討論知當 n = 3 時, x² $\equiv$ 3, 5, 7(mod 8) 無解, 而 x² $\equiv$ 1(mod 8) 有解且解為 x $\equiv$ ±1,±3(mod 8). n > 3 時, 我們知道不能如此硬作下去, 可以利用數學歸納法得到以下結果.

証明. 若 a $\equiv$ 3, 5, 7(mod 8), 則由前知 x² $\equiv$ a(mod 8) 無解. 因為 n $\ge$ 3, 故由 Lemma 4.2.2 知 x² $\equiv$ a(mod 2ⁿ) 無解. 因為 a 為奇數故僅剩下 a $\equiv$ 1(mod 8) 的情形未討論. 所以我們只要證明 a $\equiv$ 1(mod 8) 時 x² $\equiv$ a(mod 2ⁿ) 有解.

已知 n = 3 時成立. 假設 n = k - 1 (k $\ge$ 4) 時成立, 即當 a $\equiv$ 1(mod 8) 時, x² $\equiv$ a(mod 2^{k - 1}) 有解. 假設 c $\in$ $\mathbb {Z}$ 是 x² $\equiv$ a(mod 2^{k - 1}) 的一個解 (即 2^{k - 1}| c² - a), 也就是說 c² = a + 2^{k - 1}b, 其中 b $\in$ $\mathbb {Z}$ . 我們想利用 c 找到 x² $\equiv$ a(mod 2^k) 之解. 若 c² = a + 2^{k - 1}b 其中 b 為偶數, 則自然 2^k| c² - a, 得 c 為 x² $\equiv$ a(mod 2^k) 之一解. 若 b 為奇數, 則考慮 c' = c + 2^{k - 2}. 此時 c'² = c² + 2^{k - 1}c + 2^{2k - 4} = a + 2^{k - 1}(b + c) + 2^{2k - 4}. 由於 b 和 c 皆為奇數知 2| b + c, 而且 2k - 4 = k + k - 4 $\ge$ k (因 k $\ge$ 4), 故得 c'² $\equiv$ a(mod 2^k). 得證 x² $\equiv$ a(mod 2^k) 有解. $\qedsymbol$

我們已知 x² $\equiv$ a(mod 2ⁿ) 何時有解何時無解. 若有解時, 其在 modulo 2ⁿ 之下會有多少解呢? 我們依然用兩個解之間的關係來探討.

証明. 若 c' $\in$ $\mathbb {Z}$ 亦為一解, 則 2ⁿ| c² - c'², 即 2ⁿ|(c - c')(c + c'). 要注意因為 c 和 c' 皆為奇數, 我們可以有 c $\equiv$ ±1(mod 4) 和 c' $\equiv$ ±1(mod 4), 四種情形. 不過不管是哪一種情形 c - c' 和 c + c' 之中必有一個(且僅有一個)不能被 4 整除 (但仍為偶數). 例如在 c $\equiv$ 1(mod 4) 及 c' $\equiv$ - 1(mod 4) 的情況, 我們有 c + c $\equiv$ 0(mod 4) 但 c - c' $\equiv$ 2(mod 4). 即 2| c - c' 但 4 $\nmid$ c - c'. 我們先考慮 4 $\nmid$ c + c' 這種情形. 此時 c + c' = 2 $\lambda$ , 其中 $\lambda$ 為奇數. 因此由前面已知 2ⁿ|(c - c')(c + c'), 得 2ⁿ| 2 $\lambda$ (c - c'), 即 2^{n - 1}| $\lambda$ (c - c'). 現由於 gcd(2, $\lambda$ ) = 1, 故由 Proposition 1.2.7(1) 得 2^{n - 1}| c - c'. 同理若 4 $\nmid$ c - c', 則知 2^{n - 1}| c + c'.

總結來說, 若 c' 是 x² $\equiv$ a(mod 2ⁿ) 之一解, 則存在 t $\in$ $\mathbb {Z}$ 使得 c' = c + t2^{n - 1} 或 c' = - c + t2^{n - 1}. 反之若 c' = c + 2^{n - 1}, 則 c'² = c² + 2ⁿct + 2^{2n - 2}t². 由於 2n - 2 $\ge$ n + 1, 得 c'² $\equiv$ c² $\equiv$ a(mod 2ⁿ). 故知 c' 為 x² $\equiv$ a(mod 2ⁿ) 之ㄧ解. 同理 c' = - c + t2^{n - 1} 亦為 x² $\equiv$ a(mod 2ⁿ) 之ㄧ解. 然而當 t 是奇數時 c' = c + t2^{n - 1} $\equiv$ c + 2^{n - 1}(mod 2ⁿ) 且 c' = - c + t2^{n - 1} $\equiv$ - c + 2^{n - 1}(mod 2ⁿ). 而當 t 是偶數時 c' = c + t2^{n - 1} $\equiv$ c(mod 2ⁿ) 且 c' = - c + t2^{n - 1} $\equiv$ - c(mod 2ⁿ). 故得知在 modulo 2ⁿ 之下 x² $\equiv$ a(mod 2ⁿ) 共有 x $\equiv$ c, c + 2^{n - 1}, - c + 2^{n - 1}, - c(mod 2ⁿ) 這 4 個根 (注意因 c 為奇數, 所以這些數在 modulo 2ⁿ 之下皆相異). $\qedsymbol$

Example 5.2.3 解 x² $\equiv$ 17(mod 32). 由於 17 $\equiv$ 1(mod 8), 由 Proposition 5.2.1 知必有解. 我們利用 Proposition 5.2.1 證明中所用的方法來找出一個解. 首先解 x² $\equiv$ 17(mod 2^{5 - 1}), 即 x² $\equiv$ 1(mod 16). 可知 x = 1 為 x² $\equiv$ 17(mod 16) 之一解. 但由於 1² - 17 = 2⁴×(- 1) 且 -1 是奇數, 故利用 Proposition 5.2.1 的證明知 1 + 2^{(5 - 2)} = 9 為 x² $\equiv$ 17(mod 32) 之一解. 找到一解後, 最後利用 Proposition 5.2.2 知 x $\equiv$ 9, 25, 7, 23(mod 32) 為 x² $\equiv$ 17(mod 32) 所有的解.