1. 高校数学の美しい物語
  2. 数オリの整数論(難問)に対するテクニック

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

更新日時 2021/03/07

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

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

目次
  • 割り切れる回数

  • LTEの補題

  • 数オリの難問に挑戦

割り切れる回数

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

有力な定理ですが使うときはなが~い証明を答案に書かないといけないのが残念です。

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

人気記事
  1. 高校数学の美しい物語
  2. 数オリの整数論(難問)に対するテクニック