リュカの定理

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

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

主張

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

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

ここで、

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

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

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

証明

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

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

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

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

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

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

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

が成り立つ。

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

${\displaystyle {\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}}}$ 

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

結果

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

非素数法への拡張

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

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

${\displaystyle {\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}}},}$ 

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

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

q二項係数への拡張

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

脚注

1. ^ Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500
2. ^ Fine, Nathan (1947). “Binomial coefficients modulo a prime”. American Mathematical Monthly 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500. 
3. ^ Rowland, Eric (2022). “Lucas' theorem modulo p²”. American Mathematical Monthly 129 (9): 846–855. arXiv:2006.11701v3. doi:10.1080/00029890.2022.2038004. 
4. ^ Kenneth S. Davis, William A. Webb (1990). “Lucas' Theorem for Prime Powers”. European Journal of Combinatorics 11 (3): 229–233. doi:10.1016/S0195-6698(13)80122-9. 
5. ^ Andrew Granville (1997). “Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers”. Canadian Mathematical Society Conference Proceedings 20: 253–275. MR1483922. http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf. 
6. ^ Désarménien, Jacques (March 1982). “Un Analogue des Congruences de Kummer pour les q-nombres d'Euler”. European Journal of Combinatorics 3 (1): 19–28. doi:10.1016/S0195-6698(82)80005-X. 

外部リンク

• 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].