Lucasの定理とその証明 | 高校数学の美しい物語

任意の素数 ppp と非負整数 m,nm,nm,n に対して， mCn≡∏i=0kmiCni(modp)\displaystyle{}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\pmod{p}m​Cn​≡i=0∏k​mi​​Cni​​(modp) ただし，mkmk−1⋯m1m0m_km_{k-1}\cdots m_1m_0mk​mk−1​⋯m1​m0​ は mmm の ppp 進数表示，nknk−1⋯n1n0n_kn_{k-1}\cdots n_1n_0nk​nk−1​⋯n1​n0​ は nnn の ppp 進数表示。 なお，m≥nm\geq nm≥n のときは mCn=m!n!(m−n)!{}_{m}\mathrm{C}_{n}=\dfrac{m!}{n!(m-n)!}m​Cn​=n!(m−n)!m!​ です