初学者でも分かるLTEの補題

初学者でも分かるLTEの補題

ごきげんよう。
いきなりですが、次の数を見てみましょう。
$$ 2^6-1=63=3^2\cdot 7 $$
この数には、素数 $3$ が 2個 含まれています。
では、指数を一気に大きくして、
$$ 2^{600}-1 $$
には $3$ が何個含まれているでしょうか。
もちろん、$2^{600}-1$ を実際に計算してから素因数分解する必要はありません。巨大な整数そのものを知らなくても、そこに特定の素数が何個含まれているかだけを調べる方法があります。
この記事の最終目標は、その方法の一つである LTE（Lifting The Exponent）の補題 を、公式の暗記ではなく証明から理解することです。

「$p$ で割れるか」から「$p$ で何回割れるか」へ。

その見方を身につけると、巨大なべきの整除性が驚くほど小さな計算で分かるようになります。
この記事では、LTE をいきなり提示しません。次の順に道具を一つずつ作り、最後にそれらをつなげます。

1. 約数・倍数と素因数分解
2. 「素数が何個含まれるか」を表す p 進付値
3. 合同式とべきの差の因数分解
4. 二項係数に現れる素数の性質
5. LTE の核心となる二つの補題
6. 奇素数型・和型・2の場合の証明
7. 使い方、変形、演習、入試整数への発展
   途中で数学的帰納法を使う箇所があります。未習の方は、別記事「数学的帰納法を初めから」を先に読むと安心です。もっとも、この記事でも使う場面では何を繰り返しているのかを具体的に書きます。

第1部　「割り切れる」を整理する

1.1　約数・倍数

例えば、
$$ 72=8\cdot 9 $$
なので、$8$ は $72$ の約数であり、$72$ は $8$ の倍数です。

1.2　「割れる」の先を見る

$72$ を $2$ のべきで割ってみると、
$$ 72=2^3\cdot 3^2 $$
ですから、$2,2^2,2^3$ では割れますが、$2^4$ では割れません。
そこで、

$72$ の中には $2$ が3個含まれている
と考えることができます。
同様に、$72$ の中には $3$ が2個含まれています。LTE で数えるのは、まさにこの「素数の個数」です。

第2部　素数と素因数分解

2.1　素数・合成数

例えば、$2,3,5,7,11$ は素数です。一方、
$$ 12=3\cdot 4 $$
のように $1$ と $12$ 以外の正の約数をもつので、$12$ は合成数です。
なお、$1$ は素数でも合成数でもありません。

2.2　素因数分解

正の整数を素数の積で表すことを、素因数分解といいます。
例えば、
$$ 360=2^3\cdot 3^2\cdot 5 $$
です。この式を見るだけで、$360$ には、$2$ が3個、$3$ が2個、$5$ が1個含まれ、それ以外の素数は含まれていないことが分かります。

2.3　素因数分解が一意であるということ

これは算術の基本定理とも呼ばれます。この記事では証明までは扱いませんが、この一意性があるからこそ、「ある素数が何個含まれているか」が曖昧なく決まります。

2.4　素数が積を割るとき

素因数分解で考えると自然です。積 $ab$ の中に素数 $p$ が現れるなら、その $p$ は $a$ の素因数分解か $b$ の素因数分解のどちらかから来るしかありません。
これは $p$ が素数だから成り立つ性質です。合成数では成り立ちません。
例えば、
$$ 6\text{ は }2\cdot 3\text{ の約数} $$
ですが、$6$ は $2$ の約数でも $3$ の約数でもありません。
この「素数が積を割るなら、どちらか一方を割る」という性質は、LTE の条件確認でも証明でも何度も使います。
合同式の言葉では、素数を法とする零積性と呼ばれることもあります。

第3部　「素数が何個含まれるか」を記号にする

3.1　$p$-進付値

ここから、毎回「$p$ が何個含まれる」と文章で書く代わりに、一つの記号を使います。

初めのうちは、
$$ v_p(N)=\text{「$N$ の中に含まれる素数 $p$ の個数」} $$
と読めば十分です。
負の整数については、符号を無視して
$$ v_p(-N)=v_p(N) $$
と考えます。

3.2　具体例

$$ 360=2^3\cdot 3^2\cdot 5 $$
より、
$$ v_2(360)=3,\qquad v_3(360)=2,\qquad v_5(360)=1,\qquad v_7(360)=0 $$
です。
また、どの素数 $p$ に対しても
$$ v_p(1)=0 $$
です。$1$ は $p$ では割れないからです。

