ヘンゼルの補題

数学のヘンゼルの補題（ヘンゼルのほだい、）とは、1変数多項式が素数 を法としてを持つならば、その根は の任意の冪乗を法とする根に一意的に持ち上げられるという、合同算術における補題である。この補題は、多項式が法 で2つのに因数分解できるならば、その因数分解は の任意の冪乗を法とする因数分解に持ち上げることができるという補題に一般化できる。因数分解に現れる多項式の次数が1の場合が根の場合に相当する。ヘンゼルの持ち上げ補題（）とも呼ばれる。名称はクルト・ヘンゼルに因む。

 の冪指数を無限に大きくしていったときの（射影極限の意味での）極限を取ることにより、法 での根（または因数分解）を 進整数上での根（または因数分解）に持ち上げることができる。

この補題は、任意の可換環を係数とする多項式に対して、 をイデアル、「互いに素な2つの多項式」を「2つの多項式が生成するイデアルが1を含む」に置き換えることにより一般化できる。一般化された補題も同じ名前で呼ばれる。

ヘンゼルの補題は、解析的整数論の一分野である 進解析学の基礎である。

ヘンゼルの補題の証明はであり、証明からヘンゼル持ち上げの効率的なアルゴリズムが得られる。これは多項式の因数分解のアルゴリズムの基礎である。また有理数体上の線型代数学についての最も効率の良いアルゴリズムが得られる。

ヘンゼルの補題は、ヘンゼルよりも早く1846年にによって証明されていた。また、「存在」についての主張だけならシェーネマンよりも早くカール・フリードリヒ・ガウスによっても知られていた。

還元と持ち上げ

もともとのヘンゼルの補題は、整数を係数とする多項式の因数分解と、素数 、もしくはその冪乗を法とする剰余類環を係数とする多項式の因数分解との関係についてのものであった。素数
 を極大イデアルに置き換えることで、この補題は整数から任意の可換環へそのまま一般化できる（ の極大イデアルはある素数 で と書けるのであった）。

この一般化を正確に書くためには、整数の場合の合同算術を一般化しておく必要があるので、この文脈で通常使われる用語を正確に定義しておこう。

 を可換環、 を のイデアルとする。
の元を

による像で置き換えることを、 を法とする還元、または法 での還元と呼ぶ。

例えば、
を

係数の多項式とするとき、その

を法とする還元

とは、 の係数を

での像に置き換えることで得られる

の多項式のことをいう。
の2つの多項式 と が法
 で係数が等しくなるとき、つまり

であるとき、この2つの多項式は法 で合同であるといい、
で表す。
の法 での因数分解とは、 を法 で

の2つ（以上）の多項式 の積として書き表す

ことをいう。

持ち上げとは還元の逆の操作である。つまり、
の元を使って表されている対象があったとき、持ち上げとは対象の性質を保ったまま還元するとこの対象に等しくなるように
（もしくはある に対する ）の元に置き換えることをいう。

例えば、多項式

が法 で

と因数分解されているとき、この因数分解を法

へ持ち上げるとは、多項式

であって

を満たすものを見つけることである。ヘンゼルの補題は、この因数分解の持ち上げが緩い条件のもとで常に可能であることを主張するものである。

 ヘンゼルの補題の主張 

元々のヘンゼルの補題は、整数を係数とする多項式の素数 を法とする因数分解を
 の冪乗を法とする因数分解、もしくは
 進整数環上の因数分解に持ち上げることを主張（そして証明）するものであった。この補題は、整数を任意の可換環、素数を極大イデアル、そして
 進整数環をその極大イデアルについての完備化に置き換えることで簡単に一般化できる。証明の仕方も同じである。この一般化された補題も広く用いられる。本記事で述べるのもこれである。

 を可換環、 をその極大イデアルの1つ、そして

を

の多項式で最高次の係数

が

に含まれないものとする。

を極大イデアルとしているので、
その剰余環

は体である。したがって

は単項イデアル整域なので、
特に一意分解環である。これは、任意のゼロではない

の多項式は

