Теорема Люка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента \binom{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-ричной системе счисления.

В частности, биномиальный коэффициент \binom{m}{n} делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m.

Теорема Люка была впервые получена французским математиком Люка в 1878 году.

Доказательство[править | править вики-текст]

Рассмотрим коэффициент при x^n в многочлене (x+1)^m над конечным полем GF(p). С одной стороны, он попросту равен \binom{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}.

Литература[править | править вики-текст]