Теорема Люка

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\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 года.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.