リュカの定理

数論において リュカの定理（リュカのていり、英: Lucas's theorem）とは、二項係数  を素数pで割った余りを、整数mとnのp進展開を用いて表す定理である。

リュカの定理は1878年にÉdouard Lucas.Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500の論文にて初めて登場した。

 主張 
任意の非負整数m,n及び素数pに対して、次の合同式が成立する。



ここで、

はそれぞれm,nのp進展開である。また、m < nの時はと定める。




 証明  

 結果 
リュカの定理の帰結の一つとして、二項係数  が素数 p で割り切れることと n の p 進表記における少なくとも一つの桁が、対応する m の桁よりも大きいことは同値である。特に、p=2 の場合、 が奇数になるのは n の二進数の各桁（ビット）が m のビットの部分集合である時に限られる。

 非素数法への拡張 
リュカの定理は、二項係数  を素数冪 pk で割った余りを求める形に一般化することができる。しかし、その場合の公式はより複雑になる。

特に素数 p の平方 p2 を法とする場合は、任意の 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, b ≥ 0 において次の合同式が成り立つ：



ここで  は n-番目の 調和数  である。より高い素冪 pk に対するリュカの定理の一般化は Davis と Webb (1990) および Granville (1997) によって与えられている。

また、クンマーの定理 によれば、二項係数  が素数 p で割り切れる最大の回数（P進付値）は n と m − n を p進法で加えた時に生じる繰り上がりの数と等しい。

 q二項係数への拡張 
リュカの定理には q二項係数 への一般化が存在する。整数 a, b, r, s, k が 0 ≤ b, s < k を満たすとき、以下の合同式が成立する： ここで、 および は q二項係数、は通常の二項係数、は変数 q に対する k 番目の円分多項式を表す。

 脚注 

 外部リンク 




Category:証明を含む記事
Category:数学のエポニム
Category:数学に関する記事
Category:数論の定理