Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Теорема Люка



В математики, теоремою Люка називається наступне твердження про залишок від ділення біноміального коефіцієнта \ 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 над кінцевим полем 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} \ 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}.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Послідовність Люка
Кришка каналізаційного люка
Врен-Люка, Дені
Люка, Франсуа Едуард Анатоль
H-теорема
Теорема
Пі-теорема
Теорема Тебо
Теорема Фейєрбаха
© Усі права захищені
написати до нас
Рейтинг@Mail.ru