数論において リュカの定理（リュカのていり、英: 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 番目の円分多項式を表す。
脚注
外部リンク