LTEの補題とその応用

18592

今回は自己紹介での予告通りLTEの補題について書いてみようと思います.この補題は $x^{n} - y^{n}$ が素数 $p$ で何回割り切れるかに関するもので,数オリの難問でたまに使われたりするだけでなく純粋に一般化が奥深い補題です.

$p$ 進付値

まずは $p$ で何回割り切れるかを意味する $p$ 進付値を定義します.

整数における

p

進付値

$p$ 素数とし, $n$ を( $0$ でない)整数とする. $n$ を素因数分解したときの $p$ の指数( $n = 0$ のときは便宜的に $\infty$ とする)を $v_{p} (n)$ と書き, $p$ 進付値という.

${ord}_{p} (n)$ と書くこともあり(ここでは $v_{p} (n)$ を使う),位数と呼ばれることもあるような気もします.またここから先の定理などで $n = 0$ のとき不合理であるときは適宜除いて考えてください.
添え字の $p$ は明らかなときは省略するときがあります.

p

進付値

$v_{2} (4) = 2, v_{3} (57) = 1, v_{p} (1) = 0, v_{2} (2020) = 2, v_{p} (p) = 1$ である.
また $v_{p} (n) = v_{p} (- n)$ である.

$p$ 進付値を用いれば $p$ で何回割り切れるかのみに注目できます.また, $k$ を $n = k p^{v_{p} (n)}$ を満たすようにすれば, $k$ は整数で $p$ で割りきれません.逆も然りです.(当たり前ですが結構使う性質かもしれません)
　まずは基本的な性質を証明します.便宜的に $\infty + x = \infty, \infty + \infty = \infty$ とし, $\infty - \infty$ は考えないとします.

$n, m$ を整数とすると
$(1) v_{p} (n m) = v_{p} (n) + v_{p} (m)$ $(2) v_{p} (n + m) \geq min (v_{p} (n), v_{p} (m))$ が成立する.

早速 $n = k p^{v_{p} (n)}$ の表示を用います. $n = k p^{v_{p} (n)}, m = l p^{v_{(} m)}$ とします.
$(1)$ $n m = k l p^{v_{p} (n) + v_{p} (m)}$ であり, $k l$ は $p$ で割り切れないので, $v_{p} (n m) = e_{p} + f_{p} = v_{p} (n) + v_{p} (m)$ となる.
$(2)$ 対称性から $v_{p} (n) \geq v_{p} (m)$ としてよい.このとき $n + m = p^{v_{p} (m)} (k p^{v_{p} (n) - v_{p} (m)} + l)$ となる. $()$ の中身は整数なので $a p^{e}$ ( $a, e$ はそれぞれ $p$ と互いに素な整数,非負整数)と書ける.よって $v_{p} (n + m) = v_{p} (m) + e \geq v_{p} (m)$ となる.

$(2)$ の証明において $v_{p} (n) > v_{p} (m)$ のときは $p^{v_{p} (n) - v_{p} (m)}$ が $p$ の倍数で $l$ が $p$ の倍数でないので,全体として( )の中身は $p$ で割り切れず, $e = 0$ となる.そのため, $v_{p} (n + m) = v_{p} (m)$ となるので, $v_{p} (n) \neq v_{p} (m)$ なら, $v_{p} (n + m) = min (v_{p} (n), v_{p} (m))$ となる.

これらの性質は付値を一般化する際に参考にしている性質だが,一般化については次回以降述べることとする.

LTEの補題

そろそろLTEの補題について述べておきます.

LTEの補題

$p$ を奇素数, $x, y$ が $p$ で割り切れない整数で $x \equiv y (\mod p)$ を満たすなら,任意の正整数 $n$ に対して $v_{p} (x^{n} - y^{n}) = v_{p} (x - y) + v_{p} (n)$ が成り立つ.

