書記が数学やるだけ#910 多項式におけるヘンゼルの補題

ヘンゼルの補題の初等的な証明を示しておく。

問題

説明

ヘンゼルの補題とは、1変数多項式が素数 p を法として単根を持つならば、その根は p の任意の冪乗を法とする根に一意的に持ち上げられるという、合同算術における補題である。ヘンゼルの補題の証明は構成的であり、証明からヘンゼル持ち上げの効率的なアルゴリズムが得られる。

解答

整数係数多項式 f(x) に対して x = a + ph を代入し，展開したときの各項に注目すると，(ph)^2 以上の項はすべて p^2 の倍数となるため，p mod p^2 においては 0 とみなせる。その結果、線形近似の式が得られる。

この剰余体において 0 でない元は必ず乗法逆元を持つ。これは、後続のステップで「h についての1次方程式」を解く際に、係数 f'(a) で割る（逆元を掛ける）操作が可能であることを保証している。

(1)の式を整理すると，h f'(a) ≡ -f(a)/p mod p となる。(2)より f'(a) の逆元が存在するため、この h は mod p で必ず存在し、結果として b = a + ph  mod p^2 が求められる。a_n から a_{n+1} への持ち上げも同様にして示せる。

一意性の証明は以下の通り。

n を p^2 の倍数 x p^2 に制限した多項式 f(x) = x p^2 C p^2 を定義する。 Lucasの定理を用いると，この関数は mod p において f(x) ≡ x mod p という形になる。 f(x) ≡ x mod p の微分より f’(x) ≡ 1 mod p より，ヘンゼルの補題の適用条件を満たしていることから，ヘンゼル持ち上げにより mod p^3 について式が示せる。

本記事のもくじはこちら：