のゼロでない元とモニック（最高次の係数が1という意味）な既約多項式の積として一意的にかけることを意味する。

ヘンゼルの補題は、 の法

での互いに素な多項式への因数分解は、任意の

に対して

を法とする因数分解に一意的に持ち上げられることを主張する。

もう少し詳しく書くと、上述の仮定のもとで、法
 でモニックかつな多項式
 と 
を使って

と分解できたとすると、全ての正の整数 に対してモニック多項式

と

が存在して次の式

が成り立ち、しかもこのような性質を持つ

と

は法

で一意ということを主張する。

単根の持ち上げ

大切で特別な場合として

であるときを考える。この場合、互いに素という仮定は
 は

の単根であるということを意味する。したがってこの場合にはヘンゼルの補題の主張は次のようになる（これもヘンゼルの補題と言われる）。

記号と仮定は今までと同じとし、 を

の単根とする。このとき、 は全ての正の整数 に対して

の単根に一意的に持ち上げることができる。つまり、任意の正の整数 対して

の単根

であって

を満たすものが一意的に存在する。

完備化への持ち上げ

全ての正の整数 に対して

に持ち上げることができるので、
を限りなく大きくしていったときの"極限"を考えたくなる。これが 進整数が考案された主な理由の1つである。

 を可換環、
を極大イデアルとすると、
のベキたちは
 の 進位相と呼ばれる位相についての基本近傍系になる。この位相による完備化は局所環

の完備化と同一視でき、また射影極限

とも同一視できる。この完備局所環は

と一般的に書き表される。 が整数環で
（ は素数）であるときには、この完備局所環は 進整数環

である。

完備化の射影極限を使った定義と上述のヘンゼルの補題の主張から、多項式

の法

での因数分解がどの2つの因子を取っても互いに素であるなら、それは

の

における像の因数分解に一意的に持ち上げられることが導かれる。同様に、 の法

での任意の単根は
 の

における像の単根に持ち上げられる。

証明

ヘンゼルの補題は、
での因数分解を

での因数分解に持ち上げる（#1次持ち上げ）ことを繰り返すか、または

での因数分解に持ち上げる（#2次持ち上げ）ことを繰り返すことにより証明されることが多い。

証明では、体を係数とするに対してベズーの等式が成り立つということが重要な役割を果たす。ベズーの等式とは、体（ここで使うのは

の場合）を係数とする互いに素な1変数多項式
 と 
があったとすると、ある多項式 と であって、
かつ

かつ次の式

を満たすものが存在するということである。

ベズーの等式が成り立てば

が極大イデアルではなくともヘンゼルの補題を証明することができる。

それゆえ、以下では
 を可換環、 をそのイデアル、 を最高次係数が法 
で可逆（ における像が の可逆元ということ）な多項式、 もしくは の冪乗を法とする
 の因数分解に現れる因子が法 
でベズーの等式を満たす、という設定のもとで証明を行う。証明では、 という式で

であることを表すことにする。

1次持ち上げ

 を可換環、 をそのイデアル、
を

係数の1変数多項式で最高次の係数

が法 で可逆（の における像が の可逆元という意味）であるものとする。

そして何らかの正の整数 に対して

と因数分解でき、 と

はモニック多項式で法

で互いに素だったとする。ここで、"互いに素"というのはある

が存在して

という意味で使っている。このとき、多項式

であって

かつ

かつ次の式

が成り立つものが存在する。しかもこれらの条件が成り立つ

と

は法

で一意的に定まる。

そして

と

は
 と が満たすベズーの等式を同様に満たす。つまり

が成り立つ。なぜ直前の主張からすぐにわかるこのことをあえて述べたかというと、 の値を１つ大きくして反復計算を進めるときに、これが次のステップでの前提条件が満たされていることを意味するからである。

次に示す証明は、
または

を係数とする多項式だけを使って

と

を計算することによりなされている。
で

の場合には、これは法
 での剰余類だけを使って計算できることを意味する。

証明： 仮定から

は法 で可逆である。したがって、ある

と

で

を満たすものが存在する。

多項式

を、次数が

未満で

