Lucass teoremasi - Lucass theorem - Wikipedia

Ruxsat bering M bilan to'plam bo'ling m elementlarini ajratib oling va uni bo'ling m_men uzunlik tsikllari p^men ning turli xil qiymatlari uchun men. Keyin ushbu tsikllarning har birini alohida aylantirish mumkin, shunday qilib guruh G tsiklik guruhlarning dekartiy mahsuloti bo'lgan C_p^men harakat qiladi M. Shunday qilib, u kichik to'plamlarda ham ishlaydi N hajmi n. Elementlar soni beri G ning kuchi p, uning har qanday orbitasida ham xuddi shunday. Shunday qilib hisoblash uchun ${ displaystyle { tbinom {m} {n}}}$ modul p, biz faqat ushbu guruh harakatlarining qat'iy nuqtalarini hisobga olishimiz kerak. Belgilangan punktlar ushbu pastki to'plamlardir N bu ba'zi tsikllarning birlashmasi. Aniqrog'i induksiya orqali ko'rsatish mumkin k-men, bu N aniq bo'lishi kerak n_men kattalik davrlari p^men. Shunday qilib, tanlov soni N aniq${ displaystyle prod _ {i = 0} ^ {k} { binom {m_ {i}} {n_ {i}}} { pmod {p}}}$.

Ushbu dalil Natan Faynga bog'liq.^[2]

Agar p asosiy va n 1 with bo'lgan tamsayı n ≤ p - 1, keyin binomial koeffitsientning numeratori

${ displaystyle { binom {p} {n}} = { frac {p cdot (p-1) cdots (p-n + 1)} {n cdot (n-1) cdots 1}} }$

ga bo'linadi p lekin maxraji emas. Shuning uchun p ajratadi ${ displaystyle { tbinom {p} {n}}}$. Oddiy ishlab chiqaruvchi funktsiyalar nuqtai nazaridan bu shuni anglatadi

${ displaystyle (1 + X) ^ {p} equiv 1 + X ^ {p} { pmod {p}}.}$

Induksiya bo'yicha davom etadigan bo'lsak, bizda har qanday salbiy bo'lmagan butun son mavjud men bu

${ displaystyle (1 + X) ^ {p ^ {i}} equiv 1 + X ^ {p ^ {i}} { pmod {p}}.}$

Endi ruxsat bering m manfiy bo'lmagan tamsayı bo'lsin va bo'lsin p bosh bo'ling. Yozing m bazada p, Shuning uchun; ... uchun; ... natijasida ${ displaystyle m = sum _ {i = 0} ^ {k} m_ {i} p ^ {i}}$ ba'zi bir salbiy bo'lmagan butun son uchun k va butun sonlar m_men 0 with bilan m_men ≤ p-1. Keyin

${ displaystyle { begin {aligned} sum _ {n = 0} ^ {m} { binom {m} {n}} X ^ {n} & = (1 + X) ^ {m} = prod _ {i = 0} ^ {k} chap ((1 + X) ^ {p ^ {i}} o'ng) ^ {m_ {i}} & equiv prod _ {i = 0} ^ {k} chap (1 + X ^ {p ^ {i}} o'ng) ^ {m_ {i}} = prod _ {i = 0} ^ {k} left ( sum _ {n_ {i } = 0} ^ {m_ {i}} { binom {m_ {i}} {n_ {i}}} X ^ {n_ {i} p ^ {i}} o'ng) & = prod _ {i = 0} ^ {k} chap ( sum _ {n_ {i} = 0} ^ {p-1} { binom {m_ {i}} {n_ {i}}} X ^ {n_ { i} p ^ {i}} o'ng) = sum _ {n = 0} ^ {m} chap ( prod _ {i = 0} ^ {k} { binom {m_ {i}} {n_ {i}}} o'ng) X ^ {n} { pmod {p}}, end {hizalangan}}}$

qaerda yakuniy mahsulot, n_men bo'ladi menbazadagi th raqam p vakili n. Bu Lukas teoremasini tasdiqlaydi.