Hensel 引理、原根

一、Hensel 引理

1. Hensel 引理： \(\mathsf{f(x)}\) 是一个整系数多项式 \(\mathsf{(\ f(x) \in Z(x)\ )}\)，对于素数 p，整数 a 使得 \(\mathsf{p^{k} \mid f(a)}\)，\(\mathsf{(\ f^{‘}(a)，p\ )=1}\)，即 \(\mathsf{f(a)\equiv 0\ mod\ p^{k}，f^{’}(a) \neq 0\ mod\ p}\) 。则在模 p 意义下恰有一个整数 t 使得 \(\mathsf{f(a+tp^{k}) \equiv 0\ (mod\ p^{k+1})}\) 。也就是在模 \(\mathsf{p^{k+1}}\) 的意义下有唯一一个解 \(\mathsf{b \equiv a\ (mod\ p^{k})}\) 。

• 证明：

想找的解 \(\mathsf{b=a+tp^{k}，t \in \{0,\ 1,\ \cdots,\ p-1 \}}\) 在模 \(\mathsf{p^{k+1}}\) 下。

为了验证一个 t 是否满足要求，我们以 a 使用 Taylor 展开式，

\(\mathsf{f(a+tp^{k}) \equiv f(a)+tp^{k}f^{‘}(a)+ \frac{(tp^{k})^{2}}{2!}f^{“}(a)+ \cdots + \frac{(tp^{k})^{n}}{n!}f^{n}(a)}\)

因为 f 是整系数多项式，所以 \(\mathsf{\frac{f^{n}}{n!} \in Z}\)

又 \(\mathsf{p^{nk} \equiv 0\ (mod\ p^{k+1})(k \geq 1)}\)，所以 \(\mathsf{f(a+tp^{k}) \equiv f(a) + tp^{k}f^{’}(a)\ (mod\ p^{k+1})\ (k \geq 1)}\)

注意到 \(\mathsf{p^{k} \mid\mid f(a)，p^{k} \mid\mid tp^{k}f^{‘}(a)}\)，故模 p 下只有一个 t 满足 \(\mathsf{f(a+tp^{k}) \equiv 0\ (mod\ p^{k+1})}\)

• 例子：

使用 Hensel 引理找到 \(\mathsf{x^{3}-2x \equiv 1(mod\ 125)}\) 的一个解

令 \(\mathsf{f(x)=x^{3}-2x-1}\) ，需找到 \(\mathsf{f(x) \equiv 0\ (mod\ 5)}\)

\(\mathsf{f(0) = -1 \equiv 4\ (mod\ 5)}\)

\(\mathsf{f(1) = -2 \equiv 3\ (mod\ 5)}\)

\(\mathsf{f(2)} = 3 \equiv 3\ (mod\ 5)\)

\(\mathsf{f(3) = 20 \equiv 0\ (mod\ 5)}\)

\(\mathsf{f(4) = 55 \equiv 0\ (mod\ 5)}\)

所以，\(\mathsf{a_{1}=3，4}\) 是 \(\mathsf{f(x) \equiv 0\ (mod\ 5)}\) 的所有解

计算 f 的所有导数：\(\mathsf{f^{’}(x)=3x^{2}-2}\)

\(\mathsf{f^{‘}(3) = 27-2 = 25 \equiv 0\ (mod\ 5)}\)

\(\mathsf{f^{’}(4)=48-2=46 \equiv 1\ (mod\ 5)}\)

\(\mathsf{(f^{‘}(4))^{-1}\equiv 1\ (mod\ 5)}\) 所以：

\(\mathsf{a_{2}\equiv 4-f(4)[f^{’}(4)]^{-1}(mod\ 25) \equiv 4-55 \times 1
(mod\ 25) \equiv -51\ (mod\ 25) \equiv 24\ (mod\ 25)}\)

\(\mathsf{a_3 \equiv 24-f(24)[f^{‘}(24)]^{-1}(mod\ 125)\equiv 24-13775 \times 1\ (mod\ 125)\equiv -13751\ (mod\ 125)\equiv -1\ (mod\ 125)\equiv 124\ (mod
125)}\)

所以，\(\mathsf{x=124}\) 是 \(\mathsf{x^{3}-2x \equiv 1\ (mod\ 125)}\) 的解。

二、模多项式

