スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

数論における Lucas の定理とその証明

ちょっと前に Lucas (リュカ) の定理を知るきっかけがあって、おもしろそうだったので調べてみました。


Lucas の定理

非負整数 m, n と素数 p に対して、
m, n の p 進展開を
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
とするとき、二項係数 mCn について
_mC_n \equiv \prod_{i=0}^k _{m_i}C_{k_i} \pmod p
が成り立つ。
ただし、 a < b のときは aCb = 0 と定義する。


証明は [ 続きを読む ] から。

Tags : 数学 代数学 組合せ論


証明

証明は 3 つのステップから成る。

Step 1
素数 p , 整数 r > 0 , 整数 k ( 0 < k < pr ) とするとき、
pr Ck ≡ 0 (mod p) …… (*1)
を示す。

まず、
k \cdot _{p^r}C_k = p^r \cdot _{p^{r-1}}C_{k-1} …… (1)
である。(1) が正しいことは aCb = a! / { b!・(a-b)! } を代入するとすぐにわかる。

ここで (1) の右辺は pr の倍数。 ( ∵ pr-1 Ck-1 は整数 )
一方 k は、高々 pr-1 の倍数にしかなりえない。 ( ∵ 0 < k < pr )
ゆえに、pr Ck は p の倍数 つまり (*1) である。

また、k = 0 , pr のときは、
pr Ck = 1 ≡ 1 (mod p) …… (*2)
であることにも注意しておく。

Step 2
素数 p , 整数 r > 0 , 実数 x とするとき、
(1+x)pr ≡ 1 + xpr (mod p) …… (@)
を示す。

2 項定理 より、
(1+x)pr = 1 + pr C1・x + pr C2・x2 + … + pr Cpr・xpr.

(*1)(*2) より、右辺は最初と最後の項以外が ≡ 0 (mod p) となるから、
(1+x)pr ≡ 1 + 0 + … + 0 + 1・xpr ≡ 1 + xpr (mod p).
ゆえに、(@) が示せた。

Step 3
整数 m, n ( 0 ≦ n ≦ m ) と素数 p に対して、
m, n の p 進展開を
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
とするとき、
_mC_n \equiv \prod_{i=0}^k _{m_i}C_{k_i} \pmod p …… (☆)
を示す。 (これは、最初に掲げた Lucas の定理とほとんど同じ )

( 1 + x )m
= ( 1 + x )mk pk + … + m0
= ( 1 + x )mk pk・ … ・( 1 + x )m0
≡ ( 1 + xpk )mk・ … ・( 1 + x )m0 (mod p)

( 最後の ≡ は (@) による )
ゆえに、
( 1 + x )m ≡ ( 1 + xpk )mk・ … ・( 1 + x )m0 (mod p) …… (2)

(2) で両辺の xn の係数を比較する。
左辺では、自明に mCn.
右辺では、
xn = (xpk )nk・ … ・xn0
に注意すると、
(mk コから nk コを選ぶ組合せの数)× … ×(m0 コから n0 コを選ぶ組合せの数)
= mkCnk・ … ・m0Cn0

が xn の係数になる。

ゆえに (☆) が示せた。

m < n では、
ある i で mi < ni だから miCni = 0 となり、このときにも定理は成り立っている。



証明は主に

を参照しました。
この証明は、上記のサイトの証明を自分がわかりやすいように整理したものです。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。