Теорема Люка

Шаблон:Не путать

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента $(\binom{m}{n})$ на простое число p:

(\binom{m}{n}) \equiv \prod_{i = 0}^{k - 1} (\binom{m_{i}}{n_{i}}) (\mod 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}$ над конечным полем $G F (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}} (\mod 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}}) (\mod p) .

Литература

Теорема Люка

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

Литература

Навигация

Поиск