ヘンゼルの補題と7進法人間 - tsujimotterのノートブック

みなさん、ヘンゼルの補題という定理をご存知でしょうか。

ヘンゼルの補題は、整数論についてのとても重要な定理の一つです。 $p$ 進数という、現代の整数論において必須とも言える概念とも深く関連します。

でも、ちょっとだけややこしい。今日はこの定理の紹介を試みようと思います。

ヘンゼルの補題とは

ざっくり言ってしまうと、ある整数係数の多項式 $F(X)$ の $\bmod{p^n}$ における根の存在を保証する定理です。

定理（ヘンゼルの補題）

$p$ を素数とする．整数係数の多項式 $F(X)$ に対して，

$F(x_k) \equiv 0 \pmod{p^k}$ かつ $F'(x_k) \not\equiv 0 \pmod{p}$

なる整数 $x_k$ が存在するならば， $x_{k+1} \equiv x_{k} \pmod{p^k}$ を満たす整数 $x_{k+1}$ が存在し

$F(x_{k+1}) \equiv 0 \pmod{p^{k+1}}$

を満たす．

見てほしいポイントは、この定理が

「 $x_k$ が存在するならば、 $x_{k+1}$ が存在する」

という形になっているという点です。よりよく理解するために、具体例を考えましょう。

p = 7 とします

$p = 7$ として、多項式を

$F(X) = X^2 - 2 \tag{1}$

としましょう。もちろん $F(X)$ は整数係数の多項式なので、定理の条件を満たします。また、条件として使うので、あらかじめ $F(X)$ を微分しておくと

$F'(X) = 2X \tag{2}$

です。これは「普通の意味での微分」を考えればよいです。

さてこの状況で、 $F(X) = 0$ の $\mod{p}$ での解を考えましょう。つまり、

$X^2 - 2 \equiv 0 \pmod{7} \tag{3}$

を満たす $X$ を見つければ良いわけです。 $0$ から $6$ までを代入してみると、 $X = 4$ とすれば合同式 $(3)$ を満たすことがわかります。

$4^2 - 2 = 14 \equiv 0 \pmod{7}$

この $X$ を $x_1$ とおきましょう。つまり、 $x_1 = 4$ です。

次に、 $\bmod{p^2}$ で同じことを考えます。つまり、

$X^2 - 2 \equiv 0 \pmod{7^2} \tag{4}$

を満たす $X$ を見つけます。ただし、一つだけ条件があります。ここで得られた整数 $X$ を $x_2$ としたとき

$x_2 \equiv x_1 \pmod{7}$

を満たす必要があります。 $x_2$ には $0$ から $48$ までの整数が入るはずですが、これをさらに $7$ で割ったあまりを考えたときに、 $x_1 = 4$ と一致しなければならないということです。つまり、 $x_2$ は「7で割って4あまる数」の中から探しなさいということですね。

このような条件のもと、 $x_2$ を探すと・・・ $x_2 = 39$ が見つかります。実際、

$39^2 - 2 = 1519 \equiv 0 \pmod{7^2}$

となり、合同式 $(4)$ を満たすことがわかります。

さて、だんだんと計算が大変になってきましたが、もう一つだけやってみましょう。 $\bmod{p^3}$ で同じ計算をします。つまり、

$X^2 - 2 \equiv 0 \pmod{7^3} \tag{5}$

を満たす $X$ を見つけます。もちろん条件があって、整数 $X$ を $x_3$ としたとき

$x_3 \equiv x_2 \pmod{7^2}$

を満たす必要があります。 $x_2 = 39$ より、 $x_3$ は「49で割って39あまる数」でなければなりません。

このような条件のもと、 $x_3$ を探すと・・・もはや手計算では厳しいので計算機を使うと、 $x_3 = 235$ です。実際、

$235^2 - 2 = 55223 \equiv 0 \pmod{7^3}$

となり、たしかに合同式 $(5)$ を満たすことが確認できます。

ここまでとんとん拍子に解を見つけることができましたが、ここで疑問に思った方もいるかもしれません。 $\bmod{p}, \; p^2, \; p^3$ と計算して、それぞれ条件を満たす解が見つかってきたわけですが、このまま $p^4, \; p^5, \; p^6, \; \ldots$ と続けていっても同じように解が見つかるのでしょうか。それとも、途中で終わってしまうのでしょうか。

ヘンゼルの補題が主張するのは「このままずっと解が見つかり続ける」ということです。

定理の主張は

「 $x_k$ が存在するならば、 $x_{k+1}$ が存在する」

