LTEの補題（2010年京都大学前期理系乙数学第5問）

今回は一昔前の京大の整数問題を取り上げます。数オリ級の整数問題に関心がある方なら「LTEの補題」という名前に見覚えがあるのでは･･･？

（１） $n$ を正の整数、 $a = 2^{n}$ とする。 $3^{a} - 1$ は $2^{n + 2}$ で割り切れるが $2^{n + 3}$ では割り切れないことを示せ。

（２） $m$ を正の偶数とする。 $3^{m} - 1$ が $2^{m}$ で割り切れるならば $m = 2$ または $m = 4$ であることを示せ。

（2010年京都大学前期理系(乙)第5問）

考え方

冪の整除性に関する有名な(？)問題なので、大抵のハイレベルな参考書には載っているのではないかと思います。取り敢えず「LTEの補題」が何であるかは措いておいて、普通の解答を目指すことにします。

（１）は $3^{2^{n}} - 1$ が最大で $n + 2$ 回だけ $2$ で割り切れる、という主張の証明問題です。解答の作りにくい問題に見えますが、 $A_{n} = 3^{2^{n}} - 1$ と定めたときに $A_{n + 1}$ の素因数 $2$ の増え方に着目できれば一歩前進。問題の趣旨からすると $A_{n}$ に比べて $A_{n + 1}$ は $2$ で割り切れる回数が $1$ だけ増えるようなので、これを一般の $n$ について証明すれば良いことになります。結論が分かっている命題の証明なので数学的帰納法を選択するのが自然でしょう。

（２）では $m$ が正の偶数なので $3^{m} - 1$ を因数分解することができます。ただし、このとき $m$ をどのような形で置き換えるかが勝敗の分かれ目となります。（１）の結論を活かせるような形に置き換えるセンスが要求されています。15分程度で解答できれば上々だと思います。

解答例

（１）

$A_{n} = 3^{2^{n}} - 1$ と置き、すべての正の整数 $n$ に対して、

「 $A_{n}$ は $2^{n + 2}$ で割り切れるが $2^{n + 3}$ では割り切れない」･･･( $*$ )

を数学的帰納法で示す。

（ⅰ） $n = 1$ のとき、 $A_{1} = 3^{2} - 1 = 2^{3}$ は $2^{3}$ で割り切れるが $2^{4}$ では割り切れない。よって( $*$ )が成り立つ。

（ⅱ） $n = k$ （ $k$ は自然数）のとき、( $*$ )が成り立つと仮定する。即ち、
「 $A_{k}$ は $2^{k + 2}$ で割り切れるが $2^{k + 3}$ では割り切れない」
とすると、 $A_{k}$ は奇数 $M$ を用いて、 $A_{k} = 2^{k + 2} M$ と表すことができる。このとき、 $\begin{aligned} A_{k + 1} & = 3^{2^{k + 1}} - 1 \\ = 3^{2 \cdot 2^{k}} - 1 \\ = {(3^{2^{k}})}^{2} - 1 \\ = {(A_{k} + 1)}^{2} - 1 \\ = A_{k}^{2} + 2 A_{k} \\ = {(2^{k + 2} M)}^{2} + 2 \cdot 2^{k + 2} M \\ = 2^{k + 3} M (2^{k + 1} M + 1) \end{aligned}$ となる。 $M$ は奇数であるから $2^{k + 1} M + 1$ は奇数なので、 $A_{k + 1}$ は $2^{k + 3}$ で割り切れるが $2^{k + 4}$ では割り切れない。よって $n = k + 1$ のときも( $*$ )が成り立つ。

以上（ⅰ）、（ⅱ）より、すべての正の整数 $n$ に対して( $*$ )は成り立つことが示された。

□

（２）

$m$ は偶数だから $m = 2^{n} L$ と置ける（ただし $n$ は $1$ 以上の整数、 $L$ は奇数）。このとき $A = 3^{2^{n}}$ として、 $\begin{aligned} 3^{m} - 1 \\ = 3^{2^{n} L} - 1 \\ = {(3^{2^{n}})}^{L} - 1 \\ = (3^{2^{n}} - 1) \underset{―}{(\overset{L 個}{\overset{⏞}{A^{L - 1} + A^{L - 2} + \dots + A + 1}})} \end{aligned}$ と式変形できるが、 $A$ と $L$ はともに奇数であるから、上式の下線部は奇数となる。また、（１）の結果より $3^{2^{n}} - 1$ は $2^{n + 2}$ で割り切れるが $2^{n + 3}$ では割り切れないから、 $3^{m} - 1$ は $2^{n + 2}$ で割り切れるが $2^{n + 3}$ では割り切れないことが分かる。

したがって、 $3^{m} - 1$ が $2^{m}$ で割り切れる条件は、 $m ≦ n + 2$ すなわち、 $2^{n} L ≦ n + 2 \dots (* *)$ である。

ここで、 $n ≧ 3$ のとき二項定理より、 $\begin{aligned} 2^{n} & = (1 + 1)^{n} \\ = \sum_{k = 0}^{n}_{n} C_{k} \\ ≧_{n} C_{0} +_{n} C_{1} +_{n} C_{2} +_{n} C_{3} \\ ≧ 1 + n + 1 + 1 \\ > n + 2 \end{aligned}$ となるから、 $(* *)$ を満たすのは $n = 1$ 、 $2$ の場合に限られる。

$n = 1$ 、 $2$ のいずれの場合でも、 $(* *)$ を満たすのは $L = 1$ のみだから、 $(n, L) = (1, 1), (2, 1)$ を得る。

以上より、 $m$ を正の偶数とするとき、 $3^{m} - 1$ が $2^{m}$ で割り切れるならば $m = 2$ または $m = 4$ であることが示された。