第4部　$v_p$ の基本性質

4.1　積では個数が足される

証明

$$ a=p^rA,\qquad b=p^sB $$
とします。ただし、$A,B$ は $p$ で割れない整数です。このとき、
$$ ab=p^{r+s}AB $$
です。
$A$ も $B$ も $p$ で割れないので、素数の積に対する性質から $AB$ も $p$ で割れません。したがって、$ab$ に含まれる $p$ の個数は $r+s$ 個です。
よって、
$$ v_p(ab)=r+s=v_p(a)+v_p(b) $$
となります。

4.2　べきでは個数が何倍にもなる

$a^n$ は $a$ を $n$ 個掛けたものなので、積の性質を繰り返すと、
$$ \boxed{v_p(a^n)=n\,v_p(a)} $$
を得ます。
例えば、$12=2^2\cdot 3$ なので、
$$ v_2(12^{100})=100\,v_2(12)=200 $$
です。

4.3　整数になる商

$a,b$ を $0$ でない整数とします。$b$ が $a$ の約数で、$a/b$ が整数であるとします。
$$ a=b\cdot\frac ab $$
に積の性質を使うと、
$$ v_p(a)=v_p(b)+v_p\left(\frac ab\right) $$
です。したがって、
$$ \boxed{ v_p\left(\frac ab\right)=v_p(a)-v_p(b) } $$
となります。

4.4　$v_p(N)=k$ の大切な言い換え

$$ v_p(N)=k $$
であることは、
$$ N=p^kR $$
と書けて、しかも $R$ が $p$ で割れないことと同じです。
特に、
$$ \boxed{ N=p^{v_p(N)}R \qquad \text{（$R$ は $p$ で割れない）} } $$
と書けます。
「含まれる $p$ を全部外へ出し、残りは $p$ で割れないようにする」という分解です。LTE の証明では、指数 $n$ に対してこの分解を行います。

4.5　付値の異なる二数を足すとき

積ほど単純ではありませんが、和にも非常に重要な性質があります。

証明

例えば、
$$ v_p(A)=r< s=v_p(B) $$
とします。$p$ で割れない整数 $C,D$ を用いて、
$$ A=p^rC,\qquad B=p^sD $$
と書くと、
$$ A+B=p^r\left(C+p^{s-r}D\right) $$
です。
$s-r\geqq1$ なので、$p^{s-r}D$ は $p$ の倍数です。一方、$C$ は $p$ で割れません。したがって、括弧内は $p$ で割れません。
よって、
$$ v_p(A+B)=r $$
です。

第5部　合同式の最低限

合同式を初めて学ぶ方のために、LTE に必要な部分だけを確認します。

5.1　合同式の意味

これは「$a$ と $b$ を $m$ で割った余りが同じ」という意味です。
例えば、$17-2=15$ は $5$ の倍数なので、
$$ 17\equiv2\pmod5 $$
です。

5.2　加法・減法・乗法

$$ a\equiv b\pmod m,\qquad c\equiv d\pmod m $$
なら、
$$ \begin{aligned} a+c&\equiv b+d\pmod m,\\ a-c&\equiv b-d\pmod m,\\ ac&\equiv bd\pmod m \end{aligned} $$
が成り立ちます。
特に、同じ合同式を何度も掛けることで、
$$ a\equiv b\pmod p \quad\Longrightarrow\quad a^n\equiv b^n\pmod p $$
です。

5.3　「$p$ で割れない」を表す

$p$ が $a$ の約数でないことは、
$$ a\not\equiv0\pmod p $$
と表せます。
この記事では、
$$ a\equiv b\pmod p $$
から各項を $b$ に置き換えたり、「ある整数が $p$ の倍数ではない」ことを確かめたりするために合同式を使います。

5.4　合同式の割り算には注意

通常の等式のように、合同式の両辺をいつでも同じ数で割れるわけではありません。
例えば、
$$ 2\equiv4\pmod2 $$
は正しいですが、両辺を $2$ で割って得られそうな
$$ 1\equiv2\pmod2 $$
は誤りです。
ただし、法が素数 $p$ で、割ろうとする数 $c$ が $p$ で割れないなら、
$$ ac\equiv bc\pmod p \quad\Longrightarrow\quad a\equiv b\pmod p $$
と約して構いません。
実際、左の合同式は $c(a-b)$ が $p$ の倍数であることを意味します。$p$ は素数で、$c$ は $p$ で割れないので、$a-b$ が $p$ の倍数でなければなりません。

