ヘンゼルの補題と p 進数での根

$f \in Z_{p} [x]$ と $f (a) \equiv 0$ 、 $f^{'} (a) \neq \equiv 0 (mod p)$ をみたす $a$ から、 $a_{k + 1} = a_{k} - f (a_{k}) / f^{'} (a_{k})$ で $Z_{p}$ の根を一意に持ち上げ、根を法 $p^{k}$ で求められる。 $f^{'} (a) \equiv 0$ のときは $v_{p} (f (a)) > 2 v_{p} (f^{'} (a))$ を確かめて強い形を使い、根の付値で $x = p^{k} y$ と置きかえて $Q_{p}$ での根の個数を数えられる（例: $x^{2} = 2$ の $Z_{7}$ の根で $x \equiv 3 (mod 7)$ のものは $x \equiv 10 (mod 49)$ ）

前提

p 進付値と p 進収束（大学院数学代数的整数論）
合同式（数学A 整数の性質）
多項式の微分（数学II 微分法と積分法）

この技能までの道筋（29 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

倍数の個数（算数整数の性質）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
階乗に含まれる素因数の個数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
n 進法（数学A 整数の性質）
等間隔にならんだ数の和（算数計算と数のきまり）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
無限等比級数と無限級数（数学III 極限）
p 進付値と p 進収束（大学院数学代数的整数論）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）

説明

