Hensel引理

数论中的Hensel引理

f(x)为整系数多项式,k\geq2\in \Z,p\in prime,f(r) \equiv 0 \pmod {p^{k-1}},则有

  • f'(r) \equiv\not 0\pmod p,\exists!t,0\geq t \geq p,s.t. \ f(r+tp^{k-1})\equiv0\pmod{p^k}​,其中

t=-\overline{f'(r)}{{f(r)}\over p^{k-1}}\pmod p

  • f'(r)\equiv0\pmod p ,f(r)\equiv0 \pmod {p^{k}},则\forall t都有f(r+tp^{k-1})\equiv0\pmod {p^k}

  • f'(r)\equiv0\pmod p ,f(r)\equiv\not0 \pmod {p^{k}},则f(x)\equiv0\pmod{p^k}不存在解s.t.\ x\equiv r \pmod {p^{k-1}}

证明

(latex写的太累人了,咕了)思路就是在f(r+tp^{k-1})处泰勒展开,化简,分类讨论解出t即可。

这个东西可以用来从f(x)\equiv 0 \pmod p的解求f(x)\equiv 0 \pmod {p^k}的解,在k较大时,这个东西就很高效了。因为暴力解f(x)\equiv 0 \pmod {p^k}需要p^k次计算,而利用Hensel引理计算量小于pk

需要注意的是,第三条判断只能说明方程在p^{k-1}的解不能提升为p^k的解,并不是判定方程在p^k无解

参考资料

ElementaryNumberTheory \ and \ Its Applications(Sixth \ Edition),Kenneth H.Rosen,Pearson Edu. Inc.

本文符号说明

\overline a \pmod p表示a在模p的逆
f'(x)表示f(x)的导函数

发表评论

电子邮件地址不会被公开。 必填项已用*标注