Теорема Люка

---

В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента ${\displaystyle {\tbinom {m}{n}}}$ на простое число p:

где ${\displaystyle m=(m_{k-1},\dots ,m_{0})_{p}}$ и ${\displaystyle n=(n_{k-1},\dots ,n_{0})_{p}}$ — представления чисел m и n в p-ричной системе счисления.

В частности, биномиальный коэффициент ${\displaystyle {\tbinom {m}{n}}}$ делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m.

Рассмотрим коэффициент при ${\displaystyle x^{n}}$ в многочлене ${\displaystyle (x+1)^{m}}$ над конечным полем ${\displaystyle GF(p)}$. С одной стороны, он попросту равен ${\displaystyle {\tbinom {m}{n}}}$. С другой стороны, так как

---