p進法展開からみる階乗と二項係数の整数論的性質 その１
タイトルの通り，二項係数や階乗がらみの整数論的性質
- 階乗や二項係数がある整数で割り切れる回数
- 階乗や二項係数をある整数で割った余り
などについて見ていきます．前者は今回の記事で，後者は次回紹介します．
階乗が素数$p$で割り切れる回数は，次のルジャンドルの定理を用いて計算できます
$n$を正の整数，$p$を素数とするとき，$p$が$n!$を割り切る回数$ord_p(n!)$は，次の式で与えられる．
$$ord_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right \rfloor $$
$1,2,3,\cdots,n$のうち素数の累乗$p^i$で割り切れる整数の個数は$\left\lfloor \frac{n}{p^i} \right \rfloor $である．よってこれを$i=1,2,3,\cdots$について足し合わせれば良いので，
$$ord_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right \rfloor $$
これで次のような問題に対応できます．
$100!$の末尾に$0$はいくつ並ぶか．
解答
$100!$が$10$で何回割り切れるかを考えれば良い．
ルジャンドルの定理より，
$$ord_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 = 97$$
$$ord_5(100!)=\left\lfloor \frac{100}{5} \right \rfloor + \left\lfloor \frac{100}{25} \right \rfloor = 24$$
よって，$ord_{10}(100!)=\min\{ord_2(100!),\ ord_5(100!)\}=24$
ルジャンドルの定理は具体的な値に対して$p$で割り切れる回数を計算するにはいいですが，ガウス記号を含んでいるので，文字を含んだ一般的な議論をする際にはとても扱いづらいです．そこで分母に$p^i$があることに注目して，$n$の$p$進法展開$n={a_sa_{s-1}\cdots a_0}_{(p)}$をこの式に代入してみます．すると次の式が得られます．
$n$を正の整数，$p$を素数とするとき，
$$ord_p(n!)=\frac{n-s_p(n)}{p-1}$$
ただし，$s_p(n)$は$n$を$p$進法展開したときの各位の和を表す．
$n={a_sa_{s-1}\cdots a_0}_{(p)}$とおく．
ルジャンドルの定理より，
$$ord_p(n!)=\sum_{i=1}^{s} \left\lfloor \frac{n}{p^i} \right \rfloor
=\sum_{i=1}^{s}\sum_{j=i}^{s}a_jp^{j-i}=\sum_{j=1}^{s}\sum_{i=1}^{j}a_jp^{j-i}$$$$=\frac{1}{p-1}\sum_{j=1}^{s}(p^j-1)a_j=\frac{\sum_{j=0}^{s}p^ja_j-\sum_{j=0}^{s}a_j}{p-1}=\frac{n-s_p(n)}{p-1}
$$
この式から，二項係数が素数$p$で割り切れる回数は次のようにもとめられます．
$$ord_p({}_n C _{k})=\frac{s_p(k)+s_p(n-k)-s_p(n)}{p-1}$$
実はこの式の右辺は面白い意味付けができます．$p$進法で引き算$n-k$を筆算によって計算するとき，繰り下がりが置きなければ$s_p(n-k)=s_p(n)-s_p(k)$となりますが，繰り下がりが起きるとその位の数字が$p$増えて，上の位が$1$減るので(ただし上の位が$0$であっても一旦$-1$にするものと考えてください)，繰り下がりが起きるごとに各位の和は$p-1$ずつ増えていくことがわかります．よって次のように言い換えられます．
${}_n C _{k}$が素数$p$で割り切れる回数は，$p$進法における引き算$n-k$で繰り下がりが起きる回数に等しい．
特に二項係数が素数$p$で割り切れるかどうかは次で判定できます．入試問題でも数学オリンピックでも役立ちそうな事実です．
${}_n \mathrm{C}_k$が素数$p$で割り切れないことの必要十分条件は，$n$,$k$の$p$進法展開を，
$n={a_sa_{s-1}\cdots a_0}_{(p)}, k={b_sb_{s-1}\cdots b_0}_{(p)}$
としたとき，すべての$0\leq i \leq s$に対して，$a_i\geq b_i$が成立することである．
最後に，これらを利用して解ける問題を挙げて，終わりにしたいと思います．
${}_{2015} C_{m}$が偶数となる最小の正の整数$m$を求めよ．
(2015年東大)
解答
定理3の系より，$m$を$2$進法展開したとき，
$2015$より大きい位が存在すればいい．
$2015={11111011111}_{(2)}$だから，求める最小値は
${100000}_{(2)}=32$
- $k$を自然数とする．$m$を$m=2^k$とおくとき，$0< n< m$を満たすすべての整数$n$について，二項係数${}_{m} C_{n}$は偶数であることを示せ
- 以下の条件を満たす自然数$m$をすべて求めよ．
条件:$0\le n \le m$を満たすすべての整数$n$について二項係数${}_{m} C_{n}$は奇数である．
(1999年東大)
解答
(1)
$m={1000\cdots00}_{(2)}$より，どのような$0< n< m$を満たす整数$n$をとっても，$2$進法展開において$m$よりも大きい位が存在するので，定理3の系より${}_{m} C_{n}$は偶数
(2)
定理3の系より$m$が題意を満たすには，$m$を$2$進法展開したときすべての桁が$1$となればよい．
よって，$m=2^k-1 (k=1,2,3,\cdots)$
${}_{2022} C_{n}$が$5$で割り切れる回数の最大値はいくらか．また，最大値を取るような$n$は$0\leq n\leq2022$の範囲にいくつあるか．
(自作問題)
解答
$2022={31042}_{(5)}$ (5桁)だから，定理3より$5$で割り切れる回数は高々$4$回．
${24444}_{(5)}$などはこれを満たすから，求める最大値は$4$．
$n={a_4a_3a_2a_1a_0}_{(5)}$とすると，${}_{2022} C_{n}$が$5$で$4$回割り切れることの必要十分条件は，定理3より，
$a_3\ge 1 \land a_2\ge 0 \land a_1\ge 4 \land a_0\ge 3$
ただし$n\le2022$より．$0 \le a_4\le 2$であることに注意する．
よって求める個数は
$3\times 4\times 5\times 1\times 2=120$
いかかだったでしょうか．次回は，階乗や二項係数をある整数で割った余りについて考えていきます．
続き→
p進法展開からみる階乗と二項係数の整数論的性質 その2