[數論] 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)$