Теорема Люка

Перейти к навигации Перейти к поиску

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\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. — P. 184—196. — doi:10.2307/2369308. (part 1);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (фр.) // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 3. — P. 197—240. — doi:10.2307/2369311. (part 2);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (фр.) // American Journal of Mathematics : magazine. — 1878. — Vol. 1, n^o 4. — P. 289—321. — doi:10.2307/2369373. (part 3)
A. Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (англ.) // Canadian Mathematical Society Conference Proceedings : journal. — 1997. — Vol. 20. — P. 253—275. Архивировано 2 февраля 2017 года.

Похожие исследовательские статьи

Сравне́ние двух целых чисел по мо́дулю натурального числа $\text{[math]}$ — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на $\text{[math]}$ один и тот же остаток. Любое целое число при делении на $\text{[math]}$ даёт один из $\text{[math]}$ возможных остатков: число от 0 до $\text{[math]}$ ; это значит, что все целые числа можно разделить на $\text{[math]}$ групп, каждая из которых отвечает определённому остатку от деления на $\text{[math]}$ . Эти группы называются классами вычетов по модулю $\text{[math]}$ , а содержащиеся в них целые числа — вычетами по модулю $\text{[math]}$ .

Те́ст Люка́ — Ле́мера — полиномиальный, детерминированный и безусловный тест простоты для чисел Мерсенна. Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году.

Биномиа́льный коэффицие́нт — коэффициент перед членом разложения бинома Ньютона $\text{[math]}$ по степеням $\text{[math]}$ . Коэффициент при $\text{[math]}$ обозначается $\text{[math]}$ или $\text{[math]}$ и читается «биномиальный коэффициент из $\text{[math]}$ по $\text{[math]}$ » :

\text{[math]}

Целое число $\text{[math]}$ называется квадратичным вычетом по модулю $\text{[math]}$ , если разрешимо сравнение:

\text{[math]}

Китайская теорема об остатках — несколько связанных утверждений о решении линейной системы сравнений.

Алгоритм Полига — Хеллмана — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностей алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время.

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом в 1979 году. Леонард Макс Адлеман — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Если $\text{[math]}$ простое число, то формула $\text{[math]}$ делится на $\text{[math]}$ .

Число Белла — число всех неупорядоченных разбиений $\text{[math]}$ -элементного множества, обозначаемое $\text{[math]}$ , при этом по определению полагают $\text{[math]}$ . Названы в честь Эрика Белла, который изучил их в 1930-е годы.

Число Кармайкла — составное число $\text{[math]}$ , которое удовлетворяет сравнению $\text{[math]}$ для всех целых $\text{[math]}$ , взаимно простых с $\text{[math]}$ , другими словами — псевдопростое число по каждому основанию $\text{[math]}$ , взаимно простому с $\text{[math]}$ . Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.

Критерий Поклингтона — детерминированный тест на простоту, разработанный Генри Поклингтоном и Дерриком Генри Лехмером. Критерий Поклингтона позволяет определять, является ли данное число простым.

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел $\text{[math]}$ и $\text{[math]}$ таких, что $\text{[math]}$ и $\text{[math]}$

Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 1967 году. Может использоваться также для проверки неприводимости многочленов над конечными полями. Основная идея алгоритма заключается в возможности представления исходного многочлена в виде произведения наибольших общих делителей самого многочлена и некоторых многочленов, которые с точностью до свободного члена являются $\text{[math]}$ -разлагающими.

NTRUEncrypt — это криптографическая система с открытым ключом, ранее называвшаяся NTRU.

Теорема Вольстенхольма утверждает, что для любого простого числа $\text{[math]}$ выполняется сравнение

\text{[math]}

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого $\text{[math]}$ .

Функция Кармайкла — теоретико-числовая функция, обозначаемая $\text{[math]}$ , равная наименьшему показателю $\text{[math]}$ такому, что

\text{[math]}

Алгори́тм Тоне́лли — Ше́нкса относится к модулярной арифметике и используется для решения сравнения

\text{[math]}

Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида

\text{[math]}

Лемма Гензеля — результат в модульной арифметике, утверждающий, что если алгебраическое уравнение имеет простой корень по модулю простого числа $\text{[math]}$ , то данному корню однозначно соответствует корень того же уравнения, взятого по модулю $\text{[math]}$ , который может быть найден итеративным подъёмом по степеням $\text{[math]}$ . Названа в честь Курта Гензеля. В более общем случае, лемма Гензеля также используется как обоснование для аналогов метода Ньютона в полных коммутативных кольцах.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.