Теорема Лукаса

Информацию о теореме комплексного анализа см. в теореме Гаусса – Лукаса .

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

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

Заявление

Для неотрицательных целых чисел m и n и простого числа p выполняется следующее соотношение сравнения :

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

где

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

и

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

являются по основанию p разложениями m и n соответственно. При этом используется соглашение, согласно которому ${\tbinom {m}{n}}=0$ если м < п .

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

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

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

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

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

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

Если p — простое число, а n — целое число с 1 ≤ n ≤ p − 1, то числитель биномиального коэффициента

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

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

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

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

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

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

${\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 _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{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}}$

поскольку представление n в базе p уникально и в конечном продукте n _i — это i-я цифра в по основанию p представлении n . Это доказывает теорему Лукаса.

Последствия

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

Непростые формы

Теорему Лукаса можно обобщить, чтобы дать выражение для остатка, когда ${\tbinom {m}{n}}$ делится на степень простого числа p ^к . Однако формулы усложняются.

Если по модулю является квадратом простого числа p , следующее соотношение сравнения справедливо для всех 0 ≤ s ≤ r ≤ p − 1, a ≥ 0 и b ≥ 0.

${\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},$

где $H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}$ это н ^й номер гармоники .

Обобщения теоремы Люка для высших степеней простых чисел p ^к также даны Дэвисом и Уэббом (1990). и Гранвилл (1997).

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

• Теорема Куммера утверждает, что наибольшее целое число k такое, что p ^к делит биномиальный коэффициент ${\tbinom {m}{n}}$ (или, другими словами, оценка биномиального коэффициента по отношению к простому числу p ) равна количеству переносов , которые возникают при n и m − n добавлении в базе p .

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

Внешние ссылки

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