Loading [MathJax]/jax/output/HTML-CSS/jax.js

Теорема Люка

 В математике теоремой Люка называется следующее утверждение обостатке от деления биномиального коэффициента (mn) на простоечисло p:

(mn)k1i=0(mini)(modp),
 где m=(mk1,,m0)p и n=(nk1,,n0)p —представления чисел m и n в p-ричной системесчисления.
 В частности, биномиальный коэффициент (mn) делится на простоечисло p нацело тогда и только тогда, когда хотя бы однаp-ричная цифра числа n превышает соответствующую цифручисла m.
 Теорема была впервые выведена французским математиком Эдуардом Люка в1878 году.

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


 Рассмотрим коэффициент при xn в многочлене (x+1)m над конечнымполем GF(p). С одной стороны, он попросту равен (mn). Сдругой стороны, так как

(x+1)m=k1i=0(x+1)mipik1i=0(xpi+1)mi(modp),
 то, чтобы из последнего произведения получить коэффициент при xn,нужно из нулевого сомножителя взять коэффициент при xn0, изпервого — коэффициент при xn1p, a в общем случае изi-го сомножителя — коэффициент при xnipi. Приравниваякоэффициенты, получаем

(mn)k1i=0(mini)(modp).