Теорема Люка

У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта ${\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 (6 novembre). — P. 184—196. — DOI:10.2307/2369308. — MR1505161. (part 1);
• E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 3 (6 novembre). — P. 197—240. — DOI:10.2307/2369311. — MR1505164. (part 2);
• E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 4 (6 novembre). — P. 289—321. — DOI:10.2307/2369373. — MR1505176. (part 3)
• A. Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers // Canadian Mathematical Society Conference Proceedings : journal. — 1997. — Vol. 20 (6 November). — P. 253—275. — MR1483922. Архівовано з джерела 2 лютого 2017.