二項係数とp進法

今回は二項係数をp進法展開を用いて考察していきたいと思います。 説明するよりも、見てもらった方が早いと思うので今回は二つの問題を紹介します。 それでは、よろしくお願いします。

元記事で、議論を広げる素晴らしいコメントをいただいています。 興味があったら見てみてください。

問題1

方針：\(_{2022}C_{n}\) を \((x+1)^{2022}\) の \(x^{n}\) の係数と見て, \(p\) で割った余りを考える。

解答

\((x+1)^{2022}\) を \(5\) で割った余りを考える。 以下では \(x\) は整数とし、合同式は全て \(5\) を法とする。 \[ \begin{align*} (x+1)^5 & = x^5+5x^4+10x^3+10x^2+5x+1 \\ & \equiv x^5+1 \end{align*} \] であり、さらに、 $$ \begin{align*} (x+1)^{5^k} & \equiv x^{5^k}+1 \end{align*} $$ である。 これを用いて、\(5\) 進法で展開することを考える。 \(2022_{(10)}=31042_{(5)}\) であるから、 \((x+1)^{2022}\) を \(5\) で割った余りは以下のように表現することができる。 $$ \begin{align*} (x+1)^{2022} & = \left(x+1\right)^{3\cdot 5^4} \left(x+1\right)^{1\cdot 5^3} \left(x+1\right)^{0\cdot 5^2} \left(x+1\right)^{4\cdot 5^1} \left(x+1\right)^{2\cdot 5^0} \\ & \equiv \left(x^{5^4}+1\right)^{3}\left(x^{5^3}+1\right)\left(x^{5^1}+1\right)^{4}\left(x^{5^0}+1\right)^{2} \\ & \equiv \left(x^{625}+1\right)^{3}\left(x^{125}+1\right)\left(x^{5}+1\right)^{4}\left(x+1\right)^{2} \end{align*} $$ ここで、\(x^{625}=x_4,x^{125}=x_3,x^{25}=x_2,x^{5}=x_1,x^1=x_0\) とすると、 $$ \begin{align*} \left(x^{625}+1\right)^{3}\left(x^{125}+1\right)\left(x^{5}+1\right)^{4}\left(x+1\right)^{2} & = (x_{4}+1)^3(x_{3}+1)(x_{1}+1)^4(x_{0}+1)^2 \\ & \equiv ({x_{4}}^3+3{x_{4}}^2+3{x_{4}}+1)(x_{3}+1)({x_{1}}^4+4{x_{1}}^3+6{x_{1}}^2+4{x_{1}}+1)({x_{0}}^2+2{x_{0}}+1) \end{align*} $$ となる。 ここで、 上の式は \(5\) の倍数を含んでいないので展開しても \(5\) の倍数を含む項は存在しない。 逆に上の式にない項は \(5\) で割り切れる。 よって、\(5\) の倍数とならないような \(n\) は \(4\times 2\times 1\times 5\times 3=120\) となって \(120\) 個存在する。 したがって、求める \(n\) の個数は \(2022-120=1902\) となって \(1902\) 個となる。

問題2

方針：問題1と同様

解答

以下では合同式は全て \(4\) を法とする。 \[(x+1)^4 = x^4 +4x^3 + 6x^2 + 4x + 1 \equiv x^4 +2x^2 + 1 = (x^2+1)^2\] であるので、これを利用して、 \[(x+1)^{2^{k+1}} \equiv (x^{2^k}+1)^2\] となる。 \((x+1)^{2021}\) の \(x^{37}\) の係数について考える。 \(2021_{(10)} = 11111100101_{(2)}\) であるので、 \[ \begin{align*} (x+1)^{2021} & = (x+1)^{2^{10}}(x+1)^{2^9}(x+1)^{2^8}(x+1)^{2^7}(x+1)^{2^6}(x+1)^{2^5}(x+1)^{2^2}(x+1)^{2^0} \\ & \equiv (x^{2^9}+1)^{2}(x^{2^8}+1)^{2}(x^{2^7}+1)^{2}(x^{2^6}+1)^{2}(x^{2^5}+1)^{2}(x^{2^4}+1)^{2}(x^{2^1}+1)^{2}(x+1)^{2^0} \\ & \equiv (x^{512}+1)^2(x^{256}+1)^2(x^{128}+1)^2(x^{64}+1)^2(x^{32}+1)^2(x^{16}+1)^2(x^2+1)^2(x+1) \end{align*} \] となる。 \(x^{37}\) の係数さえわかればよいので、\(x^{64}\) 以上の項は無視してよい。 \[(x^{2^5}+1)^2(x^{2^4}+1)^2(x^{2^1}+1)^2(x^{2^0}+1)=(x^{2^5}+1)(x^{2^5}+1)(x^{2^4}+1)(x^{2^4}+1)(x^{2^1}+1)(x^{2^1}+1)(x^{2^0}+1)\] の \(x^{37}\) の係数を考える。 ここで、さらに \(37_{(10)} = 100101_{(2)}\) であるから、 \[_{2021}C_{37} \equiv 3\] となる。