第6部　$a^n-b^n$ の因数分解

6.1　べきの差の公式

右辺を展開すると、途中の項が打ち消し合い、$a^n-b^n$ だけが残ります。
この公式から、$a-b$ は必ず $a^n-b^n$ の約数です。したがって、素数 $p$ が $a-b$ の約数なら、$p$ は $a^n-b^n$ の約数でもあります。
しかし、LTE が知りたいのは、単に

$p$ で割れるか
ではありません。
何回 $p$ で割れるのか
を知りたいのです。
そこで、
$$ a^n-b^n=(a-b)S $$
としたとき、もう一方の因子 $S$ から新しい $p$ が何個現れるかを調べます。

第7部　最初の核心補題――指数に $p$ がなければ増えない

ここでは $p$ が奇素数である必要はなく、$p=2$ でも成り立ちます。

証明

べきの差を因数分解して、
$$ a^n-b^n=(a-b)S $$
とおきます。ただし、
$$ S=a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1} $$
です。
$p$ が $a-b$ の約数なので、
$$ a\equiv b\pmod p $$
です。したがって、$S$ の各項はすべて $b^{n-1}$ と合同になります。
$S$ には全部で $n$ 個の項があるので、
$$ S\equiv nb^{n-1}\pmod p $$
です。
また、$p$ が $ab$ の約数でないので、$p$ は $b$ の約数ではありません。さらに、仮定より $p$ は $n$ の約数でもありません。
よって、素数の積に対する性質から、$nb^{n-1}$ は $p$ の倍数ではありません。したがって、
$$ S\not\equiv0\pmod p $$
です。つまり、$S$ からは新しい $p$ が一つも増えません。
積の付値の性質から、
$$ \begin{aligned} v_p(a^n-b^n) &=v_p(a-b)+v_p(S)\\ &=v_p(a-b) \end{aligned} $$
となります。

第8部　二項定理と、素数の二項係数

8.1　二項係数と二項定理

$n$ を正整数、$0\leqq k\leqq n$ とするとき、二項係数を
$$ {}_nC_k=\frac{n!}{k!(n-k)!} $$
と書きます。ここで、
$$ n!=n(n-1)\cdots2\cdot1 $$
であり、$0!=1$ と定めます。
${}_nC_k$ は「$n$ 個のものから $k$ 個を選ぶ方法の数」なので、上の分数は必ず整数になります。

8.2　上の数が素数のとき

証明

$$ {}_pC_k =\frac{p(p-1)(p-2)\cdots(p-k+1)}{k!} $$
なので、
$$ k!\,{}_pC_k =p(p-1)(p-2)\cdots(p-k+1) $$
です。右辺は明らかに $p$ の倍数です。
一方、$1\leqq k\leqq p-1$ なので、$1,2,\ldots,k$ のどれも $p$ の倍数ではありません。したがって、$k!$ も $p$ の倍数ではありません。
$k!\,{}_pC_k$ が $p$ の倍数で、$k!$ は $p$ の倍数ではないので、素数の積に対する性質から、${}_pC_k$ が $p$ の倍数でなければなりません。

第9部　第二の核心補題――指数を $p$ 倍すると1個増える

ここが LTE の証明で最も重要な部分です。一項ずつ、含まれる $p$ の個数を数えます。

9.1　二項展開する

$$ x=y+(x-y) $$
と書くと、
$$ \begin{aligned} x^p-y^p &=\{y+(x-y)\}^p-y^p\\ &=py^{p-1}(x-y) +{}_pC_2y^{p-2}(x-y)^2\\ &\quad+{}_pC_3y^{p-3}(x-y)^3 +\cdots+(x-y)^p \end{aligned} $$
です。
ここで、
$$ t=v_p(x-y) $$
とおきます。$p$ が $x-y$ の約数なので、$t\geqq1$ です。

9.2　第一項に含まれる $p$ の個数

第一項は
$$ py^{p-1}(x-y) $$
です。
$p$ は $xy$ の約数でないので、$y$ は $p$ で割れません。したがって、
$$ \begin{aligned} v_p\left(py^{p-1}(x-y)\right) &=v_p(p)+(p-1)v_p(y)+v_p(x-y)\\ &=1+0+t\\ &=t+1 \end{aligned} $$
です。

9.3　途中の項には、それより多く含まれる

