二項係数が素数 p で割り切れない条件 - 球面倶楽部零八式 mark II

${}_nC_{r}$ の偶奇についての話と同じ。

(1) $n!$ が持つ素因数 $p$ の個数 $f(n)$ は $\displaystyle\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor +\cdots$ である。

(2) $f(a+b)\geq f(a)+f(b)$ である。これは一般に $\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloor$ または
$\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloor+1$ となることからわかる。

(3) $f(a+b)\geq f(a)+f(b)$ の等号成立は $\displaystyle\lfloor \frac{a+b}{p^k} \rfloor =\lfloor \frac{a}{p^k} \rfloor+\lfloor \frac{b}{p^k} \rfloor$ が任意の $k$ について成立すること。
つまり、 $p$ 進数における $a+b$ の筆算において繰り上がりが生じないことが必要十分条件となる。

(4)よって ${}_nC_{r}$ が $p$ で割り切れない条件は $p$ 進数における $r+(n-r)$ の筆算において繰り上がりが生じないこととなる。

このことから、例えば、 ${}_7C_{r}$ が5の倍数となる条件を考えると、 $7_{(10)}=12_{(5)}$ であるから、5進数表示で $r=0,1,2,10,11,12$ 、
つまり $r=0,1,2,5,6,7$ のときに5で割り切れないことがわかり、 ${}_{15}C_{r}$ が5の倍数となる条件を考えると、 $15_{(10)}=30_{(5)}$ であるから、5進数表示で $r=10,20$ 、つまり $r=5,10$ のときに5で割り切れないことがわかる。

なお、二項係数が合成数で割り切れる条件は難しいと思う。

例えば、二項係数が8で割り切れない必要十分条件は、2進数における $r+(n-r)$ の筆算において繰り上がりが2回までしか生じないことになるが、まぁ、これは面倒くさい。

2020.07.11追記
大学への数学2001年2月号に雲幸一郎さんの「素数で何回割り切れるか」という記事に
「p進展開で a+b を計算するときに"繰り上がり"が何回起こるかで決まります。」
とあったので、結構良く知られている結果のようだ。
でも、p=2 の場合にビット演算子で繰り上がり判定するのは、
(これも良く知られているのだとは思うが)まだ見たことない。