Lucassova věta - Lucass theorem - Wikipedia

Nechat M být set s m prvky a rozdělit jej na m_i cykly délky pⁱ pro různé hodnoty i. Pak lze každý z těchto cyklů otáčet samostatně, takže se jedná o skupinu G což je kartézský součin cyklických skupin C_pⁱ jedná M. Působí tedy také na podmnožiny N velikosti n. Od počtu prvků v G je síla p, totéž platí o všech jeho drahách. Tedy za účelem výpočtu ${ displaystyle { tbinom {m} {n}}}$ modulo p, musíme vzít v úvahu pouze pevné body této skupinové akce. Pevné body jsou tyto podmnožiny N které jsou spojením některých cyklů. Přesněji lze ukázat indukcí na k-i, že N musí mít přesně n_i cykly velikosti pⁱ. Tedy počet možností pro N je přesně${ displaystyle prod _ {i = 0} ^ {k} { binom {m_ {i}} {n_ {i}}} { pmod {p}}}$.

Tento důkaz má na svědomí Nathan Fine.^[2]

Li p je hlavní a n je celé číslo s 1 ≤ n ≤ p - 1, pak čitatel binomického koeficientu

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

je dělitelné p ale jmenovatel není. Proto p rozděluje ${ displaystyle { tbinom {p} {n}}}$. Z hlediska běžných generujících funkcí to znamená

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

Pokračujeme indukcí a máme pro každé nezáporné celé číslo i že

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

Tak teď m být nezáporné celé číslo a nechat p být předseda. Psát si m v základně p, aby ${ displaystyle m = sum _ {i = 0} ^ {k} m_ {i} p ^ {i}}$ pro nějaké nezáporné celé číslo k a celá čísla m_i s 0 ≤ m_i ≤ p-1. Pak

${ displaystyle { begin {aligned} sum _ {n = 0} ^ {m} { binom {m} {n}} X ^ {n} & = (1 + X) ^ {m} = prod _ {i = 0} ^ {k} left ((1 + X) ^ {p ^ {i}} right) ^ {m_ {i}} & equiv prod _ {i = 0} ^ {k} left (1 + X ^ {p ^ {i}} right) ^ {m_ {i}} = prod _ {i = 0} ^ {k} left ( sum _ {n_ {i } = 0} ^ {m_ {i}} { binom {m_ {i}} {n_ {i}}} X ^ {n_ {i} p ^ {i}} right) & = prod _ {i = 0} ^ {k} left ( sum _ {n_ {i} = 0} ^ {p-1} { binom {m_ {i}} {n_ {i}}} X ^ {n_ { i} p ^ {i}} right) = sum _ {n = 0} ^ {m} left ( prod _ {i = 0} ^ {k} { binom {m_ {i}} {n_ {i}}} vpravo) X ^ {n} { pmod {p}}, end {zarovnáno}}}$

kde v konečném produktu, n_i je ith číslice v základně p zastoupení n. To dokazuje Lucasovu větu.