1. 定理：度为 n (多项式的最高次数) 的同余模多项式 \(\mathsf{f(x)\equiv 0\ mod\ p}\) (p 为素数) 至多有 n 个解。

• 证明：

上述定理一定适用于度为 0 或 1 的情况。假设它适用于度 \(\mathsf{< n\ (n \geq 2)}\) 的情况。

如果它没有根，那么结束。否则，假设它有一个根 \(\mathsf{\alpha}\) ，

将 \(\mathsf{f(x)}\) 除以 \(\mathsf{x-\alpha}\) ，会获得 \(\mathsf{g(x) \in Z[x]}\) 和一个常数 r 使得 \(\mathsf{f(x)=g(x)(x-\alpha)+r}\)

如果带入 \(\mathsf{\alpha}\) 获得 \(\mathsf{f(\alpha)=(\alpha-\alpha)g(\alpha)+r=r}\)

这意味着 \(\mathsf{f(\alpha)=r}\) 且 \(\mathsf{f(x)=(x-\alpha)g(\alpha)+f(\alpha)}\)

已知 \(\mathsf{f(\alpha)\ mod\ p =0}\)，如果 \(\mathsf{\beta}\) 是 \(\mathsf{f(x)}\) 的任何其他根，那么将 \(\mathsf{\beta}\) 带入带入方程，得到：

\(\mathsf{f(\beta)=(\beta-\alpha)g(\beta)+f(\alpha)\ mod\ p}\)

\(\mathsf{f(\beta) \equiv (\beta-\alpha)g(\beta)\ mod\ p}\)

所以 \(\mathsf{(\beta-\alpha)g(\beta) \equiv 0\ mod\ p}\) ，我们还假设 \(\mathsf{\beta \neq \alpha}\) ，所以 \(\mathsf{g(\beta) \equiv 0\ mod\ p}\)

所以 \(\mathsf{\beta}\) 是 \(\mathsf{g(x)}\) 的一个根，作为 \(\mathsf{g(x) \equiv 0\ mod\ p}\) 的一个解

可知 \(\mathsf{g(x)}\) 的度为 \(\mathsf{n-1}\) ，所以通过归纳假设 \(\mathsf{g(x) \equiv 0\ mod\ p}\) 有最多 \(\mathsf{n-1}\) 个解

所以，如果包含\(\mathsf{\alpha}\) ，\(\mathsf{f(x)}\) 至多有 n 个解。

1. 推论：如果 \(\mathsf{a{n}x^{n}+a{n-1}x^{n-1}+ \cdots +a{0} \equiv 0\ mod\ p}\) 的解超过 n 个，那么所有的 \(\mathsf{a{i} \equiv 0\ mod\ p}\)

2. 定理：令 \(\mathsf{f(x)=x^{n}+a{n-1}x^{n-1}+ \cdots + a{0}}\) ，\(\mathsf{f(x)\equiv 0\ mod\ p}\) 正好有 n 个不同的解当且仅当 \(\mathsf{f(x)}\) 除以 \(\mathsf{x^{p}-x\ mod\ p}\) ，即存在 \(\mathsf{g(x) \in Z[x]}\) 作为多项式，使得 \(\mathsf{f(x)g(x) = x^{p}-x\ mod\ p}\)

• 证明：

部分1：

假设 \(\mathsf{f(x)}\) 有 n 个解。那么 \(\mathsf{n \leq p}\) 因为在模 p 情况下只有 p 个可能的根。

