LTEの補題

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

背景

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

主張

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

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

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

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

証明

基本的な場合

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

${\displaystyle 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)

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

pが奇数の場合

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

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

式${\displaystyle \nu _{p}(x^{p}-y^{p})=\nu _{p}(x-y)+1}$をa回用いることで、

${\displaystyle {\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}}}$

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

pが2の場合

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

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

${\displaystyle {\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}}}$

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

また、これを利用して、より強い主張である${\displaystyle x\equiv y{\pmod {2}}}$のとき${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1}$が証明される^[1]。

一般化

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

応用

例1

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

149ⁿ - 2ⁿが3³ × 5⁵ × 7⁷で割り切れるような最小の正整数nについて、nの正の約数の個数を求めよ^[6]。

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

${\displaystyle \nu _{3}(149^{n}-2^{n})=\nu _{3}(147)+\nu _{3}(n)=\nu _{3}(n)+1}$

が成り立つ。したがって

${\displaystyle 149^{n}-2^{n}\equiv 0{\pmod {3^{3}}}\iff n\equiv 0{\pmod {3^{2}}}}$

である。同様にして、

${\displaystyle 149^{n}-2^{n}\equiv 0{\pmod {7^{7}}}\iff n\equiv 0{\pmod {7^{5}}}}$

が分かる。

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

${\displaystyle 149^{n}-2^{n}\equiv 0{\pmod {5}}\iff n=4k.}$

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

${\displaystyle \nu _{5}(149^{4k}-2^{4k})=\nu _{5}((149^{4})^{k}-(2^{4})^{k})=\nu _{5}(149^{4}-2^{4})+\nu _{5}(k).}$

である。

${\displaystyle 149^{4}-2^{4}\equiv (-1)^{4}-2^{4}\equiv -15{\pmod {25}}}$

より、

${\displaystyle \nu _{5}(149^{4}-2^{4})=1.}$

ゆえに、

${\displaystyle 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² × 3² × 5⁴ × 7⁵。以上よりnの正の約数の個数は210個。

例2

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

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

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

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

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

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

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

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

(A)

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

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