LTEの補題

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

## 背景
LTEの補題の起源は明確でない。現在のような名称と整理された形が注目されるようになったのは2000年代と言われる。ただし、補題の核となる発想はカール・フリードリヒ・ガウスの *[[Disquisitiones Arithmeticae]]* において言及されている。競技数学の分野で使われることがある一方で、楕円曲線の研究にも応用される。
## 主張
任意の整数及び正整数、の素因数でない素数について、次の主張が成立する。
*が奇素数であるとき、
**x-y \equiv 0 \pmod{p} であれば\nu_p(x^n-y^n)=\nu_p(x-y)+\nu_p(n)。
**x+y \equiv 0 \pmod{p} かつが奇数ならば、\nu_p(x^n+y^n) = \nu_p(x+y)+\nu_p(n).
**x+y \equiv 0 \pmod{p} かつが偶数ならば、\nu_p(x^n+y^n) = 0.
* が偶数の素数つまり2であるとき、
**x-y \equiv 0 \pmod{2} かつが偶数ならば、\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 = \nu_2\left(\frac{x^2-y^2}{2}\right)+\nu_2(n).
** x-y \equiv 0 \pmod{2} かつが奇数ならば、\nu_2(x^n-y^n) = \nu_2(x-y).
* 任意のについて、
** x-y \equiv 0 \pmod{p} かつ、がで割り切れないならば\nu_p(x^n-y^n) = \nu_p(x-y).
** x+y \equiv 0 \pmod{p} かつ、がで割り切れないかつ、が奇数ならば\nu_p(x^n+y^n) = \nu_p(x+y).

の場合の系には以下の様なものがある。
* x-y \equiv 0 \pmod{4} で、がともに奇数ならば、\nu_2(x+y)=1で、\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(n).
*x+y \equiv 0 \pmod{2} かつが偶数のとき、\nu_2(x^n+y^n) = 1.
*x+y \equiv 0 \pmod{2} かつが奇数のとき、\nu_2(x^n+y^n) = \nu_2(x+y).
## 証明
### 基本的な場合
がで割り切れない場合について、 \nu_p(x^n-y^n) = \nu_p(x-y) を証明する。x \equiv y \pmod{p} より、

また、x^n-y^n = (x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\dots+y^{n-1})であるから題意は示された。が奇数の場合の式 \nu_p(x^n+y^n) = \nu_p(x+y)については、をその反数に置き換えることで得られる。
### pが奇数の場合
（は整数）を代入しとして、二項展開することで、()式左辺はで割り切れるがでは割り切れないことが分かる。したがって\nu_p(x^p-y^p) = \nu_p(x-y)+1。同様に\nu_p(x^p+y^p) = \nu_p(x+y)+1。

（はで割り切れない）とすると、基本の場合より \nu_p(x^n-y^n) = \nu_p((x^{p^a})^b-(y^{p^a})^b) = \nu_p(x^{p^a}-y^{p^a})。

式\nu_p(x^p-y^p) = \nu_p(x-y)+1を回用いることで、
:
\begin{align}
\nu_p(x^{p^a}-y^{p^a}) &= \nu_p(((\dots(x^p)^p\dots))^p-((\dots(y^p)^p\dots))^p)\ \\
&= \nu_p(x-y)+a
\end{align}

が示される。\nu_p(x^n+y^n)の場合も同様にして証明できる。

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

x \equiv y \pmod{4} であるとき、（は奇数）とすると、
:
\begin{align}
\nu_2(x^n-y^n) &= \nu_2((x^{2^a})^b-(y^{2^a})^b) \\
&= \nu_2(x^{2^a}-y^{2^a}) \\
&= \nu_2((x^{2^{a-1}}+y^{2^{a-1}})(x^{2^{a-2}}+y^{2^{a-2}})\cdots(x^2+y^2)(x+y)(x-y)) \\
&= \nu_2(x-y)+a
\end{align}

ここでx \equiv y \equiv \pm 1 \pmod{4} より、x^{2^k}+y^{2^k} \equiv 2 \pmod{4}（は非負整数）であることを用いた。

また、これを利用して、より強い主張であるx \equiv y \pmod{2}のとき\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1が証明される。
## 一般化
LTEの補題はが整数となるような複素数においても同様に成立する。

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

である。149と2は3で割り切れないが、147は3で割り切ることができるから、
:\nu_3(149^n-2^n) = \nu_3(147)+\nu_3(n) = \nu_3(n)+1
が成り立つ。したがって
: 149^n-2^n\equiv 0\pmod{3^3} \iff n \equiv 0\pmod{3^2}
である。同様にして、
:149^n-2^n\equiv 0 \pmod{7^7} \iff n \equiv 0 \pmod{7^5}
が分かる。 

147は5で割り切れないため、因数5については次のように処理をする。を5で割った余りは4,1,4,1...という周期となること、を5で割った余りは2,4,3,1...という周期となることにより、を5で割った余りは2,2,1,0...という周期となる。したがってを整数として、
:149^n-2^n \equiv 0 \pmod{5}\iff n = 4k.

LTEの補題を再度使用して、
:\nu_5(149^{4k}-2^{4k}) = \nu_5((149^4)^k-(2^4)^k) = \nu_5(149^4-2^4)+\nu_5(k).
である。
:149^4-2^4 \equiv (-1)^4-2^4 \equiv -15 \pmod{25}
より、
:\nu_5(149^4-2^4) = 1.
ゆえに、
:149^n-2^n\equiv 0\pmod{5^5} \iff k\equiv 0 \pmod{5^4} \iff n \equiv 0\pmod{4\cdot 5^4}
であるから。以上よりの正の約数の個数は210個。

### 例2
奇数と整数k \ge 3が与えられている。剰余類環の乗法群(\mathbb{Z}/2^k\mathbb{Z})^\timesにおけるの位数はいくらか。

これはa^n\equiv 1 \pmod{2^k} すなわち \nu_2(a^n-1) \ge kとなる最小の正の整数を求めることにほかならない。

a\equiv 1 \pmod{2^k}の場合、n=1である。

a\equiv -1,~ 2^{k-1}\pm 1 \pmod{2^k}の場合、n=2であることは簡単な計算で確かめられる。

上記以外の場合を考える。まずn \ne 1がいえる。群の元の位数についてのラグランジュの定理より、は\phi(2^k)=2^{k-1}の約数だからn=2^l (は整数, 1\le l\le k-1)という形に限られ、とくに偶数である。LTEの補題より
:\nu_2(a^n-1) = \nu_2(a^n-1^n) = \nu_2(a-1) + \nu_2(a+1) + l - 1
であり、この最左辺の値が以上であるという条件は、移項によって

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

なお、最後の場合のがとる値は最大でもである(などがそれを実現する)。以上のことから、よく知られているこの群の直積分解(\mathbb{Z}/2^k\mathbb{Z})^\times \cong (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})が従う。

## 脚注

### 出典

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