Теорема Люка — Википедия

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\displaystyle {\tbinom {m}{n}}}$ на простое число p:

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

где ${\displaystyle m=(m_{k-1},\dots ,m_{0})_{p}}$ и ${\displaystyle n=(n_{k-1},\dots ,n_{0})_{p}}$ — представления чисел m и n в p-ричной системе счисления.

В частности, биномиальный коэффициент ${\displaystyle {\tbinom {m}{n}}}$ делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m.

Теорема была впервые выведена французским математиком Эдуардом Люка в 1878 году.

Рассмотрим коэффициент при ${\displaystyle x^{n}}$ в многочлене ${\displaystyle (x+1)^{m}}$ над конечным полем ${\displaystyle GF(p)}$. С одной стороны, он попросту равен ${\displaystyle {\tbinom {m}{n}}}$. С другой стороны, так как

${\displaystyle (x+1)^{m}=\prod _{i=0}^{k-1}(x+1)^{m_{i}p^{i}}\equiv \prod _{i=0}^{k-1}(x^{p^{i}}+1)^{m_{i}}{\pmod {p}},}$

то, чтобы из последнего произведения получить коэффициент при ${\displaystyle x^{n}}$, нужно из нулевого сомножителя взять коэффициент при ${\displaystyle x^{n_{0}}}$, из первого — коэффициент при ${\displaystyle x^{n_{1}p}}$, a в общем случае из ${\displaystyle i}$-го сомножителя — коэффициент при ${\displaystyle x^{n_{i}p^{i}}}$. Приравнивая коэффициенты, получаем

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

• E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (фр.) // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 2. — P. 184—196. — doi:10.2307/2369308. (part 1);
• E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (фр.) // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 3. — P. 197—240. — doi:10.2307/2369311. (part 2);
• E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (фр.) // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 4. — P. 289—321. — doi:10.2307/2369373. (part 3)
• A. Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (англ.) // Canadian Mathematical Society Conference Proceedings : journal. — 1997. — Vol. 20. — P. 253—275. Архивировано 2 февраля 2017 года.