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

はじめに

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

テーマ

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

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

以下、$(x{)}_n=x(x-1)\cdots (x-(n-1))$とします。
$$or{d}_p\left((\genfrac{}{}{0ex}{}{m}{n})\right)=or{d}_p\left(\frac{(m{)}_n}{(n{)}_n}\right)=or{d}_p((m{)}_n)-or{d}_p((n{)}_n)$$
ですから、連続$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$の倍数の個数は、の倍数分ずらした$R_p(x)-R_p(n)+1,\cdots ,R_p(x)$の中の$p$の倍数の個数と同じで、

• $R_p(x)-R_p(n)+1\ge 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{array}{r}\{\begin{array}{l}\lfloor \frac{n}{p}\rfloor (R_p(x)\ge R_p(n)のとき)\\ \lfloor \frac{n}{p}\rfloor +1 (R_p(x)<R_p(n)のとき)\end{array}\end{array}$$
$n\le p$のときも、同じ式が成り立つことが確かめられます(ここでは割愛)。これは二項係数の$or{d}_p$を考えるのにとても有用な判定法です。また、この判定法は$p$が素数である必要はありません。

$or{d}_p\left((\genfrac{}{}{0ex}{}{m}{n})\right)$を求める

上で求めた判定法を用いて、
$$or{d}_p\left((\genfrac{}{}{0ex}{}{m}{n})\right)=or{d}_p((m{)}_n)-or{d}_p((n{)}_n)$$
を求めます。ちょっと一般化して、$or{d}_p((x{)}_n)-or{d}_p((y{)}_n)$を求めましょう。
$$or{d}_p((x{)}_n)=\sum _{k=1}^{\mathrm{\infty }}{f}_{n,p^k}(x)$$
より、
$$or{d}_p((x{)}_n)-or{d}_p((y{)}_n)=\sum _{k=1}^{\mathrm{\infty }}{f}_{n,p^k}(x)-\sum _{k=1}^{\mathrm{\infty }}{f}_{n,p^k}(y)=\sum _{k=1}^{\mathrm{\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)\ge R_{p^k}(n)$かつ$R_{p^k}(y)\ge R_{p^k}(n)$のとき$0$
• $R_{p^k}(x)\ge 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)\ge 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$に何点リードしているか、が$or{d}_p((x{)}_n)-or{d}_p((y{)}_n)$というわけです。
いま、$or{d}_p((m{)}_n)-or{d}_p((n{)}_n)$を求めたかったのですから、$m$と$n$の勝負になります。しかし、任意の$k$に対して、$R_{p^k}(n)\ge R_{p^k}(n)$ですから、$n$はすべてのラウンドで無得点です。したがって、$m$の得点がそのまま$or{d}_p\left((\genfrac{}{}{0ex}{}{m}{n})\right)$になります。

練習問題

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

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

$(2)$ $(\genfrac{}{}{0ex}{}{2015}{m})$が偶数になる最小の$m\ge 1$を求めよ。(東大2015)
[解答]　$(\genfrac{}{}{0ex}{}{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\le 5$までは最大なので$2015$は無得点。得点できる可能性があるのは第$6$ラウンドからで、それは$R_{2^6}(m)>31$のときであり、そのような$m$の最小値は$32$である。

裏技

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

おわりに

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