LTEの補題とは？わかりやすく解説

初等整数論において、LTEの補題 （LTEのほだい、英: LTE lemma, lifting-the-exponent lemma）とは、特別な整数のp-進付値 $v_{p}$ がより次数の低い整数のものと等しいという補題である。ヘンゼルの補題と関連している。

背景

LTEの補題の起源は明確でない。補題の結果及び名称と形は近10,20年以内に注目されたと言われる^[1]。ただし、補題の核となる発想はカール・フリードリヒ・ガウスの Disquisitiones Arithmeticae において言及されている^[2]。競技数学の分野で使われることがある一方で、楕円曲線の研究にも応用される^[3]^[4]。

主張

任意の整数 $x, y$ 及び正整数 $n$ 、 $x, y$ の素因数でない素数 $p$ について、次の主張が成立する。

pが奇素数であるとき、
- $x-y\equiv 0{\pmod {p}}$ であれば $v_{p}(x^{n}\mp y^{n})=v_{p}(x\mp y)+v_{p}(n)$ （複号同順）。
- $x+y\equiv 0{\pmod {p}}$ かつ $n$ が奇数ならば、 $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n).$
- $x+y\equiv 0{\pmod {p}}$ かつ $n$ が偶数ならば、 $\nu _{p}(x^{n}+y^{n})=0.$
pが偶数の素数つまり2であるとき、
- $x-y\equiv 0{\pmod {2}}$ かつ $n$ が偶数ならば、 $\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}}$ かつ $n$ が奇数ならば、 $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y).$
任意のpについて、
- $x-y\equiv 0{\pmod {p}}$ かつ、 $n$ が $p$ で割り切れないならば $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y).$
- $x+y\equiv 0{\pmod {p}}$ かつ、 $n$ が $p$ で割り切れないかつ、 $n$ が奇数ならば $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y).$

$p = 2$ の場合の系には以下の様なものがある。

$x-y\equiv 0{\pmod {4}}$ で、 $x, y$ がともに奇数ならば、 $\nu _{2}(x+y)=1$ で、 $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n).$
$x+y\equiv 0{\pmod {2}}$ かつ $n$ が偶数のとき、 $\nu _{2}(x^{n}+y^{n})=1.$
$x+y\equiv 0{\pmod {2}}$ かつ $n$ が奇数のとき、 $\nu _{2}(x^{n}+y^{n})=\nu _{2}(x+y).$

証明

基本的な場合

$n$ が $p$ で割り切れない場合について、 $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)$ を証明する。 $x\equiv y{\pmod {p}}$ より、

x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1}\equiv nx^{n-1}\not \equiv 0{\pmod {p}}

(1)

また、 $x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1})$ であるから題意は示された。 $n$ が奇数の場合の式 $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)$ については、 $y$ をその反数 $- y$ に置き換えることで得られる。

pが奇数の場合

$y = x + kp$ （ $k$ は整数）を代入し $n = p$ として、二項展開することで、(1)式左辺は $p$ で割り切れるが $p 2$ では割り切れないことが分かる。したがって $\nu _{p}(x^{p}-y^{p})=\nu _{p}(x-y)+1$ ^[1]。同様に $\nu _{p}(x^{p}+y^{p})=\nu _{p}(x+y)+1$ 。

$n = p a b$ （ $b$ は $p$ で割り切れない）とすると、基本の場合より $\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$ を $a$ 回用いることで、

{\begin{aligned}\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{aligned}}

が示される。 $\nu _{p}(x^{n}+y^{n})$ の場合も同様にして証明できる。

pが2の場合

$p = 2$ のとき、二項展開の際に奇素数とは異なり $p (p - 1) / 2$ が $p$ の倍数とならない。

$x\equiv y{\pmod {4}}$ であるとき、 $n = 2 a b$ （ $b$ は奇数）とすると、

{\begin{aligned}\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{aligned}}

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

また、より強い形として $x\equiv y{\pmod {2}}$ ならば、 $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1$ が証明される^[1]。

一般化

LTEの補題は $x n - y n / x - y$ が整数となるような複素数 $x, y$ においても同様に成立する^[5]。

応用

LTEの補題の利用例として2020年のAIME（英語版）の問題を挙げる。

149 n - 2 n

が

33 \times 5 5 \times 7 7

で割り切れるような最小の正整数

n

について、

n

の正の約数の個数を求めよ^[6]。

$149 - 2 = 147 = 3 \times 7 2$ である。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については次のように処理をする。 $149 n$ を5で割った余りは4,1,4,1...という周期となること、 $2 n$ を5で割った余りは2,4,3,1...という周期となることにより、 $149 n - 2 n$ を5で割った余りは2,2,1,0...という周期となる。したがって $k$ を整数として、