初学者でもわかるLTEの補題(改訂)
ごきげんよう。まずは、次の数を見てみましょう。
素因数分解すると、$3$ が 2個 現れます。では、$2^{600}-1$ には $3$ が何個現れるでしょうか。
巨大な数を実際に計算しなくても、特定の素数の個数だけなら調べられます。そのための道具が、LTE（Lifting The Exponent）の補題です。最初に、この記事のゴールを見ておきましょう。
この記事で証明する式
$v_p(N)$ は「$N$ の素因数分解に現れる $p$ の個数」です。底の差にある分に、指数にある分を足すと、べきの差にある分が分かります。
代表的な条件は、$p$ が奇素数、$a,b$ が相異なる正整数、$n$ が正整数で、$a-b$ は $p$ の倍数、$ab$ は $p$ の倍数でないことです。
現段階では、式を完全に理解できなくても構いません。必要な準備をしたあと、「なぜこの式になるのか」「なぜ条件が要るのか」を順に確かめます。
1 前提知識｜証明に使う道具だけ
この記事の証明で使用する知識
素数・約数の意味は既知とします。同じ操作を有限回繰り返す部分は、数学的帰納法でも書けます。
1.1 p進付値：素数が何個あるか
定義｜p進付値
$p$ を素数、$N$ を $0$ でない整数とします。$p^t$ では割れるが $p^{t+1}$ では割れないとき、$v_p(N)=t$ と定めます。
と書け、$u$ が $p$ で割れない整数であることと同じです。$t$ は $0$ 以上の整数で、負の $N$ は符号を無視します。
例えば、$360=2^3\cdot3^2\cdot5$ なので、
です。この記事では $v_p(0)$ を扱いません。
積では、素因数の個数が足されます。
実際、$A=p^s u,\ B=p^t w$ とし、$u,w$ が $p$ で割れないように取ると、$AB=p^{s+t}uw$ です。$p$ は素数なので $uw$ も $p$ で割れず、積の式が従います。べきの式は、これを $m$ 回使ったものです。ここで $A,B$ は $0$ でない整数、$m$ は正整数です。
1.2 和は「最小の付値が一つだけ」なら決まる
積と違い、和の付値は無条件には決まりません。ただし、一つの項だけが最小の付値をもつときは、その値で決まります。
例えば、$v_p(A)=s\lt v_p(B)=t$ なら、$p$ で割れない整数 $u,w$ を用いて、
と書けます。括弧内は $p$ で割れないため、$v_p(A+B)=s$ です。二項の場合は、$\min\{s,t\}$ を「$s,t$ の小さい方」として、
とまとめられます。一方、$v_3(1)=v_3(2)=0$ でも $v_3(1+2)=1$ です。同じ付値の項どうしでは、足すと新たな $p$ が現れることがあります。
二項展開で使う見方
一項だけが $p^s$ でちょうど割れ、残りはすべて $p^{s+1}$ で割れるなら、全体は
と書けます。ここで $U,M$ は整数で、$U$ は $p$ で割れません。括弧内は $p$ で割れないので、全体の付値はちょうど $s$。この形まで確かめれば、相殺を心配する必要がありません。
1.3 合同式と、べきの差の因数分解
$a\equiv b\pmod p$ は、$a-b$ が $p$ の倍数であることを表します。合同式は足す・引く・掛けることができ、$a$ を $b$ に置き換えて、式が $p$ で割れるかを判定できます。
例えば $a\equiv b\pmod p$ なら、$a^2+ab+b^2\equiv3b^2\pmod p$ です。また、$p$ が素数なら、$p$ で割れない整数どうしの積は $p$ で割れません。
正整数 $n$ に対し、べきの差は
と因数分解できます。$S$ は $a^{n-1},a^{n-2}b,\ldots,b^{n-1}$ の $n$ 項の和です。$n=1$ なら $S=1$ です。右辺を展開すると途中の項が消えて、左辺が残ります。
LTEでは、もともとの因子 $a-b$ に加え、もう一方の因子 $S$ から新しい $p$ が何個現れるかを調べます。
1.4 二項定理で必要になる性質
二項定理を、次の形で使います。
ここで大切なのは、$p$ が素数なら、$1\leqq j\leqq p-1$ に対して ${}_pC_j$ は $p$ の倍数になることです。
実際、
の右辺は $p$ の倍数ですが、$j\lt p$ なので $j!$ は $p$ の倍数ではありません。よって、整数 ${}_pC_j$ が $p$ の倍数でなければなりません。
2 証明の核①｜指数にpがなければ増えない
核①｜増えない段階
$p$ を素数、$a,b$ を相異なる正整数、$n$ を正整数とします。$a-b$ は $p$ の倍数、$ab$ と $n$ は $p$ の倍数でないとき、
が成り立ちます。この段階では $p=2$ でも構いません。
因数分解して $a^n-b^n=(a-b)S$ と書きます。$a\equiv b\pmod p$ なので、$S$ の各項はどれも $b^{n-1}$ と合同です。項は $n$ 個あるため、
となります。$n$ も $b$ も $p$ で割れないので、この余りは $0$ ではありません。したがって $v_p(S)=0$ であり、積の付値を足せば結論が出ます。
つまり、指数側に $p$ がなければ、追加の因子 $S$ にも $p$ は現れないのです。
答案としてまとめると｜核①
補題の仮定の下で、$S=\sum_{j=0}^{n-1}a^{n-1-j}b^j$ とおく。$a\equiv b\pmod p$ より、
である。よって $a^n-b^n=(a-b)S$ から、$v_p(a^n-b^n)=v_p(a-b)$ を得る。
なお、この証明は底が負でも、$a^n-b^n\ne0$ であれば同じです。後で和を差に直すときに使います。
3 証明の核②｜指数をp倍すると一つ増える
核②｜持ち上がる一段階
$p$ を奇素数、$x,y$ を相異なる正整数とします。$x-y$ は $p$ の倍数、$xy$ は $p$ の倍数でないとき、
が成り立ちます。指数に $p$ が一つ追加されると、付値も一つ増える。ここがLTEの中心です。
なぜ二項展開するのか。 $x-y$ に含まれる $p$ の個数が分かっているので、$h=x-y$ とおき、$x=y+h$ と書きます。こうすれば、各項に $h$ が何個掛かっているかで付値を比べられます。
$t=v_p(h)$ とすると、仮定より $t\geqq1$ です。二項定理から、
を得ます。三つの部分を比べましょう。
| 展開の部分 | 付値の評価 |
|---|---|
| 第一項 $py^{p-1}h$ | $y$ は $p$ で割れないので、ちょうど $t+1$ |
| 中間項 ${}_pC_jy^{p-j}h^j$（$2\leqq j\leqq p-1$） | ${}_pC_j$ から少なくとも1個。付値は $1+jt\geqq t+2$ 以上 |
| 最後の項 $h^p$ | 付値は $pt$。$p\geqq3,\ t\geqq1$ より $pt\geqq t+2$ |
第一項は $p^{t+1}$ で割れ、$p^{t+2}$ では割れません。他の項はすべて $p^{t+2}$ で割れます。したがって、整数 $U,M$ を用いて、
と書けます。括弧内が $p$ で割れないので、全体の付値は ちょうど $t+1$ です。
証明の決め手
第一項だけが、ただ一つ最小の付値をもつ。
全項が $p^{t+1}$ で割れることだけでは、付値が「$t+1$ 以上」としか分かりません。$p^{t+2}$ では割れないところまで確かめて、初めて値が決まります。
答案としてまとめると｜核②
補題の仮定の下で、$h=x-y,\ t=v_p(h)\geqq1$ とおく。二項定理より、
第一項の付値は $t+1$。$2\leqq j\leqq p-1$ では ${}_pC_j$ は $p$ の倍数であり、$1+jt\geqq t+2$、また $pt\geqq t+2$ である。よって他の項はすべて $p^{t+2}$ の倍数なので、和の付値は $t+1$。したがって $v_p(x^p-y^p)=v_p(x-y)+1$。
ここでも、底の正負は証明に影響しません。なお $p=2,\ t=1$ では、第一項と最後の項の付値がともに $2$ になります。奇素数という条件を使った場所はここです。 2の場合は第6節で扱います。
4 LTEの補題｜二つの核を組み合わせる
主定理｜LTEの補題（奇素数・差型）
$p$ を奇素数、$a,b$ を相異なる正整数、$n$ を正整数とします。
を満たすとき、
が成り立ちます。
$k=v_p(n)$ とおき、指数から $p$ をすべて取り出します。
まず、指数を $r$ にする段階では、核①により付値は増えません。次に指数を $p$ 倍する操作を $k$ 回行うと、核②により一回につき $1$ ずつ増えます。
| 指数の変化 | 付値の変化 |
|---|---|
| $1\longrightarrow r$ | 核①：変わらない |
| $r$ から $rp^k=n$ へ（$p$ 倍を $k$ 回） | 核②：$k$ 回で $k$ 増える |
この繰り返しで条件が保たれることも確認しましょう。$a,b$ は $p$ で割れないので、そのべきも $p$ で割れません。また、$a\equiv b\pmod p$ から、同じ指数のべきどうしは引き続き合同です。正の異なる底なので、べきの差も $0$ になりません。
よって、
が得られます。$k=0$ なら繰り返しは不要で、核①だけで終わります。
式の二つの項が表すもの
LTEは、「増えない段階」と「一つずつ増える段階」をつないだ結果です。指数に含まれる $p$ の個数が、そのままべきの差の側へ持ち上がります。
答案としてまとめると｜LTE全体
主定理の仮定の下で、$k=v_p(n)$ とし、$n=p^kr$（$r$ は $p$ で割れない正整数）と書く。核①より $v_p(a^r-b^r)=v_p(a-b)$。
$0\leqq j\lt k$ に対し、$a^{rp^j},b^{rp^j}$ は核②の条件を満たすので、
が成り立つ。これを $k$ 回用いて、
を得る。$k=0$ の場合も核①より同じ結論となる。
この答案は、核①・核②が既に示されている場合のものです。主定理だけを証明する問題なら、先に二つの核の答案も書きます。
5 和の場合｜負の底を使って差に直す
$n$ が奇数なら、
です。差型の証明は負の底でも使えるので、$b$ を $-b$ に置き換えます。底の「差」は $a-(-b)=a+b$ になり、積が $p$ で割れるかどうかは符号に影響されません。
系｜LTEの和型
$p$ を奇素数、$a,b$ を正整数、$n$ を正の奇数とします。$a+b$ は $p$ の倍数、$ab$ は $p$ の倍数でないとき、
が成り立ちます。正整数の和なので、付値に入る数が $0$ になる心配もありません。
奇数条件は、和を差へ読み替えるために必要です。 偶数 $n$ では $(-b)^n=b^n$ になり、元の和には戻りません。実際、同じ底の条件の下では、
なので、偶数 $n$ での付値は $0$ です。和型をそのまま延長することはできません。
6 p=2の場合｜最初の平方差だけ、増え方が違う
ここでは $a,b$ を 相異なる正の奇数とします。
奇素数 $p$ では、LTEの条件の下で $a-b$ と $a+b$ の両方が $p$ の倍数になることはありません。両方が倍数なら、その和 $2a$ と差 $2b$ も倍数になり、$p$ が $a,b$ を割らない条件に反するからです。
ところが $a,b$ が奇数なら、$a-b$ も $a+b$ も偶数です。したがって、最初に指数を2倍すると、
の $a+b$ に含まれる2も、まとめて増えます。増加量は必ずしも1ではありません。例えば、$3^2-1=2\cdot4$ なので、$v_2(3-1)=1$ から $v_2(3^2-1)=3$ へ、2増えます。
二項展開で見ても、奇数 $x,y$ について $h=x-y$ としたとき $x^2-y^2=2yh+h^2$ です。$v_2(h)=1$ なら二項とも付値が2で、最小の項が一つに定まりません。核②で使った議論が、そのまま通らないわけです。
定理｜2の場合
$a,b$ を相異なる正の奇数、$n$ を正整数とします。
$n$ が奇数なら
$n$ が偶数なら
6.1 奇数の指数では増えない
差については、$p=2$ として核①を使えます。また、奇数 $r$ では $a^r+b^r=a^r-(-b)^r$ なので、負の底に核①を使うと、
です。どちらも、因数分解後の商が奇数になることを表しています。
6.2 偶数の指数では、平方差を繰り返す
$n=2^kr$（$k=v_2(n)\geqq1,\ r$ は正の奇数）と書き、$X=a^r,\ Y=b^r$ とおきます。平方差を繰り返すと、
です。ここで $\prod_{j=0}^{k-1}$ は、$j=0,1,\ldots,k-1$ の因子をすべて掛ける記号です。$k=1$ なら $(X-Y)(X+Y)$ だけになります。
最初の二因子 $X-Y,\ X+Y$ の付値は、6.1よりそれぞれ $v_2(a-b),\ v_2(a+b)$ です。
残りを見ます。奇数の平方は $4$ で割ると1余るため、$j\geqq1$ では、
です。したがって、残りの $k-1$ 個の因子には、2がちょうど1個ずつ含まれます。積の付値を足して、
を得ます。
2の場合の増え方
奇数部分では増えない。最初の2倍では $a+b$ の分が増える。その後の2倍では1ずつ増える。
補正項 $v_2(a+b)-1$ は、この「最初の一回の違い」から生まれます。
答案としてまとめると｜2の場合
相異なる正の奇数 $a,b$ について、$n$ が奇数の場合は核①による。偶数の場合は $n=2^kr$（$k=v_2(n)\geqq1,\ r$ は奇数）とし、$X=a^r,\ Y=b^r$ とおく。核①を差と和に用いると、$v_2(X-Y)=v_2(a-b),\ v_2(X+Y)=v_2(a+b)$。平方差の反復により、
$1\leqq j\leqq k-1$ では $X^{2^j}+Y^{2^j}\equiv2\pmod4$ なので、各因子の付値は1。よって $v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+k-1$ となる。
例えば、$a=3,\ b=1,\ n=100$ なら、
です。なお、和については、奇数 $n$ なら $v_2(a^n+b^n)=v_2(a+b)$、偶数 $n$ なら $a^n+b^n\equiv2\pmod4$ より付値は1です。
7 注意｜付値を決める前に確認すること
公式を使うときの注意
① 底の差・和が $p$ の倍数か。
$v_3(2^n-1)$ に差型を直接使えません。$2-1=1$ は3の倍数ではないからです。底を作り直す方法は、次の実戦で扱います。
② 底が $p$ で割れていないか。
$p=3,\ a=6,\ b=3,\ n=2$ では、$v_3(6^2-3^2)=3$ ですが、$v_3(6-3)+v_3(2)=1$。底の条件は省けません。
③ $p=2$ か。和なら指数は奇数か。
$v_2(3^2-1)=3$ は奇素数型では出ません。また、偶数指数の $2^2+1=5$ に和型を使うと誤ります。
④ 付値に入れる数が0になっていないか。
差型の $a=b$ などは、この記事の定義では扱いません。
証明するときの注意
「全部 $p^s$ の倍数」から分かるのは、付値が $s$ 以上ということだけ。
付値を $s$ と決めるには、$p^{s+1}$ で割れないことも必要です。
$v_p(A+B)$ を無条件に最小値で処理しない。
最小付値の項が複数あれば、和で付値が上がることがあります。核②では「第一項だけが最小」を示して、この問題を除きました。
8 実戦｜LTEを使える形を見つける
例1 そのまま差型を使う
求めるもの
$3$ は奇素数で、$10-1=9$ は3の倍数、$10\cdot1$ は3の倍数ではありません。したがって、
です。$3^6$ では割れ、$3^7$ では割れないところまで分かります。
例2 和を差に読み替える
求めるもの
$49$ は奇数です。$13+1=14$ は7の倍数で、$13\cdot1$ は7の倍数ではないため、和型が使えます。
底を $13,-1$ と見て差型を使った、と考えても同じです。
例3 等比数列の和を、べきの差に直す
求めるもの
まず、和をまとめます。
$10^{81}-1=9S$ と例1の結果から、$6=2+v_3(S)$。よって 答えは4です。
一般にも、整数になる商では、$A=B\cdot(A/B)$ から $v_p(A/B)=v_p(A)-v_p(B)$ が使えます。分母が分子の約数であることを確認してから、付値を引きます。
例4 底を作り直す｜導入の問いへ
求めるもの
$2-1$ は3の倍数ではありません。そこで、2の何乗なら、1との差が3の倍数になるかを見ます。$2^2\equiv1\pmod3$ なので、
とまとめます。新しい底 $4,1$ は差型の条件を満たすため、
です。巨大な数を計算せず、冒頭の $2^6-1$ と同じく 3が2個と分かりました。
同じ考えで、正整数 $n$ に対して、
が成り立ちます。指数が奇数なら $2^n-1\equiv1\pmod3$ で、付値は0です。最初に合同式で指数の奇偶を調べると、LTEを使う場面も見えてきます。
もう一問｜同じ発想で $v_5(2^{500}-1)$ は？
法5で $2,2^2,2^3,2^4$ を見ると、余りは順に $2,4,3,1$。そこで $2^{500}-1=16^{125}-1$ と直す。$16-1=15$ は5の倍数で、$16\cdot1$ は5の倍数ではないから、
となる。
例5 整数条件を、指数の条件へ変える
問題
次の数が整数となる正整数 $n$ をすべて求めてください。
分母は3のべきだけなので、分子に3が $n$ 個以上あることが必要十分です。差型の条件を満たすため、LTEより、
です。よって条件は $n\leqq2+v_3(n)$ になります。$n=1,2,3$ はすべて満たします。
$n\geqq4$ でも満たすと仮定すると、$v_3(n)\geqq n-2$ なので、$n$ は $3^{n-2}$ の倍数です。一方、二項定理より、
となり、正整数 $n$ が自分より大きい正整数の倍数になるので矛盾します。したがって、
です。LTEによって、巨大な分子の条件が、指数 $n$ に含まれる3の個数との比較に変わりました。
使う形を探すときの視点
合同式で、まず $p$ の倍数になる底の差・和を見つける。
等比数列の和なら、べきの差へまとめる。
$a^{mn}-b^{mn}$ なら、$(a^m)^n-(b^m)^n$ と底をまとめ直す。
どのまとまりを「底」と見るかを選ぶことが、LTEを使うための一歩です。
9 周辺知識｜LTEと一緒に使う三つの道具
補足A｜フェルマーの小定理で、使える底を作る
$p$ が素数で $a$ が $p$ の倍数でなければ、$a^{p-1}\equiv1\pmod p$。これがフェルマーの小定理です。
二項定理からの短い証明。中間の二項係数が $p$ の倍数なので、$(a+1)^p\equiv a^p+1\pmod p$。$a=0$ からの帰納法で、0以上の整数について $a^p\equiv a\pmod p$ が従います。任意の整数も余りに置き換えれば同じです。$a(a^{p-1}-1)$ は $p$ の倍数で、$a$ はそうでないため、結論を得ます。
LTEとの接続。$p$ を奇素数、$a\gt 1$ を $p$ で割れない整数、$n$ を正整数とすれば、新しい底 $a^{p-1},1$ は差型の条件を満たします。
ただし、小定理から分かるのは $v_p(a^{p-1}-1)\geqq1$ までです。初めの付値が必ず1になるわけではありません。
補足B｜底の差と和の最大公約数
$\gcd(A,B)$ は正整数 $A,B$ の最大公約数を表します。$a\gt b$ を満たす互いに素な正整数 $a,b$ では、
実際、共通約数は和 $2a$ と差 $2b$ も割ります。$\gcd(a,b)=1$ より $\gcd(2a,2b)=2$ なので、共通約数は1か2。あとは偶奇で決まります。
平方差を因数分解したあと、二因子に共通する素因数は2しかあり得ないと分かります。LTEでは各因子の付値を数え、互いに素の条件は因子間の共通部分を整理するために使います。
補足C｜等比数列型の因子との最大公約数
$a\gt b$ を満たす互いに素な正整数 $a,b$ と、正整数 $n$ に対して、
とおきます。このとき、
です。$a\equiv b\pmod{a-b}$ より $S\equiv nb^{n-1}\pmod{a-b}$ であり、$\gcd(a-b,b)=1$ なので、
となります。核①と同じ合同式が、こちらでは最大公約数を決めています。因数分解後に共通因子を調べるときに使える形です。
みなさまの日常に良き数学の彩りのあらんことを。
それでは、ごきげんよう。
この記事を高評価した人
この記事に送られたバッジ
投稿者