というものでした。まるで数学的帰納法のようだと思ったかもしれません。実際、まさに数学的帰納法になっていて、 $\bmod{p^k}$ の解が存在するならば、その次の $\bmod{p^{k+1}}$ の解も存在する。 $\bmod{p^{k+1}}$ の解が存在するならば、またその次の $\bmod{p^{k+2}}$ の解も存在する。このように、ずっと解が見つかり続けるのです。最初に $\mod{p^k}$ で解が見つかれば・・・という条件付きですが。今回の例では、 $\mod{p}$ の時点で解が見つかりましたので、その先もずっと解が見つかり続けることになります。

おっと、重要な条件を忘れていました。「 $F'(x_k) \not\equiv 0 \pmod{p}$ 」という条件です。今回見つけた解は、 $x_1 = 4, \; x_2 = 39, \; x_3 = 235, \; \cdots$ でしたが、これらを $F'(X) = 2X$ に代入したとき、 $p$ で割り切れてはいけません。実際

$F'(x_1) = 2\cdot 4 \not\equiv 0 \pmod{7}$

$F'(x_2) = 2\cdot 39 \not\equiv 0 \pmod{7}$

$F'(x_3) = 2\cdot 235 \not\equiv 0 \pmod{7}$

となって無問題です。よくよく考えてみれば、 $x_1 \equiv 4 \pmod{7}$ で、以降はすべて $\bmod{7}$ であまり $4$ が変わらないので、 $x_1$ だけ確認すれば十分でしたね。

というわけで、ここまでがヘンゼルの補題の確認です。少しはわかったかもしれませんが、まだ腑に落ちない人もいるかもしれませんね。

そんなあなたのために、ここで一つとっておきの解決策を考えました。それは「7進法人間になる」ということです。

7進法で考えよう

遠い昔インドで 0 という数字が発明され、フィボナッチが著書「Liber Abaci」でアラビア数字をヨーロッパ全土に広めて以来、人類は10進法に親しんできました。10進法というシステムは実に便利で、わずか0から9までの10個の数を並べることによって、任意の自然数を表記することが可能となります。これによって、数学や計算の技術は一気に花開いたといってもいいでしょう。

とはいえ、10進法は完全ではありません。10進法を捨て、7進法で考えた方が、実は判りやすいこともあるのです。ヘンゼルの補題に慣れ親しむための第一歩は、7進法人間になることであると、私は主張したい。

ポエムはこの辺にしておいて、7進法をつかうとどうなるか、考えてみましょう。7進法の世界へようこそ。

まず、最初の計算ですが

$X^2 - 2 \equiv 0 \pmod{7}$

の解 $X$ を求めよ、というものでした。この問題を我々「7進法人間」が見るとこうなります。

「 $X^2 - 2$ の下1桁が 0 になるような $X$ を求めよ」

なんとわかりやすそうな。これなら小学生でも理解できそうじゃないですか。実際 $X = 4$ として、7進法で計算してみましょう。

$4^2 - 2 = 22 - 2 = 20$

たしかに、結果が $2$ $0$ なので、下一桁は $0$ になりますね！

いいですか、7進法ですよ。 $4 \times 4 = 16$ じゃないんですよ。 $4 \times 4 = 22$ ですからね。九九から覚え直してください。あ、九九じゃなくて六六か。

$x_1 = 4$ と求まりました。この調子でもう一個いってみましょう。

次は、

$X^2 - 2 \equiv 0 \pmod{7^2}$

の解 $X$ を求めよ、というものでした。この問題は「7進法人間」によると

「 $X^2 - 2$ の下2桁が 0 になるような $X$ を求めよ」

です。「下2桁が2になるような平方数」といっても良さそうですね。ただし、この $X$ を $x_2$ とすると、

「 $x_2$ と $x_1$ の下1桁は等しい」

となります。おお、条件までわかりやすくなってしまった！！

さて、そんな条件をみたす $x_2$ の候補は

$x_2 = 4, \; 14, \; 24, \; 34, \; 44, \; 54, \; 64$

の中にあるわけです。うおお、下1桁が全部 4 だから、わかりやすいですね。この中で2乗して下2桁が2になる数はというと、 $x_2 = 54$ ということになります。もちろん7進法です。

こんな風に、7進法の計算に慣れておくと、ヘンゼルの補題の意味がより明確になるのです。この調子で計算結果を並べていくと

$x_1 = 4$

$x_2 = 54$

$x_3 = 454$

$x_4 = 454$

$x_5 = 50454$

$x_6= 450454$

$x_7 = 5450454$

$x_8 = 25450454$