が成り立つものとする。
と置いてもよいが、他のものを選んだ方が計算が簡単になることがある。例えば

で

の場合には、係数が区間 
に入る整数係数の多項式

を使って

と表せるようなものを取ることができるので、こう取ったほうがよい。

 はモニックなので、多項式に対する除法の原理を

と
 に適用し、 と で

かつ

となるものを見つけることができる。この
 と は

に入っている。同様に、 で

かつ

となるものを取る。

このとき

である。実際、まず

が成り立っている。
はモニックなので、
の法

での次数が

の次数よりも小さくなるのは

のときだけである。

こうして、

を法とする合同を考えることにより次の式

が成り立つことがわかる。そして、

と置けば求めるものになっているので、存在が示せた。

 一意性 

記号 、、、
は前節と同じとする。 が

と、
となる互いに素な多項式（前述の意味で）に因数分解できたとする。1次持ち上げを

に適用して、多項式

と

であって

かつ

かつ次の式

を満たすものの存在がわかる。この多項式

と

は法

で一意に定まる。つまり、同じ条件を満たす組

が他にあったとすると、

が成り立つ。

証明: 
を法とする合同は

を法とする合同を意味するので、
数学的帰納法を使って証明する。
 の場合は明らかである。
 の場合の一意性は証明されているものと仮定する。つまり、

と仮定する。仮定により

が成り立ち、これから

が成り立つ。帰納法の仮定から右辺の2番目の項は

に含まれ、（左辺もそうなので）同じことが初項についても成り立つ。
は法 で可逆なので、ある

と

が存在して

が成り立つ。これと帰納法の仮定から

が成り立つ。

法 で互いに素という仮定から、ある

が存在して

が成り立つ。帰納法の仮定をもう一度使うと

となる。したがって、次数が

未満の多項式が法

でモニック多項式 ともう1つの多項式 の積と合同になったことになる。これが起こり得るのは

の場合だけなので、これから

が得られる。同様に

も

に含まれることが示せるので、これで一意性が証明できた。

2次持ち上げ

1次持ち上げは法

での因数分解を法

での因数分解に持ち上げるものであった。2次持ち上げでは法

での因数分解に一気に持ち上げる。しかし、ベズーの等式の持ち上げも必要になり、（上述の1次持ち上げでは）法
 での計算だけで済んだが法

での計算が必要になるため、追加の計算コストがかかる。

どちらの方法でも大きな
 に対して法

まで持ち上げることができる。例えば

の場合に法

まで因数分解を持ち上げるためには、1次持ち上げを使うと
 回の反復計算が必要になるが、
2次持ち上げを使えば
 回の反復計算で済む。しかし、2次持ち上げを使う方法では扱わなければならない係数のサイズが計算中に増大していく。これは、一番いい持ち上げの方法は、 の値や
 の性質、
使用する乗算アルゴリズム、
ハードウェアの特性などの状況に依存することを意味する。

2次持ち上げは次の性質を利用する。

ある正の整数 に対して因数分解

があったとし、 と はモニック多項式で、ある

が存在し

が成り立つという意味で法

で互いに素だったとする。このとき、ある多項式

が存在し、
かつ

かつ

が成り立つ。さらに

と

は次の形のベズーの等式

を満たす（つまり2次持ち上げの反復計算を行うための前提が満たされる）。

証明: 最初の主張は1次持ち上げを
 で
 の代わりにイデアル に対して適用することでわかる。

と置く。次の式

が、

と置くことで成り立つ。2つの多項式を

と

で定めると

が成り立つ。これで2番目の主張も証明できた。

 具体例 

多項式

を考えよう。

この多項式に対して法2でのヘンゼルの補題を適用することはできない。なぜなら

を法 2 で還元すると単に
pg 15-16

となり、この6つの因子

はどの2つを取っても互いに素ではないからだ。しかし、アイゼンシュタインの既約判定法を使って多項式

が

で既約であることは示せる。

一方、 では

となる。
は

における2の平方根である。4は

における立方数ではないので、この2つの因子は

上既約である。したがって

の
（または）における既約多項式への因数分解は

