二項係数の剰余　その1 - Haruto117の数学blog

この記事では、連続 $\displaystyle{n}$ 整数の積が $\displaystyle{n!}$ で割り切れることの証明を通して、連続 $\displaystyle{n}$ 整数をその素因数 $\displaystyle{p}$ で何回割れるかを調べます。

定理1

連続n整数の積はn!で割り切れる。

連続n整数の積を

$\displaystyle{ (x)_n=x(x-1)\cdots (x-(n-1)) }$

で表しましょう。すると、この定理は次のように言い換えられます。

定理1'

任意の整数 $\displaystyle{x\geq n}$ に対して、 $\displaystyle{ (x) _ n }$ は $\displaystyle{ (n) _ n }$ で割り切れる。

ということで、 $\displaystyle{ (x) _ n }$ が持つ素因数 $\displaystyle{ p }$ の次数を調べることにします。これには、ルジャンドルの定理という便利な定理がありまして、 $\displaystyle{ x! }$ を $\displaystyle{ p }$ で割り切れる回数は

$\displaystyle{ \sum_{k=1}^{\infty} \lfloor \frac{x}{p^k}\rfloor }$

であることがわかっています。と言っても、 $\displaystyle{ 1,2,\cdots ,x }$ の中の $\displaystyle{ p }$ の倍数の個数、 $\displaystyle{ p^2 }$ の倍数の個数、...を足し合わせたと考えれば当たり前です。 $\displaystyle{ (x)_n=x!/(x-n)! }$ ですから、 $\displaystyle{ (x) _ n }$ の $\displaystyle{ p }$ で割り切れる回数は

$\displaystyle{ \sum_{k=1}^{\infty} \left( \lfloor \frac{x}{p^k}\rfloor-\lfloor \frac{x-n}{p^k}\rfloor \right) }$

となります。

さて、これを $\displaystyle{ x }$ の関数と見て、任意の素数 $\displaystyle{ p }$ に対して $\displaystyle{ x=n }$ のときにこの値が最小になることを示せばよいです。そこで、まずはシグマの中身について考えてみましょう。これは $\displaystyle{ n }$ 整数 $\displaystyle{x-n+1,x-n+2,\cdots ,x}$ の中にある $\displaystyle{p^k}$ の倍数の個数を表しています。これは次の図のように、周の長さが $\displaystyle{p^k}$ の円に長さnの糸を巻きつけてゆく様子と考えるとわかりやすいです。(図は $\displaystyle{p^k}$ が $\displaystyle{p}$ になっていますが同じことです。(すみません、直すのめんどくさいです泣))

f:id:Haruto117:20200829212539j:plain — 周の長さpの円に長さnの糸を巻きつける。目盛り0を糸が通過した回数を数える。ただし、白丸はカウントしない。

このとき問題の個数は、円につけられた印を糸が何回通過しているかに対応していることになります。しかし考えてみると、糸の末端である $\displaystyle{x}$ の位置を変えてみても、その数は2種類(場合によっては1種類)しかないことがわかります。つまり、 $\displaystyle{\lfloor \frac{x}{p^k}\rfloor-\lfloor \frac{x-n}{p^k}\rfloor}$ の値は2つだけということです。具体的には $\displaystyle{\lfloor \frac{n}{p^k}\rfloorか\lfloor \frac{n}{p^k}\rfloor+1}$ です。

では次に考えることは、 $\displaystyle{x}$ がどんな条件を満たすときにどちらの値を取るのか、です。

f:id:Haruto117:20200829213524j:plain — 赤の長さが青の長さより長くなると、カウントが1増える。

この図を見ると、赤い部分の長さが青い部分の長さを超えると $\displaystyle{x-n}$ に対応する糸の先端が印を跨ぐので回数としては大きい方の値をとります。逆に、赤い部分の長さが青い部分の長さ以下であれば小さい方の値をとります。赤い部分の長さとは $\displaystyle{x}$ を $\displaystyle{p^k}$ で割った余りのことであり、青い部分の長さとは $\displaystyle{n}$ を $\displaystyle{p^k}$ で割った余りのことであるので、今述べたことは次の定理にまとめられます。ただし、以降 $\displaystyle{x}$ を $\displaystyle{p}$ で割った余りを $\displaystyle{R_p(x)}$ と書きます。

定理2

$\displaystyle{ \lfloor \frac{x}{p^k}\rfloor-\lfloor \frac{x-n}{p^k}\rfloor= \begin{cases} \lfloor \frac{n}{p^k}\rfloor & (R_{p^k}(x)\geq R_{p^k}(n))\\ \lfloor \frac{n}{p^k}\rfloor+1 & (R_{p^k}(x)\lt R_{p^k}(n)) \end{cases} }$

ここまで来ればもう簡単ですね。当然 $\displaystyle{R_{p^k}(n)\geq R_{p^k}(n)}$ なので、 $\displaystyle{x=n}$ のときは常に上側、すなわち小さい方の値を取ることになり、 $\displaystyle{k=1,2,\cdots ,\infty}$ で足し合わせた値は最小になります。よって

( $\displaystyle{(x)_n}$ が $\displaystyle{p}$ で割り切れる回数) $\displaystyle{\geq}$ ( $\displaystyle{(n)_n}$ が $\displaystyle{p}$ で割り切れる回数)

という不等式が任意の素数 $\displaystyle{p}$ で成り立つことになり、定理1が無事示されました。

次回は、この定理2を使って二項係数が素数で何回割れるかを調べます。ではまた。