まずは一般化の際に用いる方法を紹介する.
$x \equiv y (\mod p)$ より, $x - y = k p^{e}$ とする( $k$ は $p$ で割り切れない)と, $e > 0$ であり, $v_{p} (x - y) = e$ なので
$\begin{aligned} v_{p} (x^{n} - y^{n}) = & v_{p} (x^{n} - (x - k p^{e})^{n})) \\ = & v_{p} (n k p^{e} x^{n - 1} -_{n} C_{2} k^{2} p^{2 e} x^{n - 2} + . . . - (- k p^{e})^{n}) \\ = & v_{p} (k p^{e}) + v_{p} (n x^{n - 1} -_{n} C_{2} k p^{e} x^{n - 2} + . . . + (- k p^{e})^{n - 1}) (∵ 補題1) \\ = & e + v_{p} (n x^{n - 1} -_{n} C_{2} k p^{e} x^{n - 2} + . . . + (- k p^{e})^{n - 1}) \end{aligned}$
となる.
従って, $v_{p} (n) = v_{p} (n x^{n - 1} -_{n} C_{2} k p^{e} x^{n - 2} + . . . + (- k p^{e})^{n - 1})$ を示せば良いが,補題 $1$ の注意から $2$ 以上 $n$ 以下の整数 $l$ に対して $v_{p} (_{n} C_{l} (k p^{e})^{l - 1} x^{n - l}) > v_{p} (n)$ を示せば良く, また $k, x$ は $p$ と互いに素なので, $v_{p} (_{n} C_{l} p^{e (l - 1)}) > v_{p} (n)$ を示せば良い.ここでは整数の範囲で議論したいので少し不思議な変形をする.
$\begin{aligned} v_{p} (_{n} C_{l} p^{e (l - 1)}) + v_{p} (l) = & v_{p} (l_{n} C_{l} p^{e (l - 1)}) \\ = & v_{p} (n_{n - 1} C_{l - 1} p^{e (l - 1)}) \\ \geq & v_{p} (p^{l - 1}) + v_{p} (n) = l - 1 + v_{p} (n) \end{aligned}$ よってこれを移項すれば, $l - 1 > v_{p} (l)$ を示せば良い. $b = v_{p} (l), l = a p^{b}$ と置くと, $l \geq 2$ と $p > 2$ より $a p^{b} - 1 \geq p^{b} - 1 > 2^{b} - 1 = (1 + 1)^{b} - 1 \geq 1 + b - 1 = b$ 最後から $2$ 番目の変形は $b \geq 1$ と二項定理を用いている.よって $v_{p} (_{n} C_{l} (k p^{e})^{l - 1}) > v_{p} (n)$ がわかったので補題 $1$ の $(2)$ とその注意から,
$\begin{aligned} v_{p} (x^{n} - y^{n}) = & e + v_{p} (n x^{n - 1} -_{n} C_{2} k p^{e} x^{n - 2} + . . . + (- k p^{e})^{n - 1}) \\ = & v_{p} (x - y) + v_{p} (n) \end{aligned}$

これでLTEの補題の証明は完了したが帰納法を使った証明も記しておく.(飛ばしても良いです.)

帰納法で証明する.証明 $(1)$ の様に二項定理を使うことも可能だが別の方法を使ってみる.まずはStep $1, 2$ で帰納法の準備をする.

Step1 $n$ が $p$ で割り切れないとき

$v_{p} (x^{n} - y^{n}) = v_{p} (x - y) + v_{p} (x^{n - 1} + x^{n - 2} y + . . . + y^{n - 1})$ なので $v_{p} (x^{n - 1} + x^{n - 2} y + . . . + y^{n - 1}) = v_{p} (n) = 0$ すなわち, $x^{n - 1} + x^{n - 2} y + . . . + y^{n - 1}$ が $p$ で割り切れないことを示せば良い.これは条件 $x \equiv y (\mod p)$ より $x^{n - 1} + x^{n - 2} y + . . . + y^{n - 1} \equiv n x^{n - 1} ≢ 0 (\mod p)$ であることから示される.

Step2 $n = p$ のとき

Step $1$ と同様な方針だが少しだけ異なってくる.
$\begin{aligned} v_{p} (x^{p} - y^{p}) = & v_{p} (x - y) + v_{p} (x^{p - 1} + x^{p - 2} y + . . . + y^{p - 1}) \\ = & v_{p} (x - y) + v_{p} ((x - y) (x^{p - 2} + 2 x^{p - 3} y + . . . + (p - 1) y^{p - 2}) + p y^{p - 1}) \end{aligned}$ ここで補題 $1$ の注意より, $y$ は $p$ で割り切れないので, $(x - y) (x^{p - 2} + 2 x^{p - 3} y + . . . + (p - 1) y^{p - 2})$ が $p$ で $2$ 回以上割り切れることを示せば良い.これは $x - y$ が $p$ で $1$ 回以上割り切れることと $p$ が奇素数であること, $x \equiv y (\mod p)$ より, $\begin{aligned} x^{p - 2} + 2 x^{p - 3} y + . . . + (p - 1) y^{p - 2} \equiv & x^{p - 2} (1 + 2 + . . . + (p - 1)) \\ \equiv & x^{p - 2} \frac{p (p - 1)}{2} \equiv 0 (\mod p) \end{aligned}$ であることから従う.

Step3 帰納法

