2020-09-05

二項係数の剰余　その2

前回の復習
二項係数の素因数の指数の計算方法
応用例
裏技
おまけ

前回の復習

前回は、連続 $\displaystyle{n}$ 整数の積が $\displaystyle{n!}$ で割り切れることの証明の中で、次の定理を示したのでした。ただし、 $\displaystyle{R_p(x)}$ は $\displaystyle{x}$ を $\displaystyle{p}$ で割った余りを表します。

定理1

$\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} }$

haruto117.hatenablog.com

この定理は、連続 $\displaystyle{n}$ 整数の積の素因数について考える上での基礎になります。今回は、これを使って二項係数の素因数について調べようと思います。

二項係数の素因数の指数の計算方法

二項係数 $\displaystyle{\binom{m}{n}}$ は $\displaystyle{\binom{m}{n} =\frac{(m)_n}{(n)_n} }$ ですので、これを $\displaystyle{p}$ で割り切れる回数は

( $\displaystyle{(m)_n}$ を $\displaystyle{p}$ で割り切れる回数) $\displaystyle{-}$ ( $\displaystyle{(n)_n}$ を $\displaystyle{p}$ で割り切れる回数)

となり、確かに定理1が使えそうです。とりあえず、一般に、 $\displaystyle{(x)_n}$ と $\displaystyle{(y)_n}$ の $\displaystyle{p}$ で割り切れる回数を比較する方法を考えてみましょう。

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

となるので、最後のシグマの中身に定理1が使えます。 $\displaystyle{R_{p^k}(x)}$ と $\displaystyle{R_{p^k}(y)}$ を $\displaystyle{R_{p^k}(n)}$ と比較すればいいわけです。式を書きやすくするために、カウンターを定義しましょう。

$\displaystyle{ c(x,n;p^k)=\begin{cases} 1 &(R_{p^k}(x)\lt R_{p^k}(n))\\ 0 &(R_{p^k}(x)\geq R_{p^k}(n)) \end{cases} }$

こうすると、

と、よりわかりやすくなりました。さて、二項係数 $\displaystyle{\binom{m}{n}}$ を考えていたので、実際は $\displaystyle{x=m,y=n}$ です。すると、 $\displaystyle{c(n,n;p^k)=0}$ より、

$\displaystyle{ \sum_{k=1}^{\infty} c(m,n;p^k) }$

と、さらに簡潔になりました。

定理2

二項係数 $\displaystyle{\binom{m}{n}}$ は素数 $\displaystyle{p}$ で

$\displaystyle{ \sum_{k=1}^{\infty} c(m,n;p^k) }$

回割り切れる。

これ以上は綺麗にならないので、一般的な考察はここまでとして、具体例を使って遊んでみましょう。

応用例

定理3

$\displaystyle{p}$ は素数とする。 $\displaystyle{\binom{p}{r} (r=1,2,\cdots ,p-1)}$ は $\displaystyle{p}$ でちょうど1回割り切れる。

(証明) $\displaystyle{R_p(p)=0,R_p(r)\gt 0}$ より $\displaystyle{c(p,r;p)=1}$ 。 $\displaystyle{k\gt 1}$ のときは、 $\displaystyle{R_{p^k}(p)=p,R_{p^k}(r)=r\lt p}$ より $\displaystyle{c(p,r;p^k)=0}$ である。したがって、定理2から $\displaystyle{\binom{p}{k}}$ は $\displaystyle{p}$ でちょうど1回割り切れる。[証明終]

定理4

$\displaystyle{p}$ は素数とする。 $\displaystyle{\binom{p^2}{p}}$ は $\displaystyle{p}$ でちょうど1回割り切れる。

(証明) $\displaystyle{R_p(p^2)=R_p(p)=0}$ より $\displaystyle{c(p^2,p;p)=0}$ 。 $\displaystyle{R_{p^2}(p^2)=0,R_{p^2}(p)=p \gt 0}$ より $\displaystyle{c(p^2,p;p^2)=1}$ なので、定理2から $\displaystyle{\binom{p^2}{p}}$ は $\displaystyle{p}$ でちょうど1回割り切れる。[証明終]

定理5

$\displaystyle{p,q}$ は相異なる素数とする。 $\displaystyle{\binom{pq}{p}}$ は $\displaystyle{p}$ で割り切れない。

(証明) $\displaystyle{c(pq,p;p)=0}$ は明らか。 $\displaystyle{k\gt 1}$ のとき、 $\displaystyle{R_{p^k}(pq)}$ は $\displaystyle{0}$ でない $\displaystyle{p}$ の倍数なので、 $\displaystyle{R_{p^k}(pq) \geq p}$ である。 $\displaystyle{R_{p^k}(p)=p}$ とあわせて、 $\displaystyle{c(pq,p;p^2)=0}$ であるから、定理2より $\displaystyle{\binom{pq}{p}}$ は $\displaystyle{p}$ で割り切れない。[証明終]

こんな風に二項係数の素因数について面白いことがたくさん導けます。やろうと思えばまだまだ作れそうですが、あんまりたくさん作ってもどうしようもないのでこの辺でやめておきましょう。

裏技

ところで、実は $\displaystyle{c(m,n;p^k)}$ を $\displaystyle{k}$ を一つずつ増やしながらちまちま計算するのではなく、一気に計算する方法があります。それは次の定理を利用するものです。

定理6

$\displaystyle{m,n}$ を $\displaystyle{p}$ 進数表示して、 $\displaystyle{m-n}$ を計算するとき、その繰り下がりの回数は

$\displaystyle{ \sum_{k=1}^{\infty} c(m,n;p^k) }$

に等しい。

(証明)

$\displaystyle{ m= \sum_{i=1}^{\infty} M_ip^i\\ n= \sum_{i=1}^{\infty} N_ip^i }$

とする。 $\displaystyle{m-n}$ で $\displaystyle{p^a}$ の桁で繰り下がりが起きるのは、

$\displaystyle{ \sum_{i=1}^{a} M_ip^i \lt \sum_{i=1}^{a} N_ip^i }$

であることと同等である。左辺は $\displaystyle{R_{p^{a+1}}(m)}$ と、右辺は $\displaystyle{R_{p^{a+1}}(n)}$ と等しいから、繰り下がりの回数と、 $\displaystyle{c(m,n;p^k)}$ が1になる回数は等しい。[証明終]

この裏技を使って、あの有名な東京大学2015年の入試問題を解いてみましょう！

東大2015

$\displaystyle{\binom{2015}{m}}$ が偶数になる $\displaystyle{m}$ の最小値を求めよ。

(略解) $\displaystyle{2015-m}$ を2進数で計算したとき少なくとも1回繰り下がるような $\displaystyle{m}$ の最小値を求めればよい。 $\displaystyle{2015=11111011111_{(2)}}$ より、求める $\displaystyle{m}$ は $\displaystyle{m=100000_{(2)}=32}$ である。

おまけ

最後に定理1を使えば解ける自作問題を載せておきます。

問題

$\displaystyle{\prod_{k=1}^{2021}\binom{2021}{k}}$ は43で何回割れるか。

さて、なるほどなるほど、 $\displaystyle{\binom{pq}{p}}$ は $\displaystyle{p}$ で割り切れないのか...と、まさかこれで満足できないですよね。割り切れないなら、当然余りが知りたくなりますよね。ということで、次回は二項係数を素数で割った余りについて見てゆきます。もちろん、定理1や定理2は素因数のことしか考えていないので、余りが0かそうでないかしか判別することができません。したがって、他の方法が必要になります。それは次回のお楽しみに。ではまた。

2020-08-29

二項係数の剰余　その1

整数

この記事では、連続 $\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{R_{p^k}(n)\geq R_{p^k}(n)}$ なので、 $\displaystyle{x=n}$ のときは常に上側、すなわち小さい方の値を取ることになり、 $\displaystyle{k=1,2,\cdots ,\infty}$ で足し合わせた値は最小になります。よって