Теорема Люка

У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта $(\binom{m}{n})$ на просте число p:

(\binom{m}{n}) \equiv \prod_{i = 0}^{k - 1} (\binom{m_{i}}{n_{i}}) (\mod p),

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

Зокрема, біноміальний коефіцієнт $(\binom{m}{n})$ ділиться на просте число p націло тоді й лише тоді, коли хоча б одна p-кова цифра числа n перевищує відповідну цифру числа m.

Теорему вперше вивів 1878 року французький математик Едуард Люка.

Доведення

Розглянемо коефіцієнт при $x^{n}$ у многочлені $(x + 1)^{m}$ над скінченним полем $G F (p)$ . З одного боку, він просто дорівнює $(\binom{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}} (\mod 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}}) (\mod p) .

Див. також

Теорема Волстенголма

Література

E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 2 (5 novembre). — P. 184—196. — DOI:10.2307/2369308. — MR 1505161. (part 1);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 3 (5 novembre). — P. 197—240. — DOI:10.2307/2369311. — MR 1505164. (part 2);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 4 (5 novembre). — P. 289—321. — DOI:10.2307/2369373. — MR 1505176. (part 3)
A. Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers // Canadian Mathematical Society Conference Proceedings : journal. — 1997. — Vol. 20 (5 November). — P. 253—275. — MR 1483922. Архівовано з джерела 2 лютого 2017.