数学オリンピック / 数論

p進評価

p進評価は「その整数に素数 \(p\) が何回含まれるか」を数える記法です。割り切れの問題を、指数の比較に変えられます。

定義

素数 \(p\) と正整数 \(n\) に対し、 \(p^e\mid n\) かつ \(p^{e+1}\nmid n\) を満たす整数 \(e\ge0\) を \(v_p(n)\) と定義します。

例として \(72=2^3\cdot3^2\) なので \(v_2(72)=3,\ v_3(72)=2\) です。

基本性質

\(v_p(ab)=v_p(a)+v_p(b)\)
\(v_p(a^k)=k\,v_p(a)\)（\(k\) は非負整数）
\(v_p\!\left(\frac{a}{b}\right)=v_p(a)-v_p(b)\)（\(a,b\neq0\) を有理数で考える）
\(v_p(a+b)\ge\min\{v_p(a),v_p(b)\}\)

証明を見る

たとえば \(a=p^ru,\ b=p^sv\)（\(p\nmid u,v\)）と書くと \(ab=p^{r+s}(uv)\) で \(p\nmid uv\) だから \(v_p(ab)=r+s\) です。加法の不等式は \(a+b=p^{\min(r,s)}(p^{r-\min(r,s)}u+p^{s-\min(r,s)}v)\) と因数分解すれば従います。

Legendreの公式

階乗に含まれる \(p\) の個数は次で求まります。

v_p(n!)=\sum_{k\ge1}\left\lfloor\frac{n}{p^k}\right\rfloor

証明を見る

\(1\) から \(n\) までのうち \(p\) の倍数は \(\lfloor n/p\rfloor\) 個あり、それぞれ最低1個の \(p\) を供給します。さらに \(p^2\) の倍数は追加で1個、\(p^3\) の倍数はさらに1個というように数えると、ちょうど上の和になります。

例題

例1：階乗の2進評価

\(v_2(100!)\) を求めます。

解答を見る

v_2(100!)= \left\lfloor\frac{100}{2}\right\rfloor+ \left\lfloor\frac{100}{4}\right\rfloor+ \left\lfloor\frac{100}{8}\right\rfloor+ \left\lfloor\frac{100}{16}\right\rfloor+ \left\lfloor\frac{100}{32}\right\rfloor+ \left\lfloor\frac{100}{64}\right\rfloor =50+25+12+6+3+1=97

例2：二項係数の3進評価

\(v_3\!\left(\binom{10}{4}\right)\) を求めます。

解答を見る

\(\binom{10}{4}=\frac{10!}{4!6!}\) なので

v_3\!\left(\binom{10}{4}\right)=v_3(10!)-v_3(4!)-v_3(6!)=(3+1)-1-2=1

よって 3 でちょうど1回割り切れます。

例3：最大公約数を指数で処理

\(A=2^{20}3^{12}5^3,\ B=2^{14}3^{15}5\) の \(\gcd(A,B)\) を求めます。

解答を見る

\(v_2\) は \(\min(20,14)=14\)、\(v_3\) は \(\min(12,15)=12\)、\(v_5\) は \(\min(3,1)=1\) です。よって \(\gcd(A,B)=2^{14}3^{12}5\) です。

例4：和での注意

\(v_2(12+20)\) と \(\min(v_2(12),v_2(20))\) を比べます。

解答を見る

\(v_2(12)=2,\ v_2(20)=2\) なので最小値は \(2\) です。しかし \(12+20=32\) なので \(v_2(32)=5\) です。したがって等号は常には成り立たず、不等号 \(\ge\) だけが一般に正しいと分かります。

数学オリンピックでの使いどころ

「何乗で割り切れるか」を厳密に出す問題
二項係数や階乗の素因数の個数評価
LTEやKummerの定理を使う前処理

ありがちな失敗

\(v_p(a+b)=\min(v_p(a),v_p(b))\) と常に等しいと思い込む
Legendreの和でゼロになる項まで足し続ける
\(p\) が素数である条件を忘れて \(v_6\) のように書く

次に学ぶもの

Kummerの定理（桁上がりと二項係数）
LTE（指数引き上げ補題）
合同式と併用した整除性の証明