$n = m p^{v_{p} (n)}$ とし, $v_{p} (n)$ の帰納法で. $v_{p} (x^{n} - y^{n}) = v_{p} (x - y) + v_{p} (n) . . . (1)$ を示す.
$v_{p} (n) = 0$ すなわち, $n$ と $p$ が互いに素なとき.Step $1$ より $(1)$ は成り立つ.
$v_{p} (n) = k$ のとき $(1)$ が成立すると仮定する. $v_{p} (n) = k + 1$ のとき $n = m p^{k + 1}$ と書ける.従ってStep $2$ と帰納法の仮定から $\begin{aligned} v_{p} (x^{n} - y^{n}) = v_{p} ((x^{m p^{k}})^{p} - (y^{m p^{k}})^{p}) = & v_{p} (x^{m p^{k}} - y^{m p^{k}}) + 1 \\ = & v_{p} (x - y) + k + 1 \\ = & v_{p} (x - y) + v_{p} (n) \end{aligned}$ となり $v_{p} (n) = k + 1$ のときも $(1)$ が成立する.以上より数学的帰納法から $v_{p} (x^{n} - y^{n}) = v_{p} (x - y) + v_{p} (n)$ が示された.

LTEの補題の応用

ここからは具体例と応用を見ていく.

LTEの補題

$v_{3} (11 - 2) = 2, v_{3} (3) = 1$ より $v_{3} (11^{3} - 2^{3}) = 2 + 1 = 3$ 実際 $11^{3} - 2^{3} = 1331 - 8 = 1323 = 27 \cdot 49$ となり,補題が正しい事がわかる.
$v_{7} (26 - (- 23)) = 2, v_{7} (2401) = 4$ より, $v_{7} (26^{2401} + 23^{2401}) = v_{7} (26^{2401} - (- 23)^{2401}) = 2 + 4 = 6$ となる.

例題 (UNESCO Competition1995)

$a, n$ を正整数, $p$ を奇素数とし, $a^{p} \equiv 1 (\mod p^{n})$ が成り立っているとする. $a \equiv 1 (\mod p^{n - 1})$ を示せ.

解答

条件式と示すべき式を移項すればLTEの補題が見えてくる.
$n = 1$ のときは示すことはない. $n \geq 2$ のとき,背理法で示す. $a^{p} \equiv 1 (\mod p^{n})$ かつ $a ≢ 1 (\mod p^{n - 1})$ と仮定すると, $v_{p} (a - 1) < n - 1$ である.また,フェルマーの小定理より $a \equiv a^{p} \equiv 1 (\mod p)$ なのでLTEの補題の仮定を満たす.従って $v_{p} (a^{p} - 1) = v_{p} (a - 1) + 1 < n$ となり, $a \equiv 1 (\mod p^{n})$ に矛盾する.

この問題のように $y = 1$ の時にLTEの補題を適用することも結構あります.
整数解を決定する問題も書いてみます.

例題

以下の方程式を満たす非負整数 $(m, n)$ を全て求めよ.
$13^{m} - 4^{m} = 5^{n} - 2^{n}$

あからさまにLTEの匂いがしますね.そうやって見ると $p = 3$ が見えてきます.

解答

$n = 0$ または $m = 0$ のときは明らかに $(m, n) = (0, 0)$ が条件を満たす.よって $m, n$ はともに正整数として良い. $v_{3} (13 - 4) = 2, v_{3} (5 - 2) = 1$ よりLTEの補題から, $2 + v_{3} (m) = 1 + v_{3} (n)$ となる.よって $v_{3} (n) \geq 1$ つまり $n$ は $3$ の倍数となる.よって与式の右辺は $5^{3} - 2^{3} = 117$ で割り切れるが $117 = 9 \cdot 13$ で左辺は $m > 0$ より $13$ で割り切れないので矛盾する.以上より求める非負整数解は $(m, n) = (0, 0)$ のみである.

次回は $p = 2$ のときや有理数などに拡張して一般化の準備を進めるのと,整数解を決定する問題でLTEの補題を使うものを書こうと思います.

参考文献

数学徘徊記:LTEの補題 LTEの補題の証明の二つ目の参考にしました.
Lifting The Exponet Lemma 問題の参考にしました.他にもたくさん問題があるので是非見てみてください(僕は有料pdfなるものは見てませんが)

投稿日：2020年11月7日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

じゅんにー

297

63626

整数が好きです

他の人のコメント

コメントはありません。

読み込み中

じゅんにー

LTEの補題とその応用

$p$ 進付値
LTEの補題
LTEの補題の応用

LTEの補題とその応用

p進付値

LTEの補題

Step1 nがpで割り切れないとき

Step2 n=pのとき

Step3 帰納法

LTEの補題の応用

例題 (UNESCO Competition1995)

解答

例題

解答

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

$p$ 進付値

Step1 $n$ が $p$ で割り切れないとき

Step2 $n = p$ のとき