Люк теоремасы

Математикада, Люк теоремасы деп ${\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 жай санына бүтіндей сонда тек сонда, егер n санының кем дегенде бір p-лық цифры m санының сйкес цифрынан асса бөлінеді.

Бұл теореманы алғашқы рет Люка Франсуа Эдуард Анатоль 1878 жылы ашқан.

Дәлелдеу

$GF(p)$ Шекті өрісіндегі $(x+1)^{m}$ көпмүшелігіндегі $x^{n}$ мүшесіндегі коэффициентті қарастырайық. Бір жағынан ол — ${\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}$ коэффициентін, жалпы $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. Үлгі:MR.  (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. Үлгі:MR.  (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. Үлгі:MR.  (part 3)
• A. Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers". Canadian Mathematical Society Conference Proceedings 20: 253-275. Үлгі:MR. http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf.