数オリの整数論(難問)に対するテクニック

数学オリンピックの整数問題でときどき使うテクニックを解説します。pp 進付値・オーダーの話・Lifting The Exponent Lemma・LTEの補題,などと言われているものです。

JMO本選以降の対策にどうぞ。

割り切れる回数

nn は任意の整数,pp を素数とするとき,nnpp何回割り切れるか,その最大の回数vp(n)v_p(n) と書くことにします。

つまり,vp(n)=k    nv_p(n)=k \iff npkp^k の倍数であるが pk+1p^{k+1} の倍数でない

v3(90)=2,v5(7)=0,v7(14100)=100v_3(90)=2,\:v_5(7)=0,\:v_7(14^{100})=100

nn を素因数分解したときの pp の指数」と言うこともできます。

また,任意の pp に対して vp(0)=v_p(0)=\infty とします。

vp(n)v_p(n) のことをオーダーと呼び,ordpn\mathrm{ord}_pn と書くこともあるようです。しかしオーダーというと群の位数を表す(→位数の性質と原始根の応用)こともあるので紛らわしいです。この記事では「割り切れる回数」と言うことにします。

なお,「合成数で割り切れる回数」は「素数で割り切れる回数」を求める問題に帰着できます。例えば 1010 で割り切れる回数は 22 で割り切れる回数と 55 で割り切れる回数のうち小さい方です。似た話題として→ルジャンドルの定理(階乗が持つ素因数pのべき数)もどうぞ。

LTEの補題

nn は正の整数,x,yx,\:y は任意の整数で,

pp が奇素数で,xyx-ypp の倍数で,xxyypp の倍数でないとき,

vp(xnyn)=vp(xy)+vp(n)v_p(x^n-y^n)=v_p(x-y)+v_p(n)

  • 数学オリンピックの整数問題では xn±ynx^n\pm y^n の形の整数が登場することが多いです(特に xn±1x^n\pm 1 という形が頻出)。この形の整数が pp で何回割り切れるかを評価する定理です。
  • この大定理が必要な問題は,数オリの中でも難問〜超難問ばかりです。定理を知っていても一発で解けることはほとんどありません。xn±ynx^n\pm y^n が登場したときはこの大定理よりもまず因数分解を考えてみてください。→因数分解公式(n乗の差,和)
  • 定理を使うときは前提条件の確認を忘れないように注意して下さい。
  • 定理の証明には二項定理を使います(けっこう大変)。また,p=2p=2 の場合にも似たような定理が成り立ちます。詳しくは Lifting The Exponent Lemma (LTE) - Art of Problem Solving と検索してヒットする(2017年10月現在の情報)PDFファイルを参照してください。

数オリの難問に挑戦

IMO Shortlist 1991の問題です。

N=199019911992+199219911990N=1990^{1991^{1992}}+1992^{1991^{1990}}19911991 で最大何回割り切れるか求めよ。

方針

あからさまに上記の定理を使う問題です。定理を知らないと厳しいです。まずは定理が使えるように xnynx^n-y^n という形に変形します。

解答

1991=181×111991=181\times 11 であるので v11(N)v_{11}(N)v181(N)v_{181}(N) のうち小さい方の値が答え。ということでそれぞれ求める。

n=19911990n=1991^{1990} とおくと,nn は奇数であり

N=199019912n+1992n=(199019912)n(1992)nN=1990^{1991^2n}+1992^n=(1990^{1991^2})^n-(-1992)^n

よって,x=199019912x=1990^{1991^2}y=1992y=-1992 とおくと xyx-y1991=181×111991=181\times 11 の倍数であることが確認できるので定理が使える:

v11(N)=v11(xnyn)=v11(xy)+v11(n)v_{11}(N)=v_{11}(x^n-y^n)=v_{11}(x-y)+v_{11}(n)

最右辺の二項はそれぞれ計算できる。

  • v11(xy)=v11(199019912+1992)=1v_{11}(x-y)=v_{11}(1990^{1991^2}+1992)=1(注)
  • v11(n)=v11(1119901811990)=1990v_{11}(n)=v_{11}(11^{1990}181^{1990})=1990

より v11(N)=1+1990=1991v_{11}(N)=1+1990=1991 となる。全く同様に v181(N)=1991v_{181}(N)=1991 となる。よって求める答えは 19911991

注: mod11\:\mathrm{mod}\:11 では

199019912+1992(1)19912+1=01990^{1991^2}+1992\equiv (-1)^{1991^2}+1=0

mod112\:\mathrm{mod}\:11^2 では

199019912+1992=(19911)19912+19921990^{1991^2}+1992=(1991-1)^{1991^2}+1992

二項定理で第一項を展開すると,一番最後の項以外が 199121991^2 の倍数,つまり 11211^2 の倍数となるので,上式は

(1)19912+1992=199155\equiv (-1)^{1991^2}+1992=1991\equiv 55

となる。

よって,v11(199019912+1992)=1v_{11}(1990^{1991^2}+1992)=1

LTEと聞くと,携帯の通信規格を思い出す人と Lifting The Exponent Lemma を思い出す人がいます。

Tag:各地の数オリの過去問