2014/12/19

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

分野: 整数問題  レベル: 数学オリンピック

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

割り切れる回数

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

つまり,$v_p(n)=k \iff n$ は $p^k$ の倍数であるが $p^{k+1}$ の倍数でない

$v_3(90)=2,\:v_5(7)=0,\:v_7(14^{100})=100$

「 $n$ を素因数分解したときの $p$ の指数」と言うこともできます。

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

$v_p(n)$ のことをオーダーと呼び,$\mathrm{ord}_pn$ と書く流儀もあるようです。しかしオーダーというと普通は群の位数のことを表すので(→位数の性質と原始根の応用)僕はオーダーと呼ばないべきだと思います。この記事では「割り切れる回数」と言うことにします。

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

LTEの補題

$n$ は正の整数,$x,\:y$ は以下を満たす任意の整数。
$p$ が奇素数,$x-y$ は $p$ の倍数,$x$ と $y$ は $p$ の倍数でないとき,
$v_p(x^n-y^n)=v_p(x-y)+v_p(n)$

  • 数学オリンピックの整数問題では $x^n\pm y^n$ の形の整数が登場する問題が多いです(特に $x^n\pm 1$ という形が頻出)。この形の整数が $p$ で何回割り切れるかを評価する定理です。
  • この大定理が必要な問題は数オリの中でも難問〜超難問ばかりです。定理を知っていても一発で解けることはほとんどありません。 $x^n\pm y^n$ が登場したときはこの大定理よりもまず因数分解を考えてみてください。→因数分解公式(n乗の差、和)
  • 定理を使うときは前提条件の確認を忘れないように注意して下さい。
  • この定理の証明には二項定理を使います(けっこう大変)。しかし,解答中には証明を載せたほうがよいでしょう。また,$p=2$ の場合にも似たような定理が成り立ちます。詳しくはLifting The Exponent Lemmaを参照してください。

数オリの難問に挑戦

IMO Shortlist 1991の問題です。

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

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

解答

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

$n=1991^{1990}$ とおくと,$n$ は奇数であり
$N=1990^{1991^2n}+1992^n=(1990^{1991^2})^n-(-1992)^n$

よって,$x=1990^{1991^2}$,$y=-1992$ とおくと $x-y$ は $1991=181\times 11$ の倍数であることが確認できるので定理が使える:
$v_{11}(N)=v_{11}(x^n-y^n)=v_{11}(x-y)+v_{11}(n)$

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

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

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

注:$\:\mathrm{mod}\:11$ では
$1990^{1991^2}+1992\equiv (-1)^{1991^2}+1=0$
$\:\mathrm{mod}\:11^2$ では
$1990^{1991^2}+1992=(1991-1)^{1991^2}+1992$
二項定理で第一項を展開すると,一番最後の項以外が $1991^2$ の倍数,つまり $11^2$ の倍数となるので,上式は
$\equiv (-1)^{1991^2}+1992=1991\equiv 55$
となる。
よって,$v_{11}(1990^{1991^2}+1992)=1$

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

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

分野: 整数問題  レベル: 数学オリンピック