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

Математикада, Люк теоремасы деп $\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.