Haruto117の数学blog

中の人が考えたり勉強したりした数学関連のことを気が向いたときに投稿します。

二項係数の剰余　その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{ \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( c(x,n;p^k)-c(y,n;p^k) \right) }

と、よりわかりやすくなりました。 さて、二項係数\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かそうでないかしか判別することができません。したがって、他の方法が必要になります。それは次回のお楽しみに。ではまた。