【母関数マスター講座 第20回】合同式（mod）と母関数〜二項係数の偶奇を見抜く〜

前回（第19回）は、約数の問題を素因数ごとに独立に分解する指標関数の乗法性を学びました。

今回は、母関数を「mod（合同式）の世界」で考えるとどうなるかを掘り下げます。「 $${{}_{2015}\mathrm{C}_m}$$ が奇数になる $${m}$$ はいくつあるか？」という問題を、母関数の視点で鮮やかに解いてみましょう。

母関数マスター講座の全体像、シラバスは以下の記事でご覧ください。

https://note.com/goukalize/n/ne5f45c351ab2

LINE追加でまとめPDF配布中！
ㅤ
公式LINEを追加して「母関数マスター講座」と送信していただいた方に、講座全体をまとめたPDF（全63ページ）を無料でお配りしています。
ㅤ
自動送信のため、送信文は 「母関数マスター講座」 と正確にお送りください。
ㅤ
https://line.me/R/ti/p/@965ezfgt?oat_content=url

1. mod 2 の世界で母関数を考える

二項定理 $${(1+x)^n = \displaystyle \sum_{k=0}^{n} {}_n\mathrm{C}_k \, x^k}$$ を、係数を「mod 2」で見てみます。つまり、 $${{}_n\mathrm{C}_k}$$ が偶数なら0、奇数なら1として多項式を読むということです。

ここで、素数 $${p}$$ に対して成り立つ次の基本的な性質が出発点になります。

$$
\begin{aligned}
(1+x)^p \equiv 1 + x^p \pmod{p} \tag{①}
\end{aligned}
$$

①は、二項係数 $${{}_p\mathrm{C}_k}$$ が $${k = 0}$$ と $${k = p}$$ 以外のときすべて $${p}$$ の倍数であることから従います。

2. 2進展開と母関数

$${p = 2}$$ の場合、①は $${(1+x)^2 \equiv 1 + x^2 \pmod{2}}$$ です。これを繰り返し適用すると、

$$
\begin{aligned}
(1+x)^{2^k} \equiv 1 + x^{2^k} \pmod{2} \tag{②}
\end{aligned}
$$

ここで、 $${n}$$ を2進展開して $${n = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_s}}$$ （ $${e_1 > e_2 > \cdots > e_s \geq 0}$$ ）と表すと、

$$
\begin{aligned}
(1+x)^n &= (1+x)^{2^{e_1}} (1+x)^{2^{e_2}} \cdots (1+x)^{2^{e_s}} \\
&\equiv (1 + x^{2^{e_1}})(1 + x^{2^{e_2}}) \cdots (1 + x^{2^{e_s}}) \pmod{2} \tag{③}
\end{aligned}
$$

③の右辺を見てください。これは第16回で登場した「2進法の母関数」と同じ構造です！

3. リュカの定理

③の右辺を展開すると、各カッコから「 $${1}$$ を選ぶか $${x^{2^{e_i}}}$$ を選ぶか」の2択を $${s}$$ 回行い、選んだものを掛け合わせた項が並びます。

これが意味するのは、 $${{}_n\mathrm{C}_m}$$ が奇数になるのは「 $${m}$$ の2進表現の各桁が、 $${n}$$ の2進表現の対応する桁以下である」ときに限るということです。これがリュカの定理の特殊ケース（ $${p = 2}$$ ）です。

言い換えると、 $${n}$$ の2進展開で「1が立っているビット」の部分集合として $${m}$$ を選ぶ方法の数だけ、 $${{}_n\mathrm{C}_m}$$ が奇数になります。

4. 2015に適用する

$${2015}$$ を2進展開しましょう。

$$
\begin{aligned}
2015 &= 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 + 2 + 1 \\
&= 2^{10} + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 \tag{④}
\end{aligned}
$$

④より、2015の2進表現は $${(11111011111)_2}$$ です。1が立っている桁は10個あります（ $${2^5}$$ の桁だけが0）。

③より、 $${(1+x)^{2015} \pmod{2}}$$ は10個のカッコの積になります。各カッコで2択なので、mod 2 で $${x^m}$$ の係数が1（つまり $${{}_{ 2015}\mathrm{C}_m}$$ が奇数）になる $${m}$$ の個数は、

$$
\begin{aligned}
2^{10} = 1024 \tag{⑤}
\end{aligned}
$$

⑤より、 $${{}_{2015}\mathrm{C}_m}$$ が奇数になる $${m}$$ （ $${0 \leq m \leq 2015}$$ ）は $${1024}$$ 個です。

5. 一般公式

一般に、 $${n}$$ の2進表現で1が立っている桁の数を $${s(n)}$$ とすると、 $${{}_n\mathrm{C}_m}$$ が奇数になる $${m}$$ の個数は $${2^{s(n)}}$$ です。

2015では $${s(2015) = 10}$$ なので $${2^{10} = 1024}$$ 。もし $${n = 2^k - 1}$$ （すべてのビットが1）なら $${s(n) = k}$$ で、すべての $${{}_n\mathrm{C}_m}$$ が奇数になるという面白い結果も得られます。

まとめ

母関数をmod $${p}$$ の世界で考えると、 $${(1+x)^p \equiv 1 + x^p}$$ という圧縮が起こり、これを繰り返すことで $${p}$$ 進展開と母関数の積構造が直結します。第16回の2進法の話が、ここで合同式と合流しました。

次回、第21回ではいよいよ東大2026年理系第6問に挑みます。第17回〜第19回で学んだ「3の剰余フィルター」と「乗法性」のすべてを投入する、本講座のクライマックスです。

【無料相談受付中】医学部・獣医学部受験対策はゴウカライズにおまかせを！

「一般入試の勉強だけでも大変なのに、面接や小論文までどう準備すればいいかわからない…」
「医学部や獣医学部のような専門性の高い入試に、本当に今の対策で足りるのか不安…」

そんな悩みをお持ちの受験生・保護者の皆様、医学部・獣医学部専門塾 ゴウカライズにご相談ください！

医学部受験・獣医学部受験は、学科試験だけでなく、面接、小論文、志望理由書など学部特有の対策が必要になる入試です。
ゴウカライズでは、それぞれの志望校や受験方式に合わせて、合格に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
医学部・獣医学部の一般入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計します。
日々の進捗管理で、学習の遅れも見逃さず、適宜ルートを最適に修正します。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部・獣医学部特有のテーマに対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は、どちらも特殊な対策が必要です。
面接などがある入試形式の場合、学科試験以外の準備も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://line.me/R/ti/p/@965ezfgt?oat_content=url

#医学部専門予備校 #入試数学 #大学受験 #オンライン塾