每日看点!【数论与组合数学 3】Hensel 引理、原根

2023-03-23 11:11:33 来源：博客园

Hensel 引理、原根

一、Hensel 引理

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)}\) 的解。

二、模多项式

定理：度为 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 个解。

推论：如果 \(\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}\)
定理：令 \(\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(r)
如果 \(\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(r)
部分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 个不同的根。

推论：如果 \(\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 个解。

三、元素的阶

定义 (阶)：如果 \(\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}\)

引理：令 \(\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{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)}}\)

引理：如果 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)}\)

四、原根

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

例子：
3 是模 7 下的原根
2，7 是模 11 下的原根

引理：令 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}\)

推论：令 \(\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 下的原根
原根的数量：如果至少存在一个原根，那么在模 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 的原根

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

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

关键词：