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

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


 

(1)nを正の整数、a=2n とする。3a12n+2 で割り切れるが 2n+3 では割り切れないことを示せ。

(2)mを正の偶数とする。3m12m で割り切れるならば m=2 または m=4 であることを示せ。

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

 

 考え方

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

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

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


解答例

 

(1)

An=32n1 と置き、すべての正の整数nに対して、

 

An2n+2で割り切れるが2n+3では割り切れない」・・・()

 

を数学的帰納法で示す。

 

(ⅰ)n=1 のとき、A1=321=2323で割り切れるが24では割り切れない。よって()が成り立つ。

 

(ⅱ)n=kkは自然数)のとき、()が成り立つと仮定する。即ち、
Ak2k+2で割り切れるが2k+3では割り切れない」
とすると、Akは奇数Mを用いて、Ak=2k+2Mと表すことができる。このとき、Ak+1=32k+11=322k1=(32k)21=(Ak+1)21=Ak2+2Ak=(2k+2M)2+22k+2M=2k+3M(2k+1M+1)となる。Mは奇数であるから 2k+1M+1 は奇数なので、Ak+12k+3で割り切れるが2k+4では割り切れない。よって n=k+1 のときも()が成り立つ。

 

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

 

 

(2)

mは偶数だからm=2nLと置ける(ただしn1以上の整数、Lは奇数)。このとき A=32n として、3m1=32nL1=(32n)L1=(32n1)(AL1+AL2++A+1L)と式変形できるが、ALはともに奇数であるから、上式の下線部は奇数となる。また、(1)の結果より 32n12n+2で割り切れるが2n+3では割り切れないから、3m12n+2で割り切れるが2n+3では割り切れないことが分かる。

 

したがって、3m12mで割り切れる条件は、mn+2すなわち、2nLn+2()である。

 

ここで、n3 のとき二項定理より、2n=(1+1)n=k=0nnCknC0+nC1+nC2+nC31+n+1+1>n+2となるから、()を満たすのは n=12 の場合に限られる。

 

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

 

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

 


 

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

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

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

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

abを正の整数とする。

(1)c=a+bd=a2ab+b2 とおくとき、不等式 1<c2d4 が成り立つことを示せ。

(2)a3+b3 が素数の整数乗になるabをすべて求めよ。

(1984年東工大前期第1問)


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

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

一般の素数pに対して、npが互いに素 かつ pxy かつ px かつ pyとするとき、vp(xnyn)=vp(xy)が成り立ちます。これは x=y+kp (kZ) などと置けば二項定理から示されます。ここで「pxy」は「xypで割り切れる」という意味で、「px」は「pxを割り切らない」という意味です。

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

LTEの補題を利用すると、nが正の偶数で、xyがともに奇数である場合はv2(xnyn)=v2(xy)+v2(x+y)+v2(n)1が成り立ちます。xyがともに奇数のとき 4x2y2 が成り立つため、p=2 の場合のLTEの補題を適用すれば以下のように示せます。v2(xnyn)=v2((x2)n2(y2)n2)=v2(x2y2)+v2(n2)=v2(xy)+v2(x+y)+v2(n)1これを見ると、nが正の偶数であるという条件が効いているのが分かりますよね。

さて、LTEの補題を既知とすれば本問の(1)はv2(3a1a)=v2(31)+v2(3+1)+v2(a)1=2+v2(a)=n+2(v2(a)=v2(2n)=n)として、あっさり片付きます。

(2)に関してもLTEの補題よりv2(3m1m)=n+2が直ちに言えるので、あとはn+2m=2nL2nを満たすnLの組を絞り込むだけで済みます。


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

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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

©Copyright 2017-2025 理系のための備忘録 All Rights Reserved.