二項係数Part1 〜素数pで割れる回数〜

はじめに

これから、何回かに分けて、二項係数の整数論的性質について、見ていきたいと思います。受験生の時に、二項係数関連の問題(東大2015のあれとか)にハマって、あれこれ考えてみたものですので、受験生にも役に立つ話かもしれません。

テーマ

今回は、二項係数を素数$p$で割れる回数について調べます。いちいち「二項係数を素数$p$で割れる回数」というのは面倒なので、一般に、$n$の$p$で割れる回数を$ord_p(n)$と書くことにします。

連続$n$整数に属する$p$の倍数の個数

以下、$(x)_n=x(x-1)\cdots (x-(n-1))$とします。
$$ ord_p\left(\binom{m}{n}\right) =ord_p\left(\frac{(m)_n}{(n)_n}\right) =ord_p\left((m)_n\right)-ord_p\left((n)_n\right) $$
ですから、連続$n$整数に注目するのは自然な発想です。次の問題を考えましょう。

これは明らかに$\lfloor \frac{x}{p}\rfloor -\lfloor \frac{x-n}{p}\rfloor$なわけですが、もう少し踏み込んでおきます。
$R_p(n)$で$n$を$p$で割ったあまりを表します。$n>p$の場合を考えましょう。後ろから$R_p(n)$個を除いて、$x-(kp-1),\cdots, x$とします。$kp$は$n$以下の最大の$p$の倍数です。さて、この個数は$kp$なので、その中の$p$の倍数の個数は$x$によらず$k$個です。いま、除いた$R_p(n)$個$x-(n-1),\cdots ,x-kp$の中の$p$の倍数の個数は、$p$の倍数分ずらした$R_p(x)-R_p(n)+1,\cdots ,R_p(x)$の中の$p$の倍数の個数と同じで、

• $R_p(x)-R_p(n)+1\geq 1$のとき$0$個
• $R_p(x)-R_p(n)+1<1$のとき$1$個

となります。$k=\lfloor \frac{n}{p} \rfloor$であることと合わせて、問題の個数を$f_{n,p}(x)$とすると、次のようにまとめられます。
$$ f_{n,p}(x)= \begin{eqnarray} \left\{ \begin{array}{l} \lfloor \frac{n}{p} \rfloor　(R_p(x)\geq R_p(n)のとき)\\ \lfloor \frac{n}{p} \rfloor+1　(R_p(x) < R_p(n)のとき) \end{array} \right. \end{eqnarray} $$
$n\leq p$のときも、同じ式が成り立つことが確かめられます(ここでは割愛)。これは二項係数の$ord_p$を考えるのにとても有用な判定法です。また、この判定法は$p$が素数である必要はありません。

$ord_p\left(\binom{m}{n}\right)$を求める

上で求めた判定法を用いて、
$$ ord_p\left(\binom{m}{n}\right) =ord_p\left((m)_n\right)-ord_p\left((n)_n\right) $$
を求めます。ちょっと一般化して、$ord_p((x)_n)-ord_p((y)_n)$を求めましょう。
$$ ord_p((x)_n)=\sum_{k=1}^{\infty}f_{n,p^k}(x) $$
より、
$$ ord_p((x)_n)-ord_p((y)_n) =\sum_{k=1}^{\infty}f_{n,p^k}(x)-\sum_{k=1}^{\infty}f_{n,p^k}(y) =\sum_{k=1}^{\infty}(f_{n,p^k}(x)-f_{n,p^k}(y)) $$
です。$f_{n,p^k}(x)-f_{n,p^k}(y)$は判定法により、次のように場合ごとに求められます。

• $R_{p^k}(x)\geq R_{p^k}(n)$かつ$R_{p^k}(y)\geq R_{p^k}(n)$のとき$0$
• $R_{p^k}(x)\geq R_{p^k}(n)$かつ$R_{p^k}(y)< R_{p^k}(n)$のとき$-1$
• $R_{p^k}(x)< R_{p^k}(n)$かつ$R_{p^k}(y)\geq R_{p^k}(n)$のとき$1$
• $R_{p^k}(x)< R_{p^k}(n)$かつ$R_{p^k}(y)< R_{p^k}(n)$のとき$0$

ここで、暗算しやすくするため(?)に、言い換えをしましょう。今、$x$と$y$はゲームをしていて、第$k$ラウンドでは、$R_{p^k}(x)< R_{p^k}(n)$ならば$x$は$1$点を得て、$y$も同様とします。双方の得点差が一定になるまで行い、その時点で$x$が$y$に何点リードしているか、が$ord_p((x)_n)-ord_p((y)_n)$というわけです。
いま、$ord_p\left((m)_n\right)-ord_p\left((n)_n\right)$を求めたかったのですから、$m$と$n$の勝負になります。しかし、任意の$k$に対して、$R_{p^k}(n)\geq R_{p^k}(n)$ですから、$n$はすべてのラウンドで無得点です。したがって、$m$の得点がそのまま$ord_p\left(\binom{m}{n}\right)$になります。

練習問題

実際に使ってみましょう。

$(1)$ $p$を素数とするとき、$\binom{p^2}{p}$は$p$で何回割れるか。
[解答]　第$1$ラウンドは$R_p(p^2)=0\geq R_p(p)$より無得点。第$2$ラウンドは$R_{p^2}(p^2)=0< p=R_{p^2}(p)$より得点。以降$R_{p^k}(p^2)=p^2\geq p=R_{p^k}(p)$より常に無得点だから、求める値は$1$である。

$(2)$ $\binom{2015}{m}$が偶数になる最小の$m\geq 1$を求めよ。(東大2015)
[解答]　$\binom{2015}{m}$が偶数とは、$2$で$1$回以上割り切れるということ。つまり、$R_{2^k}(2015)< R_{2^k}(m)$となる回数が$1$回以上ということである。
$$ R_2(2015)=1,R_{2^2}(2015)=3,R_{2^3}(2015)=7,R_{2^4}(2015)=15,R_{2^5}(2015)=31,R_{2^6}(2015)=31 $$
このように、$R_{2^k}(2015)$は$k\leq 5$までは最大なので$2015$は無得点。得点できる可能性があるのは第$6$ラウンドからで、それは$R_{2^6}(m)>31$のときであり、そのような$m$の最小値は$32$である。

裏技

$ord_p\left(\binom{m}{n}\right)$を求める方法を得ることができましたが、これはさらに次のように言い換えることができます。

おわりに

今回は二項係数の$ord_p$を求めました。Part2では、二項係数の$\mod p$を求めます。
読んでいただきありがとうございました。