Теорема Люка

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

Литература

• E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (2): 184–196. DOI:10.2307/2369308. MR1505161. (part 1);
• E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (3): 197–240. DOI:10.2307/2369311. MR1505164. (part 2);
• E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (4): 289–321. DOI:10.2307/2369373. MR1505176. (part 3)
• A. Granville (1997). «Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers». Canadian Mathematical Society Conference Proceedings 20: 253-275. MR1483922.