WikiSort.ru - Не сортированное

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\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 (1878). “Théorie des Fonctions Numériques Simplement Périodiques”. American Journal of Mathematics. 1 (2): 184—196. DOI:10.2307/2369308. MR: 1505161. Символ переноса строки в |author= на позиции №38 (справка) (part 1);
• E. Lucas (1878). “Théorie des Fonctions Numériques Simplement Périodiques”. American Journal of Mathematics. 1 (3): 197—240. DOI:10.2307/2369311. MR: 1505164. Символ переноса строки в |author= на позиции №38 (справка) (part 2);
• E. Lucas (1878). “Théorie des Fonctions Numériques Simplement Périodiques”. American Journal of Mathematics. 1 (4): 289—321. DOI:10.2307/2369373. MR: 1505176. Символ переноса строки в |author= на позиции №38 (справка) (part 3)
• A. Granville (1997). “Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers” (PDF). Canadian Mathematical Society Conference Proceedings. 20: 253–275. MR: 1483922. Архивировано из оригинала (PDF) 2017-02-02. Символ переноса строки в |author= на позиции №38 (справка)