声明 非負整数m とn および素数p に対して、次の合同関係 が成り立つ。
（ m n ） ≡ ∏ 私 = 0 k （ m 私 n 私 ） （ モジュール p ） 、 {\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},} どこ
m = m k p k + m k − 1 p k − 1 + ⋯ + m 1 p + m 0 、 {\displaystyle 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 + ⋯ + n 1 p + n 0 {\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}} はそれぞれm とn のp 基数展開 である。これは以下の慣例を用いる。（ m n ） = 0 {\displaystyle {\tbinom {m}{n}}=0} m < n の 場合。
証明 ルーカスの定理を証明する方法はいくつかある。
群作用を用いた組み合わせ論的証明 M を m 個の要素を持つ集合とし、i のさまざまな値に対して、長さ p i の m i 個のサイクルに任意に分割します。 すると、これら の サイクルの それぞれを巡回群 C p i デカルト積 である群 Gが M に作用します。したがって、 M のn 個の要素を持つ部分集合N の集合にも作用し、その数は（ m n ） {\displaystyle {\tbinom {m}{n}}}
G の要素数はp のべき乗であるため、軌道安定化定理 により、その任意の軌道 についても同じことが成り立ちます。したがって、（ m n ） {\displaystyle {\tbinom {m}{n}}} は、軌道のサイズが 1 である集合N の数、すなわち群作用の 不動点 の数と法p に関して合同である。
すべてのサイクルは群G によって独立に回転できるため、作用の不動点は、いくつかのサイクルの和集合である部分集合N です。これは、整数nが基数 p で一意の表現を持つのと同じ理由で、 N は 各iに対してサイズ p i n i 個でなければならないことを意味します。したがって、 N の選択肢の数はちょうど ∏ 私 = 0 k （ m 私 n 私 ） {\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}}
生成関数に基づく証明 この証明はネイサン・ファインによるものである。[ 2 ]
p が素数でnが 1≤n≤p - 1を 満たす整数である場合、二項係数の分子は
（ p n ） = p ⋅ （ p − 1 ） ⋯ （ p − n + 1 ） n ⋅ （ n − 1 ） ⋯ 1 {\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}} はp で割り切れるが、分母は割り切れない。したがってp は を割り切る。（ p n ） {\displaystyle {\tbinom {p}{n}}} 二項定理 により、これは次のことを意味します。
（ 1 + X ） p ≡ 1 + X p （ モジュール p ） 。 {\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.} 帰納法 を続けると、すべての非負整数i に対して、
（ 1 + X ） p 私 ≡ 1 + X p 私 （ モジュール p ） 。 {\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.} ここで、m を 非負整数とし、p を 素数とする。mを p を基数として次のように表す。m = ∑ 私 = 0 k m 私 p 私 {\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}} k と、 0 ≤ m i p − 1を満たす整数m iに対して、
∑ n = 0 m （ m n ） X n = （ 1 + X ） m = ∏ 私 = 0 k （ （ 1 + X ） p 私 ） m 私 ≡ ∏ 私 = 0 k （ 1 + X p 私 ） m 私 = ∏ 私 = 0 k （ ∑ j 私 = 0 m 私 （ m 私 j 私 ） X j 私 p 私 ） = ∑ n = 0 m （ ∏ 私 = 0 k （ m 私 n 私 ） ） X n （ モジュール p ） 。 {\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)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}}.\end{aligned}}} 最後の等式では分配法則と、 nの p 基数表現が一意であるという事実を利用します。ここでn i はnの p 基数表現におけるi 番目の桁です。最初の和と最後の和におけるX n
パスカルの三角形。奇数次の二項係数を黒色で示す。
結果 ルーカスの定理の帰結の一つは、二項係数が（ m n ） {\displaystyle {\tbinom {m}{n}}} pで割り切れるのは、 nの p 基数表現の少なくとも 1 つの桁がm の対応する桁よりも大きい場合に限る 。特に、（ m n ） {\displaystyle {\tbinom {m}{n}}} n が奇数 となるのは、 n の二進展開 における 1 の位置が、m の二進展開における 1 の位置の部分集合である場合に限る。これにより、右図に示すシェルピンスキーの三角形 に似た、パスカルの三角形 における奇数の特異な分布が生じる。
非素数の法 ルーカスの定理は、次の場合に剰余の式を与えるように一般化できる。（ m n ） {\displaystyle {\tbinom {m}{n}}} 素数のべき乗 p k
法が素数pの二乗である場合、0 ≤ s ≤ r ≤ p − 1、a ≥ 0、b ≥ 0のすべてに対して、次の合同関係が成り立つ。
（ p 1 + r p b + s ） ≡ （ 1 b ） （ r s ） （ 1 + p 1 （ H r − H r − s ） + p b （ H r − s − H s ） ） （ モジュール p 2 ） 、 {\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{rs})+pb(H_{rs}-H_{s})){\pmod {p^{2}}},} どこH n = 1 + 1 2 + 1 3 + ⋯ + 1 n {\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}} はn 番目の調和数 です。[ 3 ] p k [ 4 ]および Granville (1997) [ 5 ]
クンマーの定理は、 p k が 整数 kが存在すると主張している。 （ m n ） {\displaystyle {\tbinom {m}{n}}} p に関する二項係数の評価）は、 底 p でn とm − n を加えたときに発生する繰り上がり の数に等しい。
参考文献 ↑ エドゥアール・ルーカス (1878)。 "Théorie des Fonctions Numériques Simplement Périodiques"。アメリカ数学ジャーナル 1 (2): 184–196 。土井 : 10.2307/2369308。JSTOR 2369308。MR 1505161。 エドゥアール・ルーカス (1878)。 "Théorie des Fonctions Numériques Simplement Périodiques"。アメリカ数学ジャーナル 1 (3): 197–240 .土井 : 10.2307/2369311。JSTOR 2369311。MR 1505164。 エドゥアール・ルーカス (1878)。 "Théorie des Fonctions Numériques Simplement Périodiques"。アメリカ数学ジャーナル 1 (4): 289–321 .土井 : 10.2307/2369373。JSTOR 2369373。MR 1505176。 ↑ Fine, Nathan (1947). "素数を法とする二項係数". American Mathematical Monthly . 54 (10): 589–592 . doi : 10.2307/2304500 . JSTOR 2304500 . ↑ Rowland, Eric (2022). "Lucas' theorem modulo p 2 ". American Mathematical Monthly . 129 (9): 846– 855. arXiv : 2006.11701v3 . doi : 10.1080/00029890.2022.2038004 . ↑ Kenneth S. Davis、William A. Webb (1990)。「素数 の べき乗に関するルーカスの定理」。European Journal of Combinatorics。11 (3): 229–233。doi : 10.1016 / S0195-6698(13)80122-9 。 ↑ Andrew Granville (1997). "二項係数の算術的性質 I: 素数のべき乗を法とする二項係数" (PDF) . Canadian Mathematical Society Conference Proceedings . 20 : 253– 275. MR 1483922 . 2017-02-02 に オリジナル (PDF) からアーカイブ済み。 ↑ デサルメニアン、ジャック (1982 年 3 月)。 "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler"。 欧州組合せ論ジャーナル 。 3 (1): 19–28 。 土井 : 10.1016/S0195-6698(82)80005-X 。
外部リンク PlanetMath の ルーカスの定理。 A. Laugier; MP Saikia (2012). 「ルーカスの定理の新しい証明」(PDF) . Notes on Number Theory and Discrete Mathematics . 18 (4): 1– 6. arXiv : 1301.4250 . R. Meštrović (2014). "Lucasの定理：その一般化、拡張、応用（1878–2014）". arXiv : 1409.3820 [ math.NT ]. 
