Теорема Люка

У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта ${\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 (5 février). — 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 février). — 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 février). — 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 February). — P. 253—275. — MR 1483922. Архівовано з джерела 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.