Русская Википедия:Теорема Люка
В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента <math>\tbinom{m}{n}</math> на простое число p:
- <math>\binom{m}{n} \equiv \prod_{i = 0}^{k - 1}{\binom{m_i}{n_i}} \pmod p,</math>
где <math>m=(m_{k-1},\dots,m_0)_p</math> и <math>n=(n_{k-1},\dots,n_0)_p</math> — представления чисел m и n в p-ричной системе счисления.
В частности, биномиальный коэффициент <math>\tbinom{m}{n}</math> делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m.
Теорема была впервые выведена французским математиком Эдуардом Люка в 1878 году.
Доказательство
Рассмотрим коэффициент при <math>x^n</math> в многочлене <math>(x+1)^m</math> над конечным полем <math>GF(p)</math>. С одной стороны, он попросту равен <math>\tbinom{m}{n}</math>. С другой стороны, так как
- <math>(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},</math>
то, чтобы из последнего произведения получить коэффициент при <math>x^n</math>, нужно из нулевого сомножителя взять коэффициент при <math>x^{n_0}</math>, из первого — коэффициент при <math>x^{n_1 p}</math>, a в общем случае из <math>i</math>-го сомножителя — коэффициент при <math>x^{n_i p^i}</math>. Приравнивая коэффициенты, получаем
- <math>\binom{m}{n} \equiv \prod_{i=0}^{k-1}{\binom{m_i}{n_i}} \pmod{p}.</math>
Литература
- Шаблон:Статья (part 1);
- Шаблон:Статья (part 2);
- Шаблон:Статья (part 3)
- Шаблон:Статья