ヘンゼルの補題は、 $Z_{p}$ 係数の多項式 $f$ について、法 $p$ での根 $a$ を法 $p^{2}, p^{3}, \dots$ での根へ一意に持ち上げ、 $Z_{p}$ の本当の根を得る方法です。 $f (a) \equiv 0$ かつ $f^{'} (a) \neq \equiv 0 (mod p)$ を確かめれば、 $x \equiv a (mod p)$ を満たす $Z_{p}$ の根がちょうど 1 つあると結論でき、その $p$ 進展開を好きな桁まで計算できます。 $f^{'} (a) \equiv 0 (mod p)$ のときも、付値の不等式 $v_{p} (f (a)) > 2 v_{p} (f^{'} (a))$ が成り立てば根の存在と一意性が言えます。これらを組み合わせると、 $Z_{p}$ や $Q_{p}$ での根の個数を数えられます。

なぜそうしてよいのか

以下 $v = v_{p}$ と書き、 $Z_{p} = {x \in Q_{p} : v (x) \geq 0}$ 、そのうち $v (x) = 0$ の元（法 $p$ で逆元をもつ元、単数）全体を $Z_{p}^{\times}$ と書きます。付値の性質 $v (x y) = v (x) + v (y)$ 、 $v (x + y) \geq min (v (x), v (y))$ 、および $v (x) < v (y)$ なら $v (x + y) = v (x)$ を使います。鍵は「ずらし展開」です。 $x = a + h$ を代入して $(a + h)^{n}$ を二項展開すると、 $h$ の 1 次の係数は $\sum n c_{n} a^{n - 1} = f^{'} (a)$ なので $f (a + h) = f (a) + f^{'} (a) h + h^{2} g (a, h)$ （ $g$ は $Z_{p}$ 係数の多項式）と書けます。同じように $f^{'} (a + h) = f^{'} (a) + h k (a, h)$ （ $k$ も $Z_{p}$ 係数）で、特に $v (f (x) - f (y)) \geq v (x - y)$ です。いま $f (a) \equiv 0 (mod p^{k})$ （ $k \geq 1$ ）、 $f^{'} (a) \neq \equiv 0 (mod p)$ とし、 $h = p^{k} t$ （ $t \in Z$ ）とおくと、 $h^{2}$ の項は $p^{2 k}$ で割り切れ $2 k \geq k + 1$ なので $f (a + p^{k} t) \equiv f (a) + f^{'} (a) p^{k} t (mod p^{k + 1})$ です。これが $0$ になる条件は $\frac{f ( a )}{p ^{k}} + f^{'} (a) t \equiv 0 (mod p)$ で、 $f^{'} (a)$ は法 $p$ で逆元をもつから $t$ は法 $p$ でただ 1 つに決まります。 $f^{'} (a + p^{k} t) \equiv f^{'} (a) \neq \equiv 0 (mod p)$ なので次の段でも同じことができ、得られる $a_{1} = a, a_{2}, a_{3}, \dots$ は $v (a_{k + 1} - a_{k}) \geq k$ を満たして $Z_{p}$ の元 $α$ に収束します。 $v (f (α) - f (a_{k})) \geq v (α - a_{k}) \geq k$ と $v (f (a_{k})) \geq k$ から、すべての $k$ で $v (f (α)) \geq k$ 、つまり $f (α) = 0$ です。各段で $t$ が一意なので、 $α \equiv a (mod p)$ を満たす根はこれだけです。なお $h = - f (a) / f^{'} (a)$ と一度に取る（ニュートン法）と $f (a + h) = h^{2} g (a, h)$ となり、 $f (a) \equiv 0 (mod p^{k})$ から $f (a + h) \equiv 0 (mod p^{2 k})$ と正しい桁数が倍になります。このとき $f (a)$ は $p^{k}$ で割り切れるので、 $f (a) \cdot f^{'} (a)^{- 1}$ を法 $p^{2 k}$ で正しく求めるには $f^{'} (a)$ の逆元を法 $p^{k}$ で取る必要があります。

$f^{'} (a) \equiv 0 (mod p)$ のときは $δ = v (f^{'} (a))$ 、 $e = v (f (a))$ とおき、 $e > 2 δ$ を仮定します。 $h = - f (a) / f^{'} (a)$ は $v (h) = e - δ > δ \geq 0$ なので $Z_{p}$ に入ります。 $a^{'} = a + h$ とすると $f (a^{'}) = h^{2} g (a, h)$ より $v (f (a^{'})) \geq 2 (e - δ)$ 、言いかえると $v (f (a^{'})) - 2 δ \geq 2 (e - 2 δ)$ で、「 $2 δ$ を超える分」が 2 倍以上になります。また $f^{'} (a^{'}) = f^{'} (a) + h k (a, h)$ で $v (h k (a, h)) \geq v (h) > δ$ だから $v (f^{'} (a^{'})) = δ$ のままです。よって同じ操作をくり返せて、差 $a_{j + 1} - a_{j}$ の付値 $v (f (a_{j})) - δ$ は $\infty$ に向かうので根 $α$ に収束し、2 段目以降の差の付値は最初の差の付値 $e - δ$ より大きいので $v (α - a) = e - δ > δ$ です。一意性: $β$ も $v (β - a) > δ$ を満たす根なら、 $v (β - α) > δ$ であり、 $0 = f (β) - f (α) = (β - α) (f^{'} (α) + (β - α) g (α, β - α))$ です。 $f^{'} (α) = f^{'} (a) + (α - a) k (a, α - a)$ より $v (f^{'} (α)) = δ$ 、第 2 項の付値は $δ$ より大きいので括弧の中の付値はちょうど $δ$ で $0$ でなく、 $β = α$ となります。まとめると（強い形）: $v (f (a)) > 2 v (f^{'} (a))$ ならば、 $v (x - a) > δ$ 、すなわち $x \equiv a (mod p^{δ + 1})$ を満たす根がただ 1 つあり、それは $v (α - a) = v (f (a)) - v (f^{'} (a))$ を満たします（ $f (a) = 0$ なら $α = a$ ）。 $δ = 0$ の場合が通常の形です。

$Q_{p}$ の根を数えるには、 $f (x) = \sum_{i = 0}^{n} c_{i} x^{i}$ （ $c_{i} \in Z_{p}$ 、 $c_{0} \neq = 0$ 。 $c_{0} = 0$ なら $x$ をくくり出す）の根 $x \neq = 0$ を $x = p^{k} y$ （ $k = v (x) \in Z$ 、 $y \in Z_{p}^{\times}$ ）と書きます。項 $c_{i} x^{i}$ の付値は $v (c_{i}) + ik$ なので、最小の付値をとる項がただ 1 つなら和の付値はその最小値に等しく、 $f (x) = 0$ になれません。したがって根の付値 $k$ は「 $min_{i} (v (c_{i}) + ik)$ が 2 つ以上の $i$ で達成される」ものに限られ、そのような $k$ は有限個です。各候補 $k$ について $m = min_{i} (v (c_{i}) + ik)$ とし $g (y) = p^{- m} f (p^{k} y)$ を作ると、 $g$ は $Z_{p}$ 係数で法 $p$ で $0$ でない多項式になり、 $f$ の付値 $k$ の根と $g$ の $Z_{p}^{\times}$ に属する根が 1 対 1 に対応します。 $y$ を単数に限るので、異なる $k$ で同じ根を二重に数えることはありません。

手順

法 $p$ の根を探す: $f (b) \equiv 0 (mod p)$ となる $b$ を $b = 0, 1, \dots, p - 1$ で調べる
各根 $a$ で $f^{'} (a) mod p$ を計算する。 $f^{'} (a) \neq \equiv 0$ なら $x \equiv a (mod p)$ を満たす $Z_{p}$ の根がちょうど 1 つある。法 $p^{k}$ の根 $a_{k}$ から $x = a_{k} + p^{k} t$ とおき、 $\frac{f ( a _{k} )}{p ^{k}} + f^{'} (a_{k}) t \equiv 0 (mod p)$ を解いて $t$ （ $0 \leq t < p$ ）を決め、目的の法までくり返す
（桁を速く増やすとき）ニュートン法 $a^{'} = a_{k} - f (a_{k}) u$ を使う。 $a_{k}$ が法 $p^{k}$ で正しいなら $a^{'}$ は法 $p^{2 k}$ で正しく、 $u$ は $f^{'} (a_{k})$ の法 $p^{k}$ での逆元とする。最後に $f (a) \equiv 0 (mod p^{k})$ を検算する
$f^{'} (a) \equiv 0 (mod p)$ のときは、整数の代表 $a$ について $δ = v_{p} (f^{'} (a))$ 、 $e = v_{p} (f (a))$ を求め、 $e > 2 δ$ を確かめる。成り立てば $x \equiv a (mod p^{δ + 1})$ の中に根がただ 1 つあり、 $v_{p} (α - a) = e - δ$ 。値は $a^{'} = a - \frac{f ( a ) / p ^{δ}}{f ^{'} ( a ) / p ^{δ}}$ （分母は単数なので法 $p$ 以上の逆元を掛ける）をくり返して求める
手順 4 の不等式が成り立たないときは、 $m = 2, 3, \dots$ と順に、 $b \equiv a (mod p)$ を満たす法 $p^{m}$ のすべての $b$ を調べる: $f (b) \neq \equiv 0 (mod p^{m})$ なら $x \equiv b (mod p^{m})$ に根はないので捨てる。 $v_{p} (f (b)) > 2 v_{p} (f^{'} (b))$ なら $x \equiv b (mod p^{v_{p} (f^{'} (b)) + 1})$ にただ 1 つ根があると記録する。どちらでもなければ法 $p^{m + 1}$ に進む。記録した範囲どうしが重なれば同じ根なので 1 つと数える（ $f$ が重根をもたなければ有限回で終わる）
$Q_{p}$ の根を数えるときは、 $f = \sum c_{i} x^{i}$ の根を $x = p^{k} y$ （ $k \in Z$ 、 $y \in Z_{p}^{\times}$ ）と書き、 $min_{i} (v_{p} (c_{i}) + ik)$ が 2 つ以上の $i$ で達成される $k$ だけを候補にする。各 $k$ で $m = min_{i} (v_{p} (c_{i}) + ik)$ 、 $g (y) = p^{- m} f (p^{k} y)$ とし、 $g$ に手順 1〜5 を適用して $y \neq \equiv 0 (mod p)$ の根だけを数え、すべての $k$ について足す

例題

$f (x) = x^{2} - 17$ とする。 $Z_{2}$ における $f$ の根 $α$ で $α \equiv 1 (mod 4)$ を満たすもの（ただ 1 つ存在する）について、 $α \equiv r (mod 64)$ 、 $0 \leq r < 64$ となる整数 $r$ を求めよ。

例題の解答

手順 1: $f (0) = - 17$ は奇数、 $f (1) = - 16 \equiv 0 (mod 2)$ なので、法 $2$ の根は $a = 1$ 。

手順 2: $f^{'} (x) = 2 x$ より $f^{'} (1) = 2 \equiv 0 (mod 2)$ 。通常の形は使えないので手順 4 へ進む。

手順 4: $δ = v_{2} (f^{'} (1)) = v_{2} (2) = 1$ 、 $e = v_{2} (f (1)) = v_{2} (- 16) = 4$ で、 $4 > 2 \cdot 1$ が成り立つ。よって $x \equiv 1 (mod 2^{2})$ を満たす根はただ 1 つで、これが $α$ 。

値を求める: $a^{'} = 1 - \frac{f ( 1 ) /2}{f ^{'} ( 1 ) /2} = 1 - \frac{- 8}{1} = 9$ 。 $a^{'} = 9$ でも $f (9) = 64$ 、 $f^{'} (9) = 18$ より $e = v_{2} (64) = 6$ 、 $δ = v_{2} (18) = 1$ で $6 > 2$ 。 $9 \equiv 1 (mod 4)$ なので、 $9$ のまわりの根も同じ $α$ であり、 $v_{2} (α - 9) = e - δ = 6 - 1 = 5$ 。つまり $α \equiv 9 (mod 32)$ だが $α \neq \equiv 9 (mod 64)$ なので、 $α \equiv 9 + 32 = 41 (mod 64)$ 。

（もう 1 回ニュートン法を使っても確かめられる: $a^{''} = 9 - \frac{64/2}{18/2} = 9 - 32 \cdot 9^{- 1}$ 。 $32 \cdot 9^{- 1}$ を法 $64$ で求めるには $9^{- 1}$ を法 $2$ で取れば足り、 $9^{- 1} \equiv 1$ より $a^{''} \equiv 9 - 32 = - 23 \equiv 41 (mod 64)$ 。このとき $v_{2} (α - a^{''}) = v_{2} (f (a^{''})) - 1 \geq 2 (6 - 1) - 1 = 9$ なので $α \equiv a^{''} (mod 2^{9})$ 。）

検算: $4 1^{2} - 17 = 1681 - 17 = 1664 = 2^{7} \cdot 13$ で $f (41) \equiv 0 (mod 64)$ 。なお $x^{2} \equiv 17 (mod 64)$ の解は $9, 23, 41, 55$ の 4 つあり、 $9$ と $41$ はどちらも $\equiv 1 (mod 4)$ なので、法 $64$ の合同式を解くだけでは $r$ は決まらない。強い形で根の位置 $v_{2} (α - 9) = 5$ まで追うことで $r = 41$ と決まる。

答え: $41$

よくある誤り

$f (a) \equiv 0 (mod p)$ だけで $Z_{p}$ に根があると結論してしまう誤り。正しくは $f^{'} (a) \neq \equiv 0 (mod p)$ か、強い形の条件 $v_{p} (f (a)) > 2 v_{p} (f^{'} (a))$ が必要で、どちらも成り立たなければ手順 5 で調べる。たとえば $f (x) = x^{2} - 5$ 、 $p = 2$ 、 $a = 1$ では $f (1) = - 4 \equiv 0 (mod 2)$ だが、 $v_{2} (- 4) = 2$ は $2 v_{2} (f^{'} (1)) = 2 v_{2} (2) = 2$ より大きくない。手順 5 で法 $8$ まで調べると、奇数 $b$ では $b^{2} \equiv 1 (mod 8)$ より $f (b) \equiv - 4 \neq \equiv 0 (mod 8)$ 、偶数 $b$ では $f (b)$ は奇数なので、 $Z_{2}$ に根はない。
持ち上げで $f (a_{k})$ を $p^{k}$ で割り忘れる誤り。 $f (x) = x^{2} + 1$ 、 $p = 5$ で法 $25$ の根 $a_{2} = 7$ （ $f (7) = 50$ 、 $f^{'} (7) = 14$ ）から法 $125$ へ進むとき、 $50 + 14 t \equiv 0 (mod 5)$ とすると $t \equiv 0$ となり $7$ のままになるが、 $7^{2} + 1 = 50 \neq \equiv 0 (mod 125)$ である。正しくは $\frac{50}{25} + 14 t = 2 + 14 t \equiv 0 (mod 5)$ より $4 t \equiv 3$ 、 $t \equiv 2$ で $a_{3} = 7 + 2 \cdot 25 = 57$ （ $5 7^{2} + 1 = 3250 = 125 \cdot 26$ ）。
倍々のニュートン法で $f^{'} (a_{k})^{- 1}$ を法 $p$ だけで取ってしまう誤り。 $f (x) = x^{2} + 1$ 、 $p = 5$ で法 $25$ の根 $a_{2} = 7$ から法 $5^{4} = 625$ の根を作るとき、 $1 4^{- 1} \equiv 4 (mod 5)$ を使うと $7 - 50 \cdot 4 = - 193 \equiv 432 (mod 625)$ となるが、 $43 2^{2} + 1 = 186625 \equiv 375 \neq \equiv 0 (mod 625)$ で誤り。 $f (7) = 50$ は $25$ で割り切れるので、 $50 u$ を法 $625$ で正しく求めるには $u$ を法 $25$ で正しく取る必要がある。正しくは $1 4^{- 1} \equiv 9 (mod 25)$ （ $14 \cdot 9 = 126$ ）を使い、 $7 - 50 \cdot 9 = - 443 \equiv 182 (mod 625)$ （ $18 2^{2} + 1 = 33125 = 625 \cdot 53$ ）。
強い形の結論を「 $x \equiv a (mod p)$ を満たす根がただ 1 つ」と読んでしまう誤り。正しくは一意なのは $v_{p} (x - a) > v_{p} (f^{'} (a))$ 、すなわち $x \equiv a (mod p^{δ + 1})$ の範囲の中だけである。 $f (x) = x^{2} - 17$ 、 $p = 2$ では $a = 1$ から得られる根 $α$ は $α \equiv 1 (mod 4)$ の範囲で一意だが、 $a = 3$ でも $v_{2} (f (3)) = v_{2} (- 8) = 3 > 2 = 2 v_{2} (f^{'} (3))$ が成り立ち、 $x \equiv 3 (mod 4)$ の範囲にもう 1 つの根 $- α$ がある。 $Z_{2}$ の根は奇数の根が 2 つで、「法 $2$ の根 $1$ から 1 つ」と数えると個数を誤る。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$f (x) = x^{2} + 1 \in Z_{5} [x]$ とする。 $5$ 進整数環 $Z_{5}$ における $f$ の根 $α$ のうち、 $α \equiv 2 (mod 5)$ をみたすものがただ 1 つ存在する。 $α \equiv n (mod 125)$ をみたす整数 $n$ （ $0 \leq n \leq 124$ ）を求めよ。

ヘンゼルの補題と p 進数での根

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題