となる。ここで

は

における2の平方根で、先ほどの因数分解を持ち上げることで得られる。

最後に、この多項式は

においては

と分解する。これらの因子はどの2つを取っても互いに素なので、（または）において6つの多項式

の積に分解する。
は（有理数ではない）727進数

である。

微分を用いた根の持ち上げ

を整数（または 進整数）を係数とする多項式とし、 と を
 ≤ 
を満たす正の整数とする。整数 に対して

が成り立ったとする。このとき、任意の

に対してある整数 が存在して

が成り立つ。この は法

で一意であり、次の式

で具体的に計算できる整数である。ここで

は次の式

を満たす整数である。先程の式で を定めれば、
なので条件

は満たされている。なお、
であるときは、持ち上げ は存在しないかもしれないし複数存在するかもしれない（あとで「#ヘンゼル持ち上げ」で例示する）。

 証明 

 の まわりでのテイラー展開

を使う。
なのである整数 が存在して

とかける。これを使うと

と計算できる。 としていたので、

である。 は
 で割り切れないという仮定から、
は法

で逆元を持ち、しかもそれは一意でなければならない。したがって、最後の式の

についての解は法

で一意に存在し、 は法

で一意に存在する。

 関連する諸結果 

 多項式の既約性判定 

仮定は今までと同じとし、既約多項式

が

だったとすると、

である。
の場合だと、 で

であるが、 なので、この多項式は既約ではありえない。一方

では両方の値が等しいので既約である可能性がある。
既約であるかどうか決定するためにはニュートンの多角形を使う必要があるpg 144。

 フロベニウス 

に対してフロベニウス自己準同型

による多項式

を考える。この微分は

となり常にゼロである。

 1の冪根 

1の

乗根は

に存在しないが、方程式

の解は存在する。次の式

は決してゼロにならないので、解が存在すればそれは

に持ち上げることができる。フロベニウスにより

なので、ゼロではない元全体

が解全体である。実は、
に含まれる1の冪根はこれらだけである。

 ヘンゼル持ち上げ 

補題を使って、多項式 の法

での根 を
法

での新しい根 に
 ≡ mod 
となるように持ち上げることができる。
（ と取る。数学的帰納法により大きい はしたがう）。

また、法

での根は法

での根でもあるので、法

での根はすべて法

での根の持ち上げである。

持ち上げた根 は法 
で

と合同なので、
新しい根も

を満たす。

したがって、
最初の根

が

を満たせば持ち上げの操作は繰り返すことができ、
の解

からはじめて、 の高次冪に対して同じ合同式を満たす解の数列
, , ...
を作れる。

このことはまた、
 の法

での根が全て単根であれば、

の法

での根の数は法
, , ...
での根の数と同じであることを示している。

 が法

で単根になっていないとき、このプロセスでは何が起きているのであろうか? これを見るために、次の状況

を考えよう。このとき、
は

を意味する。つまり任意の整数 に対して

が成り立つ。それゆえ次の2つの場合がある。

 なら の法 への の根の持ち上げは存在しない。

 なら の任意の法 への持ち上げは の法 での根である。

例:
 として両方のケースを見てみよう。

 とし、 とする。このとき、 で

である。
なので、1の法4への持ち上げで
 の法4での根になるものは存在しない。

、 とする。すると

かつ

である。また、
であるので、この解を法4へ持ち上げることができ、2つの持ち上げ（1と3）はともに解である。これらの解に対しても微分は法2でやはり0であるので、アプリオリにはこれらを法8に持ち上げられるかどうかは分からない。しかし実際には
 も も法8で0と合同であるので持ち上げることができる。法8では1, 3, 5, 7が解である。これらの中で
 と だけが法16で0なので、1と7だけが法16に持ち上げることができ、それらは1, 7, 9, 15である。これらの中では7と9だけが

なので、同様に法32での解7, 9, 23, 25が得られる。任意の整数 に対して法2での

の根1の法

の根への持ち上げは4つ存在することがわかる。

 進数の場合のヘンゼルの補題 

 進数では、 の冪乗を法とする有理数の合同類というものを、分母が