$2\leqq k\leqq p-1$ に対する項
$$ {}_pC_k y^{p-k}(x-y)^k $$
を考えます。
第8部より ${}_pC_k$ は $p$ の倍数なので、そこから少なくとも1個の $p$ が現れます。また、$(x-y)^k$ からは $kt$ 個の $p$ が現れます。
よって、この項の付値は
$$ 1+kt\geqq1+2t\geqq t+2 $$
以上です。第一項の $t+1$ より必ず大きくなります。

9.4　最後の項も、それより多く含まれる

最後の項 $(x-y)^p$ の付値は
$$ pt $$
です。
$p$ は奇素数なので $p\geqq3$、また $t\geqq1$ です。したがって、
$$ pt\geqq3t\geqq t+2 $$
です。これも第一項の $t+1$ より大きくなります。

9.5　なぜ第一項だけを見てよいのか

以上より、第一項だけが $p^{t+1}$ で割れ、ほかのすべての項は $p^{t+2}$ で割れます。
$p$ で割れない整数 $U$ と、ある整数 $M$ を用いて、全体を
$$ x^p-y^p=p^{t+1}(U+pM) $$
と書けます。
$U$ は $p$ で割れず、$pM$ は $p$ の倍数なので、$U+pM$ は $p$ で割れません。
したがって、
$$ v_p(x^p-y^p)=t+1=v_p(x-y)+1 $$
です。

第10部　LTE の補題を証明する

準備がすべて整いました。ここで初めて完成形を示します。

10.1　指数から $p$ をすべて取り出す

$$ k=v_p(n) $$
とおきます。第4部の分解により、$p$ で割れない正整数 $r$ を用いて、
$$ n=p^kr $$
と書けます。
ここで、第7部の補題を指数 $r$ に使うと、
$$ v_p(a^r-b^r)=v_p(a-b) $$
です。指数 $r$ には $p$ が含まれていないので、この段階では付値が増えません。

10.2　指数にある $p$ を一つずつ戻す

$$ A_j=a^{rp^j},\qquad B_j=b^{rp^j} $$
とおきます。すると、
$$ A_{j+1}=A_j^p,\qquad B_{j+1}=B_j^p $$
です。
第9部の補題により、指数を $p$ 倍するたびに、
$$ v_p(A_{j+1}-B_{j+1}) =v_p(A_j-B_j)+1 $$
となります。
これを $j=0,1,\ldots,k-1$ について繰り返すと、全部で $k$ 増えるので、
$$ v_p(a^{rp^k}-b^{rp^k}) =v_p(a^r-b^r)+k $$
です。
この「$k$ 回繰り返せば $k$ 増える」という部分は、厳密には $k$ に関する数学的帰納法で表せます。

10.3　結論

$rp^k=n$、$k=v_p(n)$ なので、
$$ \begin{aligned} v_p(a^n-b^n) &=v_p(a^r-b^r)+k\\ &=v_p(a-b)+v_p(n) \end{aligned} $$
となります。
これが LTE、すなわち Lifting The Exponent の補題です。

指数 $n$ に含まれる $p$ の個数が、$a^n-b^n$ の付値へそのまま持ち上がる。
そのため、
$$ v_p(a^n-b^n)=v_p(a-b)+v_p(n) $$
という形になるのです。

第11部　まず LTE を使ってみる

証明を理解したところで、実際に使ってみましょう。

11.1　最初に条件を確認する

11.2　指数にある $p$ が持ち上がる例

11.3　導入の問題に戻る

初めに見た
$$ v_3(2^{600}-1) $$
を求めます。そのままでは $3$ が $2-1$ の約数ではないため、LTE を使えません。
しかし、
$$ 2^{600}-1=4^{300}-1 $$
と見れば、$3$ は $4-1$ の約数です。したがって、
$$ \begin{aligned} v_3(2^{600}-1) &=v_3(4^{300}-1)\\ &=v_3(4-1)+v_3(300)\\ &=1+1\\ &=2 \end{aligned} $$
です。
巨大な数を計算せず、導入と同じく「$3$ が2個」と分かりました。

第12部　和の場合

和型を新しい公式として暗記する必要はありません。差型へ直します。
$n$ が奇数なら、
$$ (-b)^n=-b^n $$
なので、
$$ a^n+b^n=a^n-(-b)^n $$
です。第10部の証明は、底が負でも、式の値が $0$ でない限り全く同じです。そこで差型 LTE の証明における $b$ を $-b$ に置き換えれば、そのまま使えます。

第13部　なぜ $p=2$ だけ特殊なのか

13.1　奇素数では $a-b$ と $a+b$ の両方を割れない

