Lucasの定理とその証明

Lucasの定理

任意の素数 pp と非負整数 m,nm,n に対して,

mCni=0kmiCni(modp)\displaystyle{}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\pmod{p}

ただし,mkmk1m1m0m_km_{k-1}\cdots m_1m_0mmpp 進数表示,nknk1n1n0n_kn_{k-1}\cdots n_1n_0nnpp 進数表示。

なお,mnm\geq n のときは mCn=m!n!(mn)!{}_{m}\mathrm{C}_{n}=\dfrac{m!}{n!(m-n)!} ですが,このページではさらに m<nm < n のときは mCn=0{}_{m}\mathrm{C}_{n}=0 とします。

具体例

具体例を通じてLucasの定理の主張を理解していきましょう。

p=3p=3m=13m=13n=3n=3 としてみます。定理の左辺は,

13C3=13121132=286{}_{13}\mathrm{C}_{3}=\dfrac{13\cdot 12\cdot 11}{3\cdot 2}=286

であり,33 で割った余りは 11 です。

次に定理の右辺について考えます。mmnn33 進数表示(→二進法と十進法の変換方法と計算例)は,

13=132+13+111113=1\cdot 3^2+1\cdot 3+1\to 111

3=13103=1\cdot 3\to 10

なので,

m2Cn2m1Cn1m0Cn0=1C01C11C0=1{}_{m_2}\mathrm{C}_{n_2}\cdot{}_{m_1}\mathrm{C}_{n_1}\cdot{}_{m_0}\mathrm{C}_{n_0}={}_{1}\mathrm{C}_{0}\cdot{}_{1}\mathrm{C}_{1}\cdot{}_{1}\mathrm{C}_{0}=1

となり,33 で割った余りは 11 です。

証明(前半)

Lucasの定理の証明に向けて,まずは以下の補題を示します。二項定理を使うだけなので難しくはありません。

補題

任意の非負整数 ii に対して

(1+x)pi1+xpi(modp)(1+x)^{p^i}\equiv 1+x^{p^i}\pmod{p}

ただし,xx についての整数係数多項式 f(x),g(x)f(x),g(x) について f(x)g(x)f(x)-g(x) の各係数が pp の倍数であるとき f(x)g(x)(modp)f(x)\equiv g(x)\pmod{p} と表記します。

証明

i=0i=0 のときは両辺ともに 1+x1+x となり成立。

i=ji=j のときに補題が成立すると仮定すると,

(1+x)pj+1={(1+x)pj}p=(1+xpj)p(1+x)^{p^{j+1}}=\left\{(1+x)^{p^{j}}\right\}^p\\ =(1+x^{p^j})^p

ここで,上式を二項定理で展開すると pCt(1tp1){}_{p}\mathrm{C}_{t}\:(1\leq t\leq p-1) は全て pp の倍数(→注)なので,modp\mathrm{mod}\:p では 1+xpj+11+x^{p^{j+1}} と等しい。

つまり i=j+1i=j+1 のときにも補題が成立する。帰納法によりOK。

注: tpCt=pp1Ct1t\cdot {}_{p}\mathrm{C}_{t}=p\cdot{}_{p-1}\mathrm{C}_{t-1} であることから分かります。二項係数の有名公式一覧と2つの証明方針でも解説しています。

追記:
上の補題は,帰納法を使わず,以下のように証明することもできました(Twitterでご指摘いただきました)。

証明

任意の t(1tpi1)t\:(1\leq t\leq p^i-1) に対して piCt{}_{p^i}\mathrm{C}_tpp の倍数であることを示せばよい。

tpiCt=pipi1Ct1t\cdot {}_{p^i}\mathrm{C}_t=p^i\cdot{}_{p^i-1}\mathrm{C}_{t-1}

において,右辺は pip^i の倍数なので左辺も pip^i の倍数。t<pit<p^i より,tt が持つ素因数 pp の個数は i1i-1 以下。よって,piCt{}_{p^i}\mathrm{C}_tpp の倍数。

証明(後半)

m=mkpk+mk1pk1++m1p+m0m=m_kp^{k}+m_{k-1}p^{k-1}+\cdots +m_1p+m_0

n=nkpk+nk1pk1++n1p+n0n=n_kp^{k}+n_{k-1}p^{k-1}+\cdots +n_1p+n_0

(ただし,各 mi,nim_i,n_i00 以上 p1p-1 以下)であることを使います。美しいです!

証明

(1+x)m(1+x)^m を展開したときの xnx^n の係数を2通りの方法で考える。まず,二項定理より,これは mCn{}_{m}\mathrm{C}_{n} である。

一方,mmpp 進数表示を使うと,

(1+x)m=(1+x)mkpk(1+x)mk1pk1(1+x)m1p(1+x)m0(1+x)^m\\ =(1+x)^{m_kp^{k}}(1+x)^{m_{k-1}p^{k-1}}\cdots (1+x)^{m_1p}(1+x)^{m_0}

さらに補題を使うと,上式は modp\mathrm{mod}\:p

(1+xpk)mk(1+xpk1)mk1(1+xp)m1(1+x)m0(1+x^{p^k})^{m_k}(1+x^{p^{k-1}})^{m_{k-1}}\cdots (1+x^{p})^{m_1}(1+x)^{m_0}

と等しい。

この式について,xnx^n という項がどのように登場するか考えると,

1つめの因数部分から xnkpkx^{n_kp^k},2つめの因数部分から xnk1pk1x^{n_{k-1}p^{k-1}}\cdots,最後の因数部分から xn0x^{n_0} を取ってきたもののみなので,その係数は

i=0kmiCni\displaystyle\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}

となる(mi<nim_i < n_i となる ii が存在する場合,xnx^n という項は存在しない,これは miCni=0{}_{m_i}\mathrm{C}_{n_i}=0 であることと整合する)。

ルーカスの定理なのかリュカの定理なのか,読み方は両方あるっぽいです(自信ない)。