の倍数でなければ考えることができる。このことを使うと、
法 での根

から法 での根

を求める反復計算をずっと直感的に行うことができる。次の合同式

を解いて整数

を見つける代わりに、有理数

を次の式

で定める。分母に が出てくるように見えるが、
 が

で割れるため実際には出てこない。そして

と置く。これは整数にはならないかもしれないが、
進整数にはなっている。数列

はある
 進整数
に収束し、極限は

の解になっている。そして、
から

を計算する漸化式をよく見てみると、実数の場合における求根アルゴリズムであるニュートン法の漸化式とまったく同じになっている。

 進数の中で計算を行い
 進絶対値を使うことで

となってしまう

の解についても使えるようにしたヘンゼル補題がある。
が0になってしまわないことは必要である。この一般化されたヘンゼルの補題は次のようになる。整数 で

を満たすものがあったとすると、 進整数 で
 かつ

となるものが一意的に存在する。この
 を作るにはニュートン法の漸化式が初期値

で
 進数に収束することを示しその極限を

と置けばよい。条件
 を満たす根として
 が一意であることを示すには追加の議論がいる。

先ほどのヘンゼルの補題の の場合はこの一般化された補題の特殊な場合になっている。条件

と

は

と

を意味するからである。

 例 
 を奇素数、 を0ではない
 を法とする平方剰余とする。このとき、 進整数環 の中に
 の平方根が存在することをヘンゼルの補題を使って示すことができる。これを見るために

と置く。 を法 での
 の平方根とすると

が成り立つ。2番目の式は
 が奇数であることによる。基本形のヘンゼルの補題を使って、
から出発して反復計算を行うことにより整数の列 を

が成り立つように作ることができる。この列はある
 進整数 に収束し

を満たす。

この は、法 で と合同になる

における

の唯一の平方根である。逆に、 を
 の平方数で
 で割り切れないものとすると、
これは0ではない法 での平方剰余である。
が法 でゼロではない平方剰余かどうかは平方剰余の相互法則で簡単に判定できるので、これで（奇素数 に対する） 進数が 進平方根を持つかどうかを決定する実用的な方法が得られたことになる。
の場合にも、一般化されたヘンゼルの補題を用いることでこの方法を拡張することができる（17の2進平方根の例を後で見る）。

以上の議論をもっと具体的に理解するために、7進整数環の中で"2の平方根"、つまり方程式

の解を見つけてみよう。この方程式の法7での解の1つは3（もう1つの解は4）なので、
としよう。ヘンゼルの補題における

の計算式に現れる各種の数値は

 

となる。これらの式から、次の式

は

となり、これは

を意味する。したがって、

と計算できた。簡単に確かめられるように、
が成り立っている（ニュートン法の反復を直接7進数で使うと、
となる。 なので整合している）。

次の反復計算を行うと

となる。この計算を1回繰り返すごとに（つまり の値が1つ増えていく度に）次の7の冪乗の項が追加され7進数での桁が1つが増えていく。7進整数環の中でこの数列は収束し、その極限は

での2の平方根となる。その7進展開の初めの方は

となる。

最初に

を選んだ場合でも

における2の平方根が得られる。
これは法7で3ではなく4に合同になるもので、実は最初に得られた平方根を-1倍したものになっている（これは

であることと辻褄があっている）。

元々のヘンゼルの補題は適用できないが一般化されたものなら適用できる例として

を考える。
とすると

であり、また

であるので、

が成り立つ。これから、ある2進整数 で

を満たすものが一意に存在する。二番目の式は

を意味する。2進整数の中には17の平方根が2つ存在し、それらは符号が異なり、法2では合同であるが法4では合同ではない。これは、一般化された形のヘンゼルの補題から得られるのが法2ではなく法4で1と合同な17の2進平方根で、法4で一意であることと整合的である。最初の近似根として

を取った場合でも一般化されたヘンゼルの補題を適用することができ、法4で3と合同になる唯一の17の2進平方根をやはり見つけることができる。これがもう1つの17の2進平方根である。

