LTEの補題

初等整数論において、LTEの補題（LTEのほだい、）とは、特別な形の整数のp-進付値をより次数の低い整数のものを用いて表す一連の補題である。ヘンゼルの補題と関連している。

背景 LTEの補題の起源は明確でない。現在のような名称と整理された形が注目されるようになったのは2000年代と言われる。ただし、補題の核となる発想はカール・フリードリヒ・ガウスの Disquisitiones Arithmeticae において言及されている。競技数学の分野で使われることがある一方で、楕円曲線の研究にも応用される。 主張 任意の整数及び正整数、の素因数でない素数について、次の主張が成立する。 が奇素数であるとき、 であれば。 かつが奇数ならば、 かつが偶数ならば、 が偶数の素数つまり2であるとき、 かつが偶数ならば、 かつが奇数ならば、 任意のについて、 かつ、がで割り切れないならば かつ、がで割り切れないかつ、が奇数ならば

の場合の系には以下の様なものがある。 で、がともに奇数ならば、で、 かつが偶数のとき、 かつが奇数のとき、 証明 基本的な場合 がで割り切れない場合について、 を証明する。 より、

また、であるから題意は示された。が奇数の場合の式 については、をその反数に置き換えることで得られる。 pが奇数の場合 （は整数）を代入しとして、二項展開することで、()式左辺はで割り切れるがでは割り切れないことが分かる。したがって。同様に。

（はで割り切れない）とすると、基本の場合より 。

式を回用いることで、

が示される。の場合も同様にして証明できる。

pが2の場合 のとき、二項展開の際に奇素数とは異なりがの倍数とならない。

であるとき、（は奇数）とすると、

ここで より、（は非負整数）であることを用いた。

また、これを利用して、より強い主張であるのときが証明される。 一般化 LTEの補題はが整数となるような複素数においても同様に成立するS. Riasat, Generalising `LTE' and application to Fibonacci-type sequences.。

応用 例1 LTEの補題の利用例として2020年のの問題を挙げる。 がで割り切れるような最小の正整数について、の正の約数の個数を求めよ。

である。149と2は3で割り切れないが、147は3で割り切ることができるから、

が成り立つ。したがって

である。同様にして、

が分かる。

147は5で割り切れないため、因数5については次のように処理をする。を5で割った余りは4,1,4,1...という周期となること、を5で割った余りは2,4,3,1...という周期となることにより、を5で割った余りは2,2,1,0...という周期となる。したがってを整数として、

LTEの補題を再度使用して、

である。

より、

ゆえに、

であるから。以上よりの正の約数の個数は210個。

例2 奇数と整数が与えられている。剰余類環の乗法群におけるの位数はいくらか。

これは すなわち となる最小の正の整数を求めることにほかならない。

の場合、である。

の場合、であることは簡単な計算で確かめられる。

上記以外の場合を考える。まずがいえる。群の元の位数についてのラグランジュの定理より、はの約数だから (は整数, )という形に限られ、とくに偶数である。LTEの補題より

であり、この最左辺の値が以上であるという条件は、移項によって

と言い換えられる。これとをともに満たすような最小のを求める。いまの一方は2で1回しか割り切れず、もう一方が2で割り切れる回数は2回以上回以下であるから、である。よって、()の不等号を等号にしたものを採用してよく、この場合の答えはである。

なお、最後の場合のがとる値は最大でもである(などがそれを実現する)。以上のことから、よく知られているこの群の直積分解が従う。

脚注

出典

関連項目 Vieta jumping - 同じく数学の競技にて使用される。