Теорема Люкаса - Lucass theorem

По поводу теоремы комплексного анализа см. Теорема Гаусса – Лукаса.

В теория чисел, Теорема Лукаса выражает остаток разделения биномиальный коэффициент ${\displaystyle {\tbinom {m}{n}}}$ по простое число п с точки зрения основание п разложения целых чисел м и п.

Теорема Лукаса впервые появилась в 1878 г. в статьях А. Эдуард Лукас.^[1]

Заявление

Для неотрицательных целых чисел м и п и прайм п, следующее отношение конгруэнтности держит:

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

куда

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

и

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

являются базой п расширение м и п соответственно. Это использует соглашение, что ${\displaystyle {\tbinom {m}{n}}=0}$ если м < п.

Доказательства

Есть несколько способов доказать теорему Лукаса.

Комбинаторное доказательство —

Позволять M быть набором с м элементов, и разделите его на м_я циклы длины п^я для различных значений я. Тогда каждый из этих циклов можно вращать отдельно, так что группа грамм которое является декартовым произведением циклических групп C_п^я действует на M. Таким образом, он также действует на подмножества N размера п. Поскольку количество элементов в грамм это сила п, то же самое верно для любой из его орбит. Таким образом, чтобы вычислить ${\displaystyle {\tbinom {m}{n}}}$ по модулю п, нам нужно только рассмотреть неподвижные точки действия этой группы. Неподвижные точки - это подмножества N которые являются объединением некоторых циклов. Точнее, индукцией по k-я, который N должен иметь точно п_я циклы размера п^я. Таким образом, количество вариантов для N точно${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$.

Доказательство на основе производящих функций —

Это доказательство принадлежит Натану Файну.^[2]

Если п это простое и п является целым числом с 1 ≤ п ≤ п - 1, то числитель биномиального коэффициента

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$

делится на п но знаменатель - нет. Следовательно п разделяет ${\displaystyle {\tbinom {p}{n}}}$. В терминах обычных производящих функций это означает, что

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$

Продолжая по индукции, для каждого неотрицательного целого числа я который

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

Теперь позвольте м - целое неотрицательное число, и пусть п быть первым. Написать м в базе п, так что ${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$ для некоторого неотрицательного целого числа k и целые числа м_я с 0 ≤ м_я ≤ п-1. потом

${\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}$

где в конечном продукте, п_я это я-я цифра в базе п представление п. Это доказывает теорему Лукаса.

Последствие

• Биномиальный коэффициент ${\displaystyle {\tbinom {m}{n}}}$ делится на простое число п тогда и только тогда, когда хотя бы одна из базовых п цифры п больше, чем соответствующая цифра м.

Вариации и обобщения

• Теорема Куммера утверждает, что наибольшее целое число k такой, что п^k делит биномиальный коэффициент ${\displaystyle {\tbinom {m}{n}}}$ (или другими словами, оценка биномиального коэффициента относительно простого п) равно количеству несет что происходит, когда п и м − п добавлены в основание п.
• Эндрю Гранвиль дал обобщение теоремы Лукаса на случай п будучи властью премьер-министра.^[3]

• В q-Теорема Лукаса является обобщением q-биномиальные коэффициенты, впервые доказанные Ж. Дезарменьеном.^[4]

Рекомендации

1. • Эдуард Лукас (1878). "Théorie des Fonctions Numériques Simplement Périodiques". Американский журнал математики. 1 (2): 184–196. Дои:10.2307/2369308. JSTOR  2369308. МИСТЕР  1505161. (часть 1);
   • Эдуард Лукас (1878). "Théorie des Fonctions Numériques Simplement Périodiques". Американский журнал математики. 1 (3): 197–240. Дои:10.2307/2369311. JSTOR  2369311. МИСТЕР  1505164. (часть 2);
   • Эдуард Лукас (1878). "Théorie des Fonctions Numériques Simplement Périodiques". Американский журнал математики. 1 (4): 289–321. Дои:10.2307/2369373. JSTOR  2369373. МИСТЕР  1505176. (часть 3)
2. Хорошо, Натан (1947). «Биномиальные коэффициенты по простому модулю». Американский математический ежемесячный журнал. 54: 589–592. Дои:10.2307/2304500.
3. Эндрю Гранвиль (1997). «Арифметические свойства биномиальных коэффициентов I: биномиальные коэффициенты по модулю простых степеней» (PDF). Материалы конференции Канадского математического общества. 20: 253–275. МИСТЕР  1483922. Архивировано из оригинал (PDF) на 02.02.2017.
4. Дезарменин, Жак (март 1982 г.). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". Европейский журнал комбинаторики. 3 (1): 19–28. Дои:10.1016 / S0195-6698 (82) 80005-X.

внешняя ссылка

• Теорема Лукаса в PlanetMath.
• А. Ложье; М. П. Сайкия (2012). «Новое доказательство теоремы Лукаса» (PDF). Заметки по теории чисел и дискретной математике. 18 (4): 1–6. arXiv:1301.4250.
• Р. Мештрович (2014). «Теорема Лукаса: ее обобщения, расширения и приложения (1878-2014)». Препринт. arXiv:/1409.3820.