となります。 $x_{k+1}$ の下 $k$ 桁が $x_k$ に一致することが一目でわかりますね！

要するにヘンゼルの補題は「k桁以下は一致して、多項式の根になるk+1桁目が作れまっせ」という話なのです。数学的帰納法より、1桁目に解があれば、無限に桁を伸ばし続ける「奇妙な数」を作ることができる、ということでもありますね。

ちょっとだけ発展的なお話

ヘンゼルの補題の意味をわかっていただけたところで、少しだけ発展的なお話を。

実は、今回の話は $p$ 進数まであと一歩のところまで迫っています。ヘンゼルの補題は、 $F(X)$ の根が $\bmod{p^k}$ で見つかれば、以降ずっと見つかり続けることを主張していました。無限に続くのですね。この無限に続く $F(X) \bmod{p^k}$ の根を以下のように形式的に並べることにします。

$(4, 54, 454, 454, 50454, 450454, 5450454, 25450454, \cdots)$

このような形式的な列を数とみなしてみよう、というのがp進数の発想です。これを仮に ${\bf x}$ とおいて、列の $k$ 番目の値を $x_k$ とします。すると、それぞれの $x_k$ においては $\bmod{p^k}$ で普通に足し算・引き算・掛け算ができる。どれも、それぞれの列の中では、2乗して $2$ を引くと $0$ になる数となっている。それぞれの列の演算をまとめることで、 ${\bf x}$ の演算とみなしてしまうのです。すると

${\bf x}^2 - 2 = 0$

が成り立っていると考えることはできないでしょうか。「そんなことしていいの？」と思うかもしれません。しかし、ヘンゼルの補題によると、各 $\bmod{p^k}$ の無限の演算が整合性を保つことが保証されています。

こうして、先ほどの無限に続く数の列自体を数とみなすことができ、なおかつ、足し算・引き算・掛け算が定義できる。このような数の集合を $p$ 進整数環 $\mathbb{Z}_p$ といいます。こうしてp進数という概念が生まれていくわけですね。

参考までに、 $p$ 進整数環 $\mathbb{Z}_p$ の定義は以下の通りです：

$\mathbb{Z}_p := \{ (x_{k})_{k \in \mathbb{N}} \;\; | \;\; k \in \mathbb{N},\; x_k \in \mathbb{Z}/p^k \mathbb{Z},\; x_{k+1} \equiv x_k \pmod{p^k} \}$

条件としてついている $x_{k+1} \equiv x_k \pmod{p^k}$ は「下 $k$ 桁は一致する」という条件に読みかえられますね。この集合に

$(x_{k})_{k \in \mathbb{N}} + (y_{k})_{k \in \mathbb{N}} := (x_{k}+y_{k})_{k \in \mathbb{N}}$

$(x_{k})_{k \in \mathbb{N}}(y_{k})_{k \in \mathbb{N}} := (x_{k}y_{k})_{k \in \mathbb{N}}$

として自然に和と積を入れると環になります。また、 $p$ が素数のときは整域であることが示せます。これが $p$ を素数とした理由です。

整域にはその商体がとれるので、この $\mathbb{Z}_p$ の商体として $p$ 進数体 $\mathbb{Q}_p$ が定義されます。 $\mathbb{Q}_p$ の元のことを「 $p$ 進数」と呼びます。

ところで、先の例の式 $(1)$ は $F(X) = X^2 - 2$ というものでしたが、このような $F(X)$ の根は「2乗して2に一致する数」、すなわち、 $\sqrt{2}$ です。我々は、7進整数の世界に $\sqrt{2}$ を発見したのです。

系

$\sqrt{2} \in \mathbb{Z}_7$

普通の整数の世界には $\sqrt{2}$ は存在しませんでしたから、 $\mathbb{Z}_7$ は $\mathbb{Z}$ よりも真に大きい世界であるというわけですね。

ピタゴラスもびっくり！*1

おわりに

というわけで、今回は「ヘンゼルの補題」の紹介を試みました。最初は、難しそうだなと思ったかもしれませんが、7進法人間になってみるとずいぶん自然な概念であることがわかっていただけたのではないでしょうか。

まだ、7進法人間になりきれていないという方もいるかもしれません。そんなあなたは、以下を試してみてはいかがでしょうか？
togetter.com

それでは今日はこの辺で。

*1:「万物は数なり」として自然数とその比で表せる数を崇拝した古代の数学者。 $\sqrt{2}$ が無理数であることを世に広めようとした弟子を海に沈めたという「逸話」で有名。本当か嘘かは知りません。