将 \(\mathsf{x^{p}-x}\) 除以 \(\mathsf{f(x)}\) 获得 \(\mathsf{x^{p}-x=f(x)g(x)+r(x)，deg®

如果 \(\mathsf{\alpha}\) 是 \(\mathsf{f(x)}\) 在模 p 情况下的根，带入 \(\mathsf{\alpha}\) 可得：\(\mathsf{\alpha^{p}-\alpha=f(\alpha)g(\alpha)+r(\alpha) \equiv 0}\)

所以，\(\mathsf{\alpha}\) 一定是 \(\mathsf{r(x) \equiv 0\ mod\ p}\) 的一个解

由于 \(\mathsf{f(x)}\) 有不同的根，\(\mathsf{r(x)\equiv 0\ mod\ p}\) 有 n 个不同的解

但是 \(\mathsf{deg®}\) ，所以 \(\mathsf{x^{p}-x=f(x)g(x)\ mod\ p}\) 并且 \(\mathsf{f(x)}\) 除以 \(\mathsf{x^{p}-x}\)

部分2：

假设 \(\mathsf{f(x) \mid x^{p}-x\ mod\ p}\)

式子 \(\mathsf{x^{p}-x \equiv f(x)g(x)\ mod\ p}\) 其中 \(\mathsf{f(x)}\) 是度为 n 的，\(\mathsf{g(x)}\) 是度为 \(\mathsf{p-n}\) 的。

需要证明 \(\mathsf{f(x)}\) 有 n 个不同的解。

通过之前的定理，\(\mathsf{g(x)}\) 在模 p 下有至多 \(\mathsf{p-n}\) 个根。

如果 \(\mathsf{\alpha \in \{0,\ 1,\ \cdots,\ p-1 \}}\) 不是模 p 下 \(\mathsf{g(x)}\) 的根，那么 \(\mathsf{\alpha^{p}-\alpha \equiv f(\alpha)g(\alpha)\ mod\ p \equiv 0(Fermat)}\)

由于 \(\mathsf{g(\alpha) \neq 0\ mod\ p}\) ，\(\mathsf{f(\alpha)\equiv 0\ mod
p}\)

因此，由于至少有 \(\mathsf{p-(p-n)}\) 个 \(\mathsf{\alpha}\) ，可知 \(\mathsf{f(x)}\) 在模 p 下至少有 n 个不同的根。

根据该理论，\(\mathsf{f(x)}\) 在模 p 下至多有 n 个根 \(\mathsf{\ \Rightarrow\ f(x)}\) 在模 p 下正好有 n 个不同的根。

1. 推论：如果 \(\mathsf{d \mid p-1}\) 那么 \(\mathsf{x^{d} \equiv 1\ mod\ p}\) 在模 p 下恰好有 d 个不同的解

• 例子：

\(\mathsf{x^{3} \equiv 1\ mod\ 7，\qquad x^{3} \equiv 1\ mod\ 5}\)

• 证明：

\(\mathsf{d \mid p-1}\) ，所以 \(\mathsf{x^{d}-1 \mid x^{p-1}-1}\) 作为多项式

\(\mathsf{p-1=kd}\) ，所以 \(\mathsf{x^{kd}-1=(x^{d}-1)(x^{(k-1)d}+\cdots +1)}\)

所以，\(\mathsf{x^{d}-1 \mid x(x^{p-1}-1)=x^{p}-x}\) ，故有 d 个解。

三、元素的阶

1. 定义 (阶)：如果 \(\mathsf{gcd(a,m)=1}\) 且 h 是最小的正整数使得 \(\mathsf{a^{h} \equiv 1\ mod\ m}\) ，那么说 h 是模 m 下 a 的阶。记为：\(\mathsf{h=ord_{m}(a)}\)

• 例子：

\(\mathsf{ord{7}(2)=3 \qquad ord{11}(2)=10 \qquad ord_{11}(5)=5}\)

1. 引理：令 \(\mathsf{h=ord_{m}(a)}\) ，整数 k 的集合，使得 \(\mathsf{a^{k}\equiv 1\ mod\ m}\) 恰好是 h 的倍数的集合。

• 例子：

\(\mathsf{ord_{11}(5)=5}\) ，如果 \(\mathsf{5^{k}\equiv 1\ mod\ 11}\) ，那么 \(\mathsf{k=5,10}\)

• 证明：

\(\mathsf{a^{rh}\equiv (a^{h})^{r}\equiv 1^{r}\equiv 1\ mod\ m}\)

假设有一个 k 满足\(\mathsf{a^{k}\equiv 1\ mod\ m}\)

令\(\mathsf{k=hq+r}\) 其中 \(\mathsf{0 \leq r}\)

\(\mathsf{1\equiv a^{k}=a^{hq+r}=a^{hq}a^{r}\equiv 1a^{r}\ mod\ m \equiv a^{r}\ mod\ m}\)

所以，\(\mathsf{a^{r} \equiv 1\ mod\ m}\) ，但是 \(\mathsf{r}\) ，所以 \(\mathsf{r=0}\) 并且 k 是 h 的倍数，即 \(\mathsf{h \mid k}\)

1. 引理：如果 \(\mathsf{h=ord_{m}(a)}\) 那么 \(\mathsf{a^{k}}\) 在模 m 下的阶是 \(\mathsf{\frac{h}{gcd(k,h)}}\)

• 例子：

\(\mathsf{ord{11}(5)=5 \qquad ord{11}(2)=10}\)

\(\mathsf{5^{3} \equiv 4}\) 的阶 \(\mathsf{\frac{5}{gcd(3,5)}=5\ mod\ 11}\)

\(\mathsf{2^{8} \equiv 3}\) 的阶 \(\mathsf{\frac{10}{gcd(8,10)}=5\ mod
11}\)

• 证明：

\(\mathsf{a^{kj} \equiv 1\ mod\ m \iff h \mid kj \iff \frac{h}{gdc(h,k)} \mid \frac{k}{gcd(h,k)}j \iff \frac{h}{gcd(h,k)}\mid j}\)

所以，最小的正数 \(\mathsf{j=\frac{h}{gcd(h,k)}}\)

1. 引理：如果 a 在模 m 下阶为 h 并且 b 在模 m 下阶为 k 并且 \(\mathsf{gcd(h,k)=1}\) 那么 ab 在模 m 下的阶是 hk

• 例子：

\(\mathsf{ord{11}(4)=5 \qquad ord{11}(10)=2 \quad \Rightarrow \quad ord_{11}(4 \times 10 \equiv 7)=10}\)

• 证明：

\(\mathsf{(ab)^{hk} \equiv (a^{h})^{k}(b^{k})^{h} \equiv 1^{k}1^{h} \equiv 1
mod\ m}\)

相反，假设\(\mathsf{r=ord_{m}(ab)}\)

\(\mathsf{(ab)^{r} \equiv 1\ mod\ m \qquad (ab)^{rh} \equiv 1\ mod\ m \qquad (a^{h})^{r}b^{rh} \equiv 1\ mod\ m \qquad b^{rh} \equiv 1\ mod\ m}\)

所以，\(\mathsf{k \mid rh\ \Rightarrow\ k \mid r}\) ( 因为 \(\mathsf{gcd(k,h)=1}\)) 并且类似的 \(\mathsf{h \mid r}\)

所以，\(\mathsf{hk \mid r}\) 因此 \(\mathsf{hk=ord_{m}(ab)}\)

四、原根

1. 定义 (原根)：如果 a 在模 m 下的阶是 \(\mathsf{\phi(m)}\) ，称 a 是模 m 下的原根

• 例子：

3 是模 7 下的原根

2，7 是模 11 下的原根

1. 引理：令 p 为素数并且对于一些其他的素数 q 假设 \(\mathsf{q^{e} \mid p-1}\) 。那么在模 p 下存在一个 \(\mathsf{q^{e}}\) 阶元素。令 \(\mathsf{p-1=q{1}^{e{1}}q{2}^{e{2}} \cdots q{r}^{e{r}}}\) 。该引理意味着 \(\mathsf{\exists\ g{1},\ g{2}\ \cdots}\) 使 \(\mathsf{ord{p}(g{1})=q{1}^{e{1}},\ ord{p}(g{2})=q{2}^{e{2}} \cdots}\) 等等。

• 例子：

\(\mathsf{p=101,\ q=5,\ e=2 \qquad ord_{101}31=25}\)

1. 推论：令 \(\mathsf{g=g{1}g{2} \cdots g{r}}\) ，由之前的引理 g 的阶为 \(\mathsf{q{1}^{e{1}}q{2}^{e{2}} \cdots q{r}^{e{r}}=p-1= \phi(p)}\) 。因为所有的 \(\mathsf{q{i}}\) 都成对的互素，所以 g 是模 p 下的原根
2. 原根的数量：如果至少存在一个原根，那么在模 m 下原根的个数为 \(\mathsf{\phi(\phi(m))}\) 。特别的，如果 m 是素数，原根的数目就是 \(\mathsf{\phi(m-1)}\)

• 例子：

\(\mathsf{\phi(\phi(31))=8}\) 实际上 \(\mathsf{\{3,\ 11,\ 12,\ 13,\ 17,\ 21,
22,\ 24\ \}}\) 为 31 的原根

1. 定理：在模 m 下存在一个原根当且仅当 \(\mathsf{m=1,\ 2,\ 4,\ p^{e},\ 2p^{e}}\)
2. 其它相关概念：离散对数 等

• 例子：

\(\mathsf{2^{x} \equiv 5\ mod\ 11 \qquad x=log_{2}5\ mod\ 11}\) 这是一个 NPC- hard 问题