高校数学解説

文献あり

p進法展開からみる階乗と二項係数の整数論的性質その１

階乗,初等整数論,二項係数

1740

タイトルの通り，二項係数や階乗がらみの整数論的性質

階乗や二項係数がある整数で割り切れる回数
階乗や二項係数をある整数で割った余り

などについて見ていきます．前者は今回の記事で，後者は次回紹介します．

階乗が素数 $p$ で割り切れる回数は，次のルジャンドルの定理を用いて計算できます

ルジャンドルの定理

$n$ を正の整数， $p$ を素数とするとき， $p$ が $n!$ を割り切る回数 $o r d_{p} (n!)$ は，次の式で与えられる．
$o r d_{p} (n!) = \sum_{i = 1}^{\infty} ⌊ \frac{n}{p^{i}} ⌋$

$1, 2, 3, \dots, n$ のうち素数の累乗 $p^{i}$ で割り切れる整数の個数は $⌊ \frac{n}{p^{i}} ⌋$ である．よってこれを $i = 1, 2, 3, \dots$ について足し合わせれば良いので，
$o r d_{p} (n!) = \sum_{i = 1}^{\infty} ⌊ \frac{n}{p^{i}} ⌋$

これで次のような問題に対応できます．

$100!$ の末尾に $0$ はいくつ並ぶか．

解答

100!

が

10

で何回割り切れるかを考えれば良い．
ルジャンドルの定理より，

o r d_{2} (100!) = ⌊ \frac{100}{2} ⌋ + ⌊ \frac{100}{4} ⌋ + ⌊ \frac{100}{8} ⌋ + ⌊ \frac{100}{16} ⌋ + ⌊ \frac{100}{32} ⌋ + ⌊ \frac{100}{64} ⌋ = 97

o r d_{5} (100!) = ⌊ \frac{100}{5} ⌋ + ⌊ \frac{100}{25} ⌋ = 24

よって，

o r d_{10} (100!) = min {o r d_{2} (100!), o r d_{5} (100!)} = 24

ルジャンドルの定理は具体的な値に対して $p$ で割り切れる回数を計算するにはいいですが，ガウス記号を含んでいるので，文字を含んだ一般的な議論をする際にはとても扱いづらいです．そこで分母に $p^{i}$ があることに注目して， $n$ の $p$ 進法展開 $n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}$ をこの式に代入してみます．すると次の式が得られます．

$n$ を正の整数， $p$ を素数とするとき，
$o r d_{p} (n!) = \frac{n - s_{p} (n)}{p - 1}$
ただし， $s_{p} (n)$ は $n$ を $p$ 進法展開したときの各位の和を表す．

$n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}$ とおく．
ルジャンドルの定理より，
$o r d_{p} (n!) = \sum_{i = 1}^{s} ⌊ \frac{n}{p^{i}} ⌋ = \sum_{i = 1}^{s} \sum_{j = i}^{s} a_{j} p^{j - i} = \sum_{j = 1}^{s} \sum_{i = 1}^{j} a_{j} p^{j - i}$ $= \frac{1}{p - 1} \sum_{j = 1}^{s} (p^{j} - 1) a_{j} = \frac{\sum_{j = 0}^{s} p^{j} a_{j} - \sum_{j = 0}^{s} a_{j}}{p - 1} = \frac{n - s_{p} (n)}{p - 1}$

この式から，二項係数が素数 $p$ で割り切れる回数は次のようにもとめられます．

$o r d_{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} C_{k}$ が素数 $p$ で割り切れないことの必要十分条件は， $n$ , $k$ の $p$ 進法展開を，
$n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}, k = {b_{s} b_{s - 1} \dots 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 \leq n \leq m$ を満たすすべての整数 $n$ について二項係数 $_{m} C_{n}$ は奇数である．

(1999年東大)

解答

(1)

m = {1000 \dots 00}_{(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, \dots)

$_{2022} C_{n}$ が $5$ で割り切れる回数の最大値はいくらか．また，最大値を取るような $n$ は $0 \leq n \leq 2022$ の範囲にいくつあるか．
(自作問題)

解答

2022 = 31042_{(5)}

(5桁)だから，定理3より

5

で割り切れる回数は高々

4

回．

24444_{(5)}

などはこれを満たすから，求める最大値は

4

．

n = {a_{4} a_{3} a_{2} a_{1} a_{0}}_{(5)}

とすると，

_{2022} C_{n}

が

5

で

4

回割り切れることの必要十分条件は，定理3より，
　　

a_{3} \geq 1 \land a_{2} \geq 0 \land a_{1} \geq 4 \land a_{0} \geq 3

ただし

n \leq 2022

より．

0 \leq a_{4} \leq 2

であることに注意する．

よって求める個数は
　　

3 \times 4 \times 5 \times 1 \times 2 = 120

いかかだったでしょうか．次回は，階乗や二項係数をある整数で割った余りについて考えていきます．
続き→ p進法展開からみる階乗と二項係数の整数論的性質その2

参考文献

[1]

Unknown, 取得中..., Mathlog, アクセス日: Sat Apr 22 2023

投稿日：2022年6月25日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

dragoemon

144

31667

大学3年生です

他の人のコメント

コメントはありません。

読み込み中

dragoemon

p進法展開からみる階乗と二項係数の整数論的性質その１

参考文献

p進法展開からみる階乗と二項係数の整数論的性質 その１

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

p進法展開からみる階乗と二項係数の整数論的性質その１