$p$ を奇素数とし、$p$ が $a-b$ の約数であるとします。
もし $p$ が $a+b$ の約数でもあるなら、$p$ は
$$ (a+b)+(a-b)=2a $$
と
$$ (a+b)-(a-b)=2b $$
の両方の約数です。
$p$ は奇素数なので、$2$ の約数ではありません。素数の積に対する性質から、$p$ は $a$ と $b$ の両方の約数になってしまいます。
これは「$p$ が $ab$ の約数ではない」という LTE の仮定に反します。
したがって奇素数では、LTE の条件のもとで、$a-b$ と $a+b$ の両方から同じ $p$ が現れることはありません。

13.2　$2$ では両方から現れる

$a,b$ が奇数なら、
$$ a-b\quad\text{も}\quad a+b\quad\text{も偶数} $$
です。
つまり $p=2$ では、$a-b$ だけでなく $a+b$ に含まれる2も同時に数えなければなりません。
これは、平方差
$$ a^{2m}-b^{2m} =(a^m-b^m)(a^m+b^m) $$
を見ると、さらに明確です。右辺の二つの因子がどちらも偶数になります。

13.3　二項展開から見ても特殊である

第9部では、奇素数 $p$ なら、二項展開の第一項だけが最小の付値をもちました。
ところが $p=2$ では、
$$ x^2-y^2=2y(x-y)+(x-y)^2 $$
の二項が同じ付値をもつ場合があります。すると両者を足したとき、さらに2の因子が増える可能性があります。
したがって、$p=2$ は単なる暗記上の例外ではありません。構造上の違いは二つあります。一つは、$a-b$ と $a+b$ の両方が偶数になることです。もう一つは、二項展開で最小の付値をもつ項が一つに決まらないことです。

第14部　$p=2$ 型 LTE

14.1　指数を「2のべき×奇数」に分ける

$$ k=v_2(n) $$
とおくと、$n$ は偶数なので $k\geqq1$ です。ある正の奇数 $r$ を用いて、
$$ n=2^kr $$
と書けます。
ここで、
$$ X=a^r,\qquad Y=b^r $$
とおきます。$a,b,r$ は奇数なので、$X,Y$ も奇数です。

14.2　平方差を繰り返す

平方差を繰り返し使うと、
$$ \begin{aligned} X^{2^k}-Y^{2^k} &=(X-Y)(X+Y)(X^2+Y^2)\\ &\quad\cdot(X^4+Y^4)\cdots (X^{2^{k-1}}+Y^{2^{k-1}}) \end{aligned} $$
となります。
$k=1$ のときは、$(X-Y)(X+Y)$ だけです。

14.3　後ろの因子には2がちょうど1個ずつある

奇数 $X$ について、
$$ X^2\equiv1\pmod8 $$
です。実際、$X=2q+1$ と書けば、
$$ X^2-1=4q(q+1) $$
であり、連続する整数 $q,q+1$ の一方は偶数なので、右辺は $8$ の倍数です。
したがって、$j\geqq1$ なら、
$$ X^{2^j}\equiv1\pmod8,\qquad Y^{2^j}\equiv1\pmod8 $$
です。よって、
$$ X^{2^j}+Y^{2^j}\equiv2\pmod8 $$
となります。
この因子は $2$ では割れますが $4$ では割れないので、
$$ v_2(X^{2^j}+Y^{2^j})=1 $$
です。このような因子は $k-1$ 個あります。

14.4　初めの二因子を元へ戻す

$r$ は奇数なので、
$$ \frac{a^r-b^r}{a-b} =a^{r-1}+a^{r-2}b+\cdots+b^{r-1} $$
は奇数を $r$ 個足したものです。$r$ は奇数なので、この商は奇数です。
したがって、
$$ v_2(X-Y)=v_2(a^r-b^r)=v_2(a-b) $$
です。
同様に、奇数乗の和を因数分解すると、
$$ \frac{a^r+b^r}{a+b} =a^{r-1}-a^{r-2}b+\cdots-ab^{r-2}+b^{r-1} $$
となります。$2$ を法とすれば符号の違いはなく、これも奇数を $r$ 個足したものなので奇数です。
よって、
$$ v_2(X+Y)=v_2(a^r+b^r)=v_2(a+b) $$
です。

14.5　すべてを足す

積では付値が足されるので、
$$ \begin{aligned} v_2(a^n-b^n) &=v_2(X^{2^k}-Y^{2^k})\\ &=v_2(X-Y)+v_2(X+Y)+(k-1)\\ &=v_2(a-b)+v_2(a+b)+v_2(n)-1 \end{aligned} $$
となります。

