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

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу

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

Әдебиет[өңдеу]