Теорема Люка

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

(mn)i=0k1(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=i=0k1(x+1)mipii=0k1(xpi+1)mi(modp),
  то, чтобы из последнего произведения получить коэффициент при xn, нужно из нулевого сомножителя взять коэффициент при xn0, из первого — коэффициент при xn1p, a в общем случае из i-го сомножителя — коэффициент при xnipi. Приравнивая коэффициенты, получаем

(mn)i=0k1(mini)(modp).