第15部　LTE の条件を整理する

15.1　使う前の確認順

次の順に見ると、条件の見落としが減ります。
① 求めたいのは、どの素数 $p$ に関する付値か。
② $p$ は奇素数か、$2$ か。
③ 式は差か、和か。
④ $p$ は底の差または和の約数か。
⑤ $p$ は二つの底の積の約数ではないか。
⑥ 和型なら指数は奇数か。$p=2$ 型なら指数は偶数か。

15.2　奇素数・差型

15.3　奇素数・和型

15.4　$p=2$ 型

なお、$a,b$ が相異なる奇数で、$n$ が正の奇数なら、
$$ v_2(a^n-b^n)=v_2(a-b) $$
です。

第16部　よくある間違い

16.1　底の差を確認せずに使う

例えば、
$$ v_3(2^n-1) $$
に差型 LTE をそのまま使うことはできません。$3$ は $2-1=1$ の約数ではないからです。
ただし、指数が偶数なら底を作り直せます。これは第17部で扱います。

16.2　$p$ が底の積を割らない条件を忘れる

例えば $p=3,a=6,b=3,n=2$ では、$3$ は $a-b=3$ の約数ですが、底 $6,3$ も $3$ の倍数です。
実際、
$$ v_3(6^2-3^2)=v_3(27)=3 $$
であるのに、条件を無視して公式へ代入すると、
$$ v_3(6-3)+v_3(2)=1 $$
となってしまいます。

16.3　和型で指数の奇数条件を忘れる

例えば $n=2$ のとき、誤って和型を使うと、
$$ v_3(2^2+1)=v_3(2+1)+v_3(2)=1 $$
となりそうですが、実際には $2^2+1=5$ なので左辺は $0$ です。

16.4　$p=2$ に奇素数版を使う

例えば、
$$ 3^2-1=8 $$
なので、
$$ v_2(3^2-1)=3 $$
です。
奇素数版を誤って使うと、
$$ v_2(3-1)+v_2(2)=1+1=2 $$
となり、正しい値を得られません。足りない1個は $3+1$ から現れています。

16.5　$a-b$ と $a+b$ を取り違える

差型では $a-b$、和型では $a+b$ を見ます。公式の見た目だけでなく、どちらが $p$ の倍数なのかを必ず先に確認しましょう。

16.6　$v_p(0)$ を無意識に使う

$a=b$ なら $a^n-b^n=0$ です。また、負の底まで許して $n$ が偶数なら、$a=-b$ でも値は $0$ になります。この記事では $v_p(0)$ を定義していないので、式の値が $0$ でないことを確認します。

16.7　「各項が割れる」だけで付値を決める

和の付値では、最小の付値をもつ項が複数あると、足し合わせたときに付値が増えることがあります。
第9部で第一項だけを見られたのは、第一項だけがただ一つ最小の付値をもつことまで示したからです。「全部 $p$ で割れる」だけでは証明として足りません。

第17部　直接 LTE を使えないとき

LTE は、条件を満たす形に対して使う定理です。初めの形で使えなくても、式の見方を変えれば使えることがあります。

17.1　底を作り直す

例えば、
$$ v_3(2^{2n}-1) $$
では、$3$ は $2-1$ の約数ではありません。しかし、
$$ 2^{2n}-1=4^n-1 $$
と見れば、$3$ は $4-1$ の約数です。よって、
$$ \boxed{ v_3(2^{2n}-1)=v_3(4-1)+v_3(n)=1+v_3(n) } $$
となります。
一般に、
$$ a^{mn}-b^{mn}=(a^m)^n-(b^m)^n $$
と見ることで、$p$ が新しい底の差 $a^m-b^m$ を割るようにできることがあります。

17.2　具体例

17.3　因数分解してから別々に数える

$$ a^{2n}-b^{2n}=(a^n-b^n)(a^n+b^n) $$
と分け、それぞれの因子の付値を調べて足す方法もあります。
特に $p=2$ 型の証明は、この平方差を繰り返したものです。

LTE が使えないから終わり、ではありません。

LTE が使える底や因数を作れないかと考えることが大切です。

第18部　段階別演習

各問題では、計算を始める前に「どの型を、なぜ使えるか」を確認してください。

Level 1　そのまま差型

Level 2　和型

Level 3　$p=2$ 型

Level 4　底を変形してから使う

