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

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

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

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

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

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

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

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

IMO Shortlist 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:各地の数オリの過去問