Теорема Люка

Шаблон:Не плутати У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта $(\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) .

Див. також

Теорема Волстенголма

Література

Теорема Люка

Доведення

Див. також

Література

Навігаційне меню

Пошук