ルーカスの定理

ウィキペディア

ルーカスの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/10/08 18:11 UTC 版)

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

リュカの定理は1878年にÉdouard Lucas.の論文にて初めて登場した。

主張

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

${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},$

ここで、

はそれぞれm,nのp進展開である。また、m < nの時は ${\tbinom {m}{n}}=0$と定める。

$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$

$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$

証明

母関数による証明 — この証明はNathan Fineによるものである。

p を素数、n を 1 ≤ n ≤ p − 1 を満たす整数とすると、二項係数

${\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}$

の分子は p で割り切れるが、分母は p で割り切れない。したがって、p は ${\tbinom {p}{n}}$ を割る。これは

$(1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.$

を意味する。帰納的に、任意の非負整数 i に対して

$(1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.$

が成り立つ。

次に m を非負整数、p を素数とする。m を p 進法で表すと、ある非負整数 k および 0 ≤ m_i ≤ p − 1 を満たす整数 m_i に対して $m=\sum _{i=0}^{k}m_{i}p^{i}$ と書ける。このとき

${\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}\\&=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}}.\end{aligned}}$

となる。これによりリュカの定理が証明される。

結果

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

非素数法への拡張

リュカの定理は、二項係数 ${\tbinom {m}{n}}$ を素数冪 p^k で割った余りを求める形に一般化することができる。しかし、その場合の公式はより複雑になる。

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

${\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},$

ここで $H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}$ は n-番目の 調和数 である。より高い素冪 p^k に対するリュカの定理の一般化は Davis と Webb (1990) および Granville (1997) によって与えられている。

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

q二項係数への拡張

リュカの定理には q二項係数 への一般化が存在する。整数 a, b, r, s, k が 0 ≤ b, s < k を満たすとき、以下の合同式が成立する： $${\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}\equiv {\binom {a}{r}}{\begin{bmatrix}b\\s\end{bmatrix}}_{q}\mod {\Phi _{k}},$$ ここで、 ${\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}$ および ${\begin{bmatrix}b\\s\end{bmatrix}}_{q}$は q二項係数、 ${\binom {a}{r}}$は通常の二項係数、 $\Phi _{k}(q)$は変数 q に対する k 番目の円分多項式を表す。

外部リンク

• Lucas's Theorem - PlanetMath.（英語）
• A. Laugier; M. P. Saikia (2012). “A new proof of Lucas' Theorem”. Notes on Number Theory and Discrete Mathematics 18 (4): 1–6. arXiv:1301.4250. http://nntdm.net/papers/nntdm-18/NNTDM-18-4-01-06.pdf. 
• R. Meštrović. “Lucas' theorem: its generalizations, extensions and applications (1878–2014)”. arXiv:1409.3820 [math.NT].