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

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

[數論] Hensel's lifting lemma

零、參考資料
1. 泰勒展開式 http://math.nsysu.edu.tw/ezfiles/87/1087/img/495/1002.pdf
2. Hensel's Lemma, Reduction of Modulus(Lecture 10)
https://math.berkeley.edu/~mcivor/math115su12/schedule.html
3. Polynominal Congruences
http://www2.latech.edu/~schroder/slides/number_theory/14_polynomial_congruences.pdf

How to get from solutions mod $p$ to solutions mod $p^j$ when $p$ and $j$ is large?

一、Hensel's lifting lemma 精隨
「...it(Hensel's lemma) says that if we have a solution mod $p$, we get a unique solution mod $p^2$ ; if we have a solution mod $p^2$ , we get a solution mod $p^3$ , etc....」

「...如果一個模 $p$ 的同餘方程式有一個根，則可以用這個根去找到該方程式在模 $p^2$ 時的根。...」

例如，當我們要解 $f(x)\equiv 0\; (\textrm{mod}\; 2^4)$ 時，如果把 $2^4$ 的完全剩餘系的元素一一代入，總共要代 $2^4=16$ 次才能得知該同餘式的解。

Hensel's lifting lemma，或簡稱 Hensel's lemma，給了我們一種解此種同餘方程式的方法。他的基本概念是，先解 $f(x)\equiv \; (\textrm{mod}\; p^2)$ ，再解 $f(x)\equiv \; (\textrm{mod}\; p)$，接著再解 $f(x)\equiv \; (\textrm{mod}\; p^3)\cdots$ 等等，"lifing(上升)"的概念就在於此。為什麼可以這樣做呢？我們舉一個例子。如果一個數能被 $2^3$ 整除，則這個數也一定能被 $2^2$ 及 $2$ 整除。當模數變小，求解的計算量也會變得比較輕鬆。

但是，一個數能被 $2$ 整除，不代表它一定也能被 $2^2$、甚至 $2^3$ 整除。因此從 $f(x)\equiv 0\; (\textrm{mod}\; 2)$ 求得的解，並不直接等於 $f(x)\equiv 0\; (\textrm{mod}\; 2^3)$。我們必須將從 $f(x)\equiv 0\; (\textrm{mod}\; 2)$ 求得的解一步步"篩選"，最後篩選留下滿足 $f(x)\equiv 0\; (\textrm{mod}\; 2^3)$ 的解。底下的證明，告訴我們如何進行"篩選"。

Theorem (Hensel's Lemma)
Let $f(x)$ be a polynomial with integer coefficients, $p$ be a prime, and suppose $a$ is a solution of the congruence $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ such that $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$. Then there exists an integer $t$ (which is unique $\; (\textrm{mod}\; p)$) such that $a + tp^j$ is a solution to the congruence $f(x)\equiv 0\; (\textrm{mod}\; p^{j+1})$.

<proof>
一個 $n$ 階多項式 $f(x)$ 在 $x=a$ 時的 Taylor series 為 $$f(x)=f(a)+\frac{f^{(1)}(a)}{1!}(x-a)^{1}+\frac{f^{(2)}(a)}{2!}(x-a)^{2}+\cdots +\frac{f^{(n)}(a)}{n!}(x-a)^{n}=\sum_{i=1}^{n}\frac{f^{(i)}(a)}{i!}(x-a)^{i}$$ 將 $x=s=a+tp^{j-1}$ 代入上式，得到 $$f(s)=f(a+tp^{j-1})=f(a)+\frac{f'(a)}{1!}[(a+tp^{j-1})-a]+\frac{f''(a)}{2!}[(a+tp^{j-1})-a]^2+\cdots +\frac{f^{(n)}(a)}{n!}[ (a+tp^{j-1})-a]^n=\sum_{k=0}^{n}\frac{f^{(k)}(a)}{k!}(tp^{j-1})^k$$ 因為 $s$ 是 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 的解，我們有 $$\begin{array} 00 &\equiv f(s) \\ &= f(a+tp^{j-1}) \\ &= f(a)+\frac{f'(a)}{1!}[(a+tp^{j-1})-a]+\frac{f''(a)}{2!}[(a+tp^{j-1})-a]^2+\cdots +\frac{f^{(n)}(a)}{n!}[ (a+tp^{j-1})-a]^n \\ &\equiv f(a)+f'(a)\cdot tp^{j-1}\; (\textrm{mod}\; p^j) \end{array}$$ 因此 $$f'(a)\cdot tp^{j-1}\equiv -f(a)\; (\textrm{mod}\; p^j)$$ 將上式同除以 $p^{j-1}$，得到 $$f'(a)\cdot t\equiv -\frac{f(a)}{p^{j-1}}\; (\textrm{mod}\; p)$$ 我們只要找出滿足上式的 $t$ 值，就可以解方程式 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$。

令 $d=\textrm{gcd}\left ( f'(a),p \right )$。我們知道，當 $d\mid \frac{f(a)}{p^{k-1}}$，同餘方程式 $f'(a)\cdot t\equiv -\frac{f(a)}{p^{j-1}}\; (\textrm{mod}\; p)$ 恰有 $d$ 個解；當 $d\nmid \frac{f(a)}{p^{k-1}}$，則此同餘方程式無解。

我們分三種情況討論：
Case 1: $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$.
因為 $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$，所以 $d=1$。此同餘方程式有唯一解：$t\equiv -\overline{f'(a)}\cdot \frac{f(a)}{p^{k-1}}\; (\textrm{mod}\; p)$，$\overline{f'(a)}$ 是 $f'(a)$ 模 $p$ 之乘法反元素，即 $f(a) \cdot \overline{f'(a)}\equiv 1\; (\textrm{mod}\; p)$。

Case 2: $f'(a)\equiv 0\; (\textrm{mod}\; p)$ and $f(a)\equiv 0\; (\textrm{mod}\; p^j)$.
因為 $f'(a)\equiv 0\; (\textrm{mod}\; p)$，所以 $d=p$；因為 $f(a)\equiv 0\; (\textrm{mod}\; p^j)$，所以 $p\mid \frac{f(a)}{p^{j-1}}$。我們得到 $f(a+tp^{j-1})\equiv 0\; (\textrm{mod}\; p)$ 對所有整數 $t$ 都成立。

Case 3: $f'(a)\equiv 0\; (\textrm{mod}\; p)$ and $f(a)\not\equiv 0\; (\textrm{mod}\; p^j)$.
因為 $f'(a)\equiv 0\; (\textrm{mod}\; p)$，所以 $d=p$；但是 $f(a)\not\equiv 0\; (\textrm{mod}\; p^j)$，所以 $p\nmid \frac{f(a)}{p^{j-1}}$。因此找不到 $t$ 值使同餘方程式成立，也就是無解。


Corollary
設 $a$ 是 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 的解，其中 $p$ 是質數。若 $f'(x)\not \equiv 0\; (\textrm{mod}\; p)$ ，則對於每個 $j$，方程式 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 存在唯一解 $a_j$，其中 $a_j$ 是從 $a$ 而來，公式為：$a_1=a$ 且 $a_j=a_{j-1}-f(a_{j-1})\cdot \overline{f'(a)}$，其中 $\overline{f'(a)}$ 是 $f'(a)$ 模 $p$ 之乘法反元素。

<proof>
根據 Hensel's Lemma，當 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 且 $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$ 時，有 $$a_j:=a_{j-1}+\left ( -\overline{f'(a)} \cdot \frac{f(a_{j-1})}{p^{j-1}} \right )p^{k-1}=a_{j-1}-f(a_{j-1})\cdot \overline{f'(a)}$$ 滿足方程式 $f(a_k)\equiv 0\; (\textrm{mod}\; p)$

[數論] p-adic Numbers (p進數)

參考資料
A first introduction to p-adic numbers http://www.madore.org/~david/math/padics.pdf
Complete Metric Spaces http://pioneer.netserv.chula.ac.th/~lwicharn/2301631/Complete.pdf

一段關於 $p$-adic 的說明影片，片長約17分鐘。

◎ $p$-adic digit
$p$-adic 的 $p$ 是 prime 的意思。我們稱一個介於 $0$ 到 $p-1$ 的整數為 $p$-adic digit。

◎ $p$-adic integer
一個 $p$-adic integer 是指一個由 $p$-adic digit 組成的序列(sequence) $\left ( a_i \right )_{i\in \mathbb{N}}$。可寫成 $$\cdots a_i\cdots a_2a_1a_0$$ 或寫成 $$a=\sum_{i=i_0}^{\infty }a_i\cdot p^i.$$
◎ $p$-adic number
一個 $p$-adic integer 是指一個由 $p$-adic digit 組成的序列(sequence) $\left ( a_i \right )_{i\in \mathbb{Z}}$，或寫成 $$a=\sum_{i=0}^{\infty }a_i\cdot p^i,\: \; a_i\in \left \{ 0,1,2,\cdots ,p-1 \right \}$$ 如果一個 $p$-adic number $a$，對於 $i<0$，$a_i=0$，則我們特別稱 $a$ 為 $p$-adic integer。(可以回上一段看 $p$-adic integer 的定義。)

$p$-adic integers 構成一個 ring: $\mathbb{Z}_p$；$p$-adic numbers 構成一個 field: $\mathbb{Q}_p$。

◎ $p$-adic norm ($p$-adic absolute value)
一般在沒有特地說明之下，我們稱的距離就是歐式距離(Euclidean distance)，也就是「$m$ 維空間中、兩個點之間的真實距離。」例如在數線(一維空間)上有兩點 $a$ 和 $b$，我們會說 $a$ 和 $b$ 的距離是 $\left | a-b \right |$，亦即兩數之差的絕對值。

$p$-adic 的「距離」概念建立在整數的整除性質上。給定一質數 $p$，若兩個數之差能被 $p$ 的高次冪整除，那麼這兩個數距離就「接近」。冪次越高，距離越近。

給定一個非零的有理數 $x$，我們可以把 $x$ 表示為 $$x=p^a\cdot \frac{r}{s}$$ 其中 $p$ 是質數，$p$、$r$、$s$ 三數彼此互質。則我們定義 $x$ 的 $p$-adic norm(或是 $x$ 的 $p$-adic absolute value)為 $$\left | x \right |_p=p^{-a}.$$ 我們也定義 $$\left | 0 \right |_p=0.$$ 例如給定一有理數 $x=\frac{968}{9}$ 及一質數 $p=11$，則 $\frac{968}{9}$ 的 $11$-adic norm 為 $$\left | x \right |_p=\left | \frac{968}{9} \right |_{11}=\left | 11^2\cdot \frac{8}{9} \right |_{11}=11^{-2}.$$ 有了 $p$-adic norm，我們就能定義何謂 $p$-adic 的「距離」（數學上稱距離為「度量」），也就是 $p$-adic metric($p$進度量)。

◎ $p$-adic metric
我們將兩個數 $x$ 和 $y$ 的 $p$-adic metric 寫為 $d(x,y)=\left | x-y \right |_p$。例如取 $p=7$，則 $2$ 和 $28814$ 的 $7$-acid metric 為 $$\left | 28814-2 \right |_7=\left | 28812 \right |_7=\left | 7^4\cdot 13 \right |_7=7^{-4}.$$ ◎實數的完備性(Completeness)
我們知道，有理數是不具備完備性的。例如給定一條數線，若我們限定只能標示有理數，則很遺憾地，我們永遠無法指出 $\sqrt{2}$ 的位置，理由是 $\sqrt{2}$ 是無理數。

如果一個空間中的任何柯西序列(Cauchy sequence)，都收斂在該空間之內，我們稱此空間是「完備度量空間(Complete Metric Spaces)」。關於柯西序列，這裡不多作討論，簡單來說，就是如果有一個數列，我們任取一個正數，你總是能在這個數列中找到某兩項，使其兩項之差的絕對值，永遠小於這個正數，我們稱具有此性質的數列為柯西序列。

因此對於 matric $d(x,y)=\left | x-y \right |_p$，$a=\sum_{i=i_0}^{\infty }a_ip^i$ 的部份和(partial sums)會趨近於 $a$。