□

（１）は数学的帰納法に頼るべき問題です。 $2$ の冪を括り出して ( $2$ の冪)×(奇数) の形に置く方法は整除性を議論する上での常套手段です。

（２）では $m$ が偶数であるという仮定から、 $m = 2 n$ のように置いた人もいるかもしれません。しかしこれでは因数分解はできても、そこから先の議論が進みません。（１）の結論を活かせるように $2$ の冪を括り出して文字で置きましょう。また、解答例では二項定理を用いて絞り込みを行っていますが、 $2^{n} > n + 2$ という不等式は数学的帰納法によっても証明可能です。二項定理が思い付かなければ解けない訳ではありません。

本問を数学オリンピック風に出題するなら、「 $\frac{3^{m} - 1}{2^{m}}$ が整数となるような正の整数 $m$ をすべて求めよ」とでもなるでしょうか。 $m$ が奇数の場合は容易に解決するので、結局 $m$ が偶数の場合について考えることになります。

また、本問の類題とは言い難い問題ですが、以下に示す1984年の東工大前期第1問も素数の冪による整除性が題材になっています。参考にして下さい。

$a$ 、 $b$ を正の整数とする。

（１） $c = a + b$ 、 $d = a^{2} - a b + b^{2}$ とおくとき、不等式 $1 < \frac{c^{2}}{d} ≦ 4$ が成り立つことを示せ。

（２） $a^{3} + b^{3}$ が素数の整数乗になる $a$ 、 $b$ をすべて求めよ。

（1984年東工大前期第1問）

冒頭で少し触れたように、本問は「LTEの補題」(Lifting-the-exponent lemma) の丁度良い練習素材と言えます。まずLTEの補題について簡単におさらいしておきましょう。

整数 $x$ を割りきる素数 $p$ の最大のべきが $p^{n}$ のとき、 $v_{p} (x) = n$ と定義します。つまり、整数 $x$ が素数 $p$ で除することができる最大の回数を $v_{p} (x)$ という記号で表すことにします（これを「 $p$ 進付値」と呼びます）。

一般の素数 $p$ に対して、 $n$ と $p$ が互いに素かつ $p ∣ x - y$ かつ $p ∤ x$ かつ $p ∤ y$ とするとき、 $v_{p} (x^{n} - y^{n}) = v_{p} (x - y)$ が成り立ちます。これは $x = y + k p$ ( $k \in Z$ ) などと置けば二項定理から示されます。ここで「 $p ∣ x - y$ 」は「 $x - y$ は $p$ で割り切れる」という意味で、「 $p ∤ x$ 」は「 $p$ は $x$ を割り切らない」という意味です。

特に $p = 2$ のとき、 $4 ∣ x - y$ かつ $x$ と $y$ が奇数であるならば、 $v_{2} (x^{n} - y^{n}) = v_{2} (x - y) + v_{2} (n)$ が成り立ちます。なお、 $p$ が奇素数の場合は $p | x - y$ 、 $p ∤ x$ 、 $p ∤ y$ の各条件が満足されるときに同様の式が成り立ちます。これらの命題が「LTEの補題」と呼ばれているものです。これは任意の正の整数 $n$ に対して有効な定理です。

LTEの補題を利用すると、 $n$ が正の偶数で、 $x$ と $y$ がともに奇数である場合は $v_{2} (x^{n} - y^{n}) = v_{2} (x - y) + v_{2} (x + y) + v_{2} (n) - 1$ が成り立ちます。 $x$ と $y$ がともに奇数のとき $4 ∣ x^{2} - y^{2}$ が成り立つため、 $p = 2$ の場合のLTEの補題を適用すれば以下のように示せます。 $\begin{aligned} v_{2} (x^{n} - y^{n}) & = v_{2} ({(x^{2})}^{\frac{n}{2}} - {(y^{2})}^{\frac{n}{2}}) \\ = v_{2} (x^{2} - y^{2}) + v_{2} (\frac{n}{2}) \\ = v_{2} (x - y) + v_{2} (x + y) + v_{2} (n) - 1 \end{aligned}$ これを見ると、 $n$ が正の偶数であるという条件が効いているのが分かりますよね。

さて、LTEの補題を既知とすれば本問の（１）は $\begin{aligned} v_{2} (3^{a} - 1^{a}) \\ = v_{2} (3 - 1) + v_{2} (3 + 1) + v_{2} (a) - 1 \\ = 2 + v_{2} (a) \\ = n + 2 (∵ v_{2} (a) = v_{2} (2^{n}) = n) \end{aligned}$ として、あっさり片付きます。

（２）に関してもLTEの補題より $v_{2} (3^{m} - 1^{m}) = n + 2$ が直ちに言えるので、あとは $n + 2 ≧ m = 2^{n} L ≧ 2^{n}$ を満たす $n$ 、 $L$ の組を絞り込むだけで済みます。

LTEの補題はその名の通り、指数が関係する整数問題で威力を発揮し、数学オリンピック級の整数問題を解く上では必需品とも言える定理です。例えば今年のアメリカ数学選抜試験 (AIME) Ｉの第12問でもLTEの補題が活躍しますし、「マスターデーモン」として悪名高い(？) 1990年IMO #3 や1991年IMOのShortlist 1991 #18 などなど、色々な問題に適用できる強力な道具です。

LTEの補題が使えそうな入試問題としては本問の他にも、2008年の東大理科第5問や2012年の名大理系第4問(文系第3問)などが挙げられます。但し、試験本番でLTEの補題を使う場合は証明してから使うべきなので必ずしも実用的とは言えませんが･･･。

月	火	水	木	金	土	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

考え方

（１）

（２）

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル