二項係数と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$$ となる。