の根を法

から法

へ持ち上げるやり方の場合、法2での根1からの持ち上げの過程は次のようになる。

 は に持ち上がる。
 は に、 は に持ち上がる。
 は に、 は に持ち上がる。一方、 と は での根に持ち上がらない。
 は に、 は に持ち上がる。一方、 と は での根に持ち上がらない。

 が3以上であれば

には4つの根がある。しかし2進極限は2つしかない。持ち上げられた根と極限の2進展開を比べてみよう。例えば、法32での4つの根を法16で等しくなるものを組にして書くと次のようになる。

 と 
 と 

一方、17の2進平方根の展開は

となっている。

基本形は使えないが一般化された形のヘンゼルの補題なら使えるもう１つの例として、
である任意の3進整数は

で立方数になることの証明を見よう。
と置き、最初の近似根として

を取る。任意の に対して

となってしまうので、基本形のヘンゼルの補題を使って

の根を見つけることはできない。

一般形のヘンゼルの補題を適用するためには

である必要がある。これは

ということである。つまり、

であれば一般形のヘンゼルの補題から

が3進根を持つことがわかり、
が3進立方数であることがわかる。しかし、

というより弱い条件のもとでこの結果が欲しい。
であれば、
である。この3つの

の値に応じて初期値を使い分けて一般形のヘンゼルの補題を適用する。
なら、 を使う。
なら、 を使う（4は法27での の根）。
なら、 を使う。なお、任意の

は3進立方数になる、という主張は正しくない。例えば、4は法9で立方数にならないので3進立方数ではない。

同様にして、少し準備が必要だが、ヘンゼルの補題を使って任意の奇素数 に対して法

で1と合同な全ての
 進整数 
は

の
 冪乗数であることを示すことができる（ の場合はこれは成り立たない）。

 多変数への一般化 

 1つの多項式 

ヘンゼルの補題は多変数の多項式への一般化もある。
を整数係数の多項式とし、ディオファントス方程式

 

を考える。これがある素数 に対して （ は非負整数）で解

を持ったとする。つまり

が成り立ったとする。さらに、少なくとも1つの変数について の偏微分の における値が でゼロではなかったとする。このとき、 は で と等しい

での解に持ち上がる。同様に の解に持ち上げることもできるので、このディオファントス方程式は 進整数環 Z で解を持つ。

 複数の多項式 

 をイデアル

について完備な可換環とし、 とする。次の式

を満たす のことを の近似根と呼ぶ。 が近似根を持つなら、 に"近い"本当の根 も持つ。つまり、次の式

を満たす が存在する。さらに、 が零因子でないならば、 は一意的である。

このことは多変数の場合に次のように一般化できる。

定理: を可換環でイデアル について完備なものとする。 を 係数の 個の 変数多項式とする。 を から自身への写像と考え、 をそのヤコビ行列とする。 = を の近似解、つまり

が成り立つものとする。このとき、ある で を満たすもの、つまり

が成り立つものが存在する。さらに、この解は

が成り立つという意味で に"近い"解である。

この定理の特別な場合として、
がすべての に対して成り立ち、しかも

が

の単数なら、解

ですべての に対して

が成り立つものが存在することがわかる。

 の場合、

は
 の元で

である。したがって、この多変数のヘンゼルの補題の仮定は1変数の場合には通常のヘンゼルの補題の仮定と同じになっている。

関連概念

環が完備であることはヘンゼルの補題が成り立つための必要条件ではない。1950年に、東屋五郎は可換な局所環であって極大イデアル

についてヘンゼルの補題が成り立つものをヘンゼル環と名付けた。

1950年代に永田雅宜は、任意の可換な局所環
 とその極大イデアル に対して
 を含む環 
であって

についてヘンゼルの補題が成り立つような最小の環

が常に存在することを証明した。この

のことを

のヘンゼル化と呼ぶ。
がネーターなら

もネーターである。また、
はの極限として構成されるので代数的である。したがって、
はヘンゼルの補題が成り立つにも関わらず、通常は完備化

よりもずっと小さく、同じ圏に属している。