Level 5　最大の指数を求める

Level 6　整数条件と組み合わせる

第19部　この記事で身につけた整数問題の武器

ここまでに使った考え方は、LTE 専用ではありません。今後の整数問題で再利用できる形にまとめます。

19.1　「割れるか」ではなく「何回割れるか」

整数 $N$ に対して、
$$ v_p(N) $$
を見る発想です。
「$p^k$ が $N$ の約数となる最大の $k$」を求める問題は、そのまま $v_p(N)$ を求める問題です。
複雑な整除条件を、

各素数が何個含まれているか
へ分けて考えられます。

19.2　積では付値が足される

$$ \boxed{ v_p(AB)=v_p(A)+v_p(B) } $$
したがって、式を因数分解できれば、各因子に含まれる $p$ の個数を別々に調べればよいことになります。

19.3　付値が異なる二数の和

$$ v_p(A)\neq v_p(B) $$
なら、
$$ \boxed{ v_p(A+B)=\min\{v_p(A),v_p(B)\} } $$
です。
さらに一般に、複数の項の中でただ一つの項だけ付値が最小なら、その項が和全体の付値を決めます。
これは二項展開や多項式の整除性で非常に強力です。

19.4　素数 $p$ と二項係数

$p$ が素数で、
$$ 1\leqq k\leqq p-1 $$
なら、
$$ \boxed{ {}_pC_k\text{ は }p\text{ の倍数} } $$
です。
LTE の証明だけでなく、「二項展開した途中の項をすべて消したい」という合同式の問題で頻出します。

19.5　二項定理から得られる合同式

$$ (a+b)^p =a^p+{}_pC_1a^{p-1}b+\cdots+b^p $$
の中間項はすべて $p$ の倍数です。したがって、
$$ \boxed{ (a+b)^p\equiv a^p+b^p\pmod p } $$
となります。
これを繰り返せば、
$$ \boxed{ (a_1+a_2+\cdots+a_m)^p \equiv a_1^p+a_2^p+\cdots+a_m^p \pmod p } $$
も得られます。

19.6　フェルマーの小定理へのつながり

前項で $b=1$ とすると、
$$ (a+1)^p\equiv a^p+1\pmod p $$
です。
$a=0$ では $a^p\equiv a\pmod p$ が成り立ちます。また、ある $a$ で $a^p\equiv a\pmod p$ が成り立つと仮定すれば、
$$ (a+1)^p\equiv a^p+1\equiv a+1\pmod p $$
です。
数学的帰納法により、すべての $0$ 以上の整数 $a$ で成立します。任意の整数も $p$ で割った余りに置き換えられるので、
$$ \boxed{ a^p\equiv a\pmod p } $$
です。
さらに、$p$ が $a$ の約数でないとき、
$$ a^p-a=a(a^{p-1}-1) $$
は $p$ の倍数です。$p$ は $a$ の約数ではないので、素数の積に対する性質から、$a^{p-1}-1$ が $p$ の倍数です。
よって、
$$ \boxed{ a^{p-1}\equiv1\pmod p } $$
となります。これがフェルマーの小定理です。
ここでは合同式を不注意に $a$ で割らず、素数が積を割るときの性質を使っている点にも注目してください。

19.7　べきの差の整除

べきの差の因数分解から、$a-b$ は $a^n-b^n$ の約数です。
さらに、正整数 $m$ が正整数 $n$ の約数なら、ある正整数 $q$ を用いて $n=mq$ と書けます。すると、
$$ a^n-b^n=(a^m)^q-(b^m)^q $$
です。したがって、
$$ \boxed{ a^m-b^m \text{ は } a^n-b^n \text{ の約数} } $$
となります。

19.8　べきの和の整除

$q$ が奇数なら、
$$ x^q+y^q =(x+y)(x^{q-1}-x^{q-2}y+\cdots-xy^{q-2}+y^{q-1}) $$
です。
したがって、$m$ が $n$ の約数で、さらに $n/m$ が奇数なら、
$$ \boxed{ a^m+b^m \text{ は } a^n+b^n \text{ の約数} } $$
となります。

19.9　$a-b$ と $a+b$ の最大公約数

