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

---

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

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

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

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

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

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

---