2016/01/01

Lucasの定理とその証明

分野: 整数問題  レベル: マニアック

Lucasの定理:
任意の素数 $p$ と非負整数 $m,n$ に対して,
$\displaystyle{}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\:\mathrm{mod}\:p$

ただし,$m_km_{k-1}\cdots m_1m_0$ は $m$ の $p$ 進数表示,$n_kn_{k-1}\cdots n_1n_0$ は $n$ の $p$ 進数表示。

なお,$m=n$ のときは${}_{m}\mathrm{C}_{n}=1$,$m < n$ のときは${}_{m}\mathrm{C}_{n}=0$ とします。

具体例

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

$p=3$,$m=13$,$n=3$ としてみます。定理の左辺は,
${}_{13}\mathrm{C}_{3}=\dfrac{13\cdot 12\cdot 11}{3\cdot 2}=286$
であり,$3$ で割った余りは $1$ です。

次に定理の右辺について考えます。 $m$ と $n$ の $3$ 進数表示(→二進法と十進法の変換方法と計算例)は,
$13=1\cdot 3^2+1\cdot 3+1\to 111$
$3=1\cdot 3\to 10$
なので,
${}_{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$
となり,$3$ で割った余りは $1$ です。

証明(前半)

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

補題:
任意の非負整数 $i$ に対して
$(1+x)^{p^i}\equiv 1+x^{p^i}\:\mathrm{mod}\:p$

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

証明

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

$i=j$ のときに補題が成立すると仮定すると,
$(1+x)^{p^{j+1}}=\left\{(1+x)^{p^{j}}\right\}^p\\
=(1+x^{p^j})^p$

ここで,上式を二項定理で展開すると${}_{p}\mathrm{C}_{t}\:(1\leq t\leq p-1)$ は全て $p$ の倍数(→注)なので,$\mathrm{mod}\:p$ では $1+x^{p^{j+1}}$ と等しい。
つまり $i=j+1$ のときにも補題が成立する。帰納法によりOK。

注:${}_{p}\mathrm{C}_{t}=\dfrac{p!}{t!(p-t)!}$ であることから分かります。二項係数の有名公式でも解説しています。

証明(後半)

$m=m_kp^{k}+m_{k-1}p^{k-1}+\cdots +m_1p+m_0$
$n=n_kp^{k}+n_{k-1}p^{k-1}+\cdots +n_1p+n_0$
(ただし,各 $m_i,n_i$ は $0$ 以上 $p-1$ 以下)
であることを使います。美しいです!

証明

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

一方,$m$ の $p$ 進数表示を使うと,
$(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}$

さらに補題を使うと,上式
$\equiv (1+x^{p^k})^{m_k}(1+x^{p^{k-1}})^{m_{k-1}}\cdots (1+x^{p})^{m_1}(1+x)^{m_0}\:\mathrm{mod}\:p$

この式について,$x^n$ という項がどのように登場するか考えると,
1つめの因数部分から $x^{n_kp^k}$,2つめの因数部分から $x^{n_{k-1}p^{k-1}}$,$\cdots$,最後の因数部分から $x^{n_0}$ を取ってきたもののみなので,その係数は
$\displaystyle\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}$
となる($m_i < n_i$ となる $i$ が存在する場合,$x^n$ という項は存在しない,これは${}_{m_i}\mathrm{C}_{n_i}=0$ であることと整合する)。

ルーカスの定理なのかリュカの定理なのか,読み方は両方あるっぽいです(自信ない)。
分野: 整数問題  レベル: マニアック