В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\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 : . (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 : . (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 : . (part 3)
• A. Granville. (англ.) // Canadian Mathematical Society Conference Proceedings : journal. — 1997. — Vol. 20 . — P. 253—275 . 2 февраля 2017 года.