Теорема Люка

Не следует путать с Теорема Гаусса — Люка.

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

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

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

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

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

Доказательство

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

$(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}},$

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

${\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 года.