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

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

背景

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

主張

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

pが奇素数であるとき、
- $x-y\equiv 0{\pmod {p}}$ であれば $\nu _{p}(x^{n}\mp y^{n})=\nu _{p}(x\mp y)+\nu _{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]。

応用

例1

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$ を整数として、

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}}}

であるから $n =2 2 \times 3 2 \times 5 4 \times 7 5$ 。以上より $n$ の正の約数の個数は210個。

例2

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

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

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

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

上記以外の場合を考える。まず $n\neq 1$ がいえる。群の元の位数についてのラグランジュの定理より、 $n$ は $\phi (2^{k})=2^{k-1}$ の約数だから $n=2^{l}$ ( $l$ は整数, $1\leq l\leq k-1$ )という形に限られ、とくに偶数である。LTEの補題より

\nu _{2}(a^{n}-1)=\nu _{2}(a^{n}-1^{n})=\nu _{2}(a-1)+\nu _{2}(a+1)+l-1

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

l\geq k+1-\nu _{2}(a-1)-\nu _{2}(a+1)

(A)

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

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

脚注

[脚注の使い方]

出典

^ ^a ^b ^c Parvardi, A. H. (2011年). “Lifting The Exponent Lemma (LTE)”. 2020年7月11日閲覧。
^ Gauss, C. (1801). Disquisitiones arithmeticae.. pp. 86-87
^ Geretschläger, R. (2020). Engaging Young Students in Mathematics through Competitions – World Perspectives and Practices.. World Scientific.
^ Heuberger, C.; Mazzoli, M. (2017). “Elliptic curves with isomorphic groups of points over finite field extensions”. Journal of Number Theory 181: 89–98.
^ S. Riasat, Generalising `LTE' and application to Fibonacci-type sequences.
^ “2020 AIME I Problems.”. Art of Problem Solving (2020年). 2020年7月20日閲覧。

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

LTEの補題

背景

主張