$a>b$ を満たす正整数 $a,b$ の最大公約数が $1$、すなわち $a,b$ が互いに素であるとします。
$a-b$ と $a+b$ の共通約数は、その和 $2a$ と差 $2b$ の共通約数でもあります。
もし奇素数が $a-b$ と $a+b$ の両方の約数なら、その奇素数は $a,b$ の両方の約数となり、互いに素であることに反します。
したがって共通約数に現れ得る素数は $2$ だけです。さらに $4$ が両方の約数なら $4$ は $2a$ の約数となり、$a$ が偶数になってしまいます。同様に $b$ も偶数となり、やはり矛盾します。
よって、
$$ \boxed{ \gcd(a-b,a+b)\text{ は }1\text{ または }2 } $$
です。
実際には、$a,b$ の一方だけが偶数なら最大公約数は $1$、両方が奇数なら $2$ です。
これは $p=2$ が特殊になる理由と直結しています。

19.10　等比和との最大公約数

$a>b$ を満たす互いに素な正整数 $a,b$ に対し、
$$ S=\frac{a^n-b^n}{a-b} =a^{n-1}+a^{n-2}b+\cdots+b^{n-1} $$
とします。
$a\equiv b\pmod{a-b}$ なので、
$$ S\equiv nb^{n-1}\pmod{a-b} $$
です。
また、$a,b$ が互いに素なら、$a-b$ と $b$ も互いに素です。そのため、$a-b$ と $nb^{n-1}$ の共通因子は、$a-b$ と $n$ の共通因子と同じです。
よって、
$$ \boxed{ \gcd\left( a-b, \frac{a^n-b^n}{a-b} \right) =\gcd(a-b,n) } $$
が得られます。
第7部の補題は、この等比和が $p$ の倍数になるかどうかを、一つの素数 $p$ に注目して調べたものだと見ることもできます。

19.11　「使える形を作る」という発想

整数問題では、知っている定理をそのまま使えるかどうかだけでなく、

定理を使える形へ式を変形できるか
が重要です。
例えば、
$$ 2^{2n}-1=4^n-1 $$
と見ることで、底の差を $1$ から $3$ へ変え、$p=3$ の LTE を使えるようにしました。
合同式で「どの法を見るか」を選ぶのと同じように、LTE では「どのまとまりを底と見るか」を選びます。

第20部　さらに先へ

今回の「素数 $p$ が何個含まれるか」という考え方は、LTE だけに終わりません。

20.1　階乗に含まれる $p$ の個数

$\lfloor x\rfloor$ は、$x$ 以下の最大の整数を表します。また、$p^j>n$ となった後の項はすべて $0$ なので、右辺は実質的には有限個の和です。
例えば、
$$ \begin{aligned} v_2(10!) &=\left\lfloor\frac{10}{2}\right\rfloor +\left\lfloor\frac{10}{4}\right\rfloor +\left\lfloor\frac{10}{8}\right\rfloor\\ &=5+2+1\\ &=8 \end{aligned} $$
です。

20.2　二項係数に含まれる $p$ の個数

$$ {}_nC_k=\frac{n!}{k!(n-k)!} $$
なので、積と商の付値の性質から、
$$ \boxed{ v_p({}_nC_k) =v_p(n!)-v_p(k!)-v_p((n-k)!) } $$
です。
ここにルジャンドルの公式を代入すれば、二項係数が $p$ で何回割れるかを調べられます。
今後は、

• ルジャンドルの公式
• 二項係数の整除性
• フェルマーの小定理
• 指数型の整数問題
• p 進付値を使う方程式・不等式
  へ進むことができます。

最終まとめ　LTE の本質

LTE の差型では、まず $p$ が $a-b$ の約数であるため、$a^n-b^n$ の中にも、もともと $a-b$ に含まれていた $p$ が存在します。
そして、指数 $n$ の中に $p$ が一つ含まれるたびに、指数を $p$ 倍する一段階によって、$a^n-b^n$ の中の $p$ も一つずつ増えます。
そのため、

となります。
公式だけを覚えるのではなく、

指数側にある $p$ の個数が、べきの差の側へ持ち上がる
という現象として理解しておけば、条件も公式の形も思い出せます。
この記事で本当に持ち帰ってほしいのは LTE 一つだけではありません。

• 素因数を「あるかないか」ではなく「何個あるか」で見る
• 因数分解して、各因子の付値を足す
• 和では、ただ一つの最小付値を探す
• 素数なら二項係数の途中がすべてその素数の倍数になる
• 定理をそのまま使えなければ、使える底や因数を作る
• 例外の公式も、その例外が生じる構造から理解する
  これらは、これから整数問題を解いていくうえで何度も再登場する考え方です。
  みなさまの日常に良き数学の彩りのあらんことを。
  それでは、ごきげんよう。