Теорема Люка

Не плутати з теоремою Гауса — Люка.

У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта ${\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 (28 mai). — 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 (28 mai). — 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 (28 mai). — 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 (28 May). — P. 253—275. — MR1483922. з джерела 2 лютого 2017.