Twierdzenie Lucasa

W $teorii$ liczb twierdzenie Lucasa wyraża resztę z dzielenia współczynnika przez liczbę pierwszą p pod względem p liczb całkowitych m rz .

Twierdzenie Lucasa po raz pierwszy pojawiło się w 1878 roku w artykułach Édouarda Lucasa .

Oświadczenie

Dla nieujemnych liczb całkowitych m i n oraz liczby pierwszej p zachodzi następująca relacja kongruencji :

{\ Displaystyle {\ binom {m} {n}} \ równoważnik \ prod _ {i = 0} ^ {k} {\ binom {m_{i}}{n_{i}}}{\pmod {p}},}

Gdzie

{\ Displaystyle m = m_ {k} p ^ {k} + m_ {k-1} p ^ {k- 1}+\cdots +m_{1}p+m_{0},}

I

{\ Displaystyle n = n_ {k} p ^ {k} + n_ {k-1} p ^ {k-1 }+\cdots +n_{1}p+n_{0}}

rozszerzeniami bazowymi p odpowiednio m i n . Wykorzystuje to konwencję, że ${\ displaystyle {\ tbinom {m} {n}} = 0}$ if m < n .

Dowody

Istnieje kilka sposobów udowodnienia twierdzenia Lucasa.

Dowód kombinatoryczny

Niech M będzie zbiorem o pi ^m elementach i podziel go na m _i cykli o długości dla różnych wartości i . Wtedy Cpi _{każdy ^z} tych cykli można obrócić oddzielnie, tak że grupa G będąca iloczynem kartezjańskim grup cyklicznych działa na M . W ten sposób działa również na podzbiory N o rozmiarze n . Ponieważ liczba elementów w G jest potęgą p , to samo dotyczy każdej z jego orbit. Zatem $,$ aby obliczyć , musimy wziąć punkty tej akcji grupowej. Punkty stałe to te podzbiory N , które są sumą niektórych cykli. Dokładniej można pokazać przez indukcję po k - i , że N musi mieć dokładnie n _i cykli o ^rozmiarze pi . Zatem liczba wyborów dla N jest dokładnie taka sama ${\ Displaystyle \ prod _ {i = 0} ^ {k} {\ binom {m_ {i}}} {n_ {i}}} {\ pmod {p }}}$ .

Dowód oparty na funkcjach generujących

Ten dowód pochodzi od Nathana Fine'a.

Jeśli p jest liczbą pierwszą, a n jest liczbą całkowitą z 1 ≤ n ≤ p - 1, to licznik współczynnika dwumianu

{\ Displaystyle {\ binom {p} {n}} = {\ Frac {p \ cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}

jest podzielna przez p , ale mianownik nie. Stąd p dzieli ${\ Displaystyle {\ tbinom {p} {n}}}$ . Pod względem zwykłych funkcji generujących oznacza to, że

{\ Displaystyle (1 + X) ^ {p} \ równoważnik 1 + X ^ {p} {\ pmod {p}}.}

Kontynuując przez indukcję, mamy dla każdej nieujemnej liczby całkowitej i to

{\ Displaystyle (1 + X) ^ {p ^ {i}} \ równoważnik 1 + X ^ {p ^ {i}} {\ pmod {p}}.}

Niech m będzie nieujemną liczbą całkowitą i niech p będzie liczbą pierwszą. Napisz m w podstawie p , tak że ${\ Displaystyle m = \ suma _ {i = 0} ^ {k} m_ {i} p ^ {i}}$ dla pewnej nieujemnej liczby całkowitej k oraz liczby całkowite m _i gdzie 0 ≤ m _i ≤ p -1. Następnie

{\ Displaystyle {\ rozpocząć {wyrównane} \ suma _ {n = 0} ^ {m} {\ binom {m} {n}} X ^ {n} &=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}} \\&\równoważnik \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0} ^{k}\left(\suma _{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)=\suma _{n=0}^{m}\left(\prod _{i=0}^ {k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}

gdzie w produkcie końcowym n _i jest i- tą cyfrą w podstawowej p reprezentacji n . To dowodzi twierdzenia Lucasa.

Konsekwencje

Dwumianowy współczynnik ${\ Displaystyle {\ tbinom {m} {n}}}$ jest podzielny przez liczbę pierwszą p wtedy i tylko wtedy, gdy co najmniej jedna z podstawowych cyfr p n jest większa niż odpowiadająca jej cyfra m .
W szczególności jest nieparzyste wtedy i tylko wtedy $,$ cyfry binarne ( bity w rozwinięciu n są bitów m .

Wariacje i uogólnienia

$p$ Kummera , że największa liczba całkowita k taka, że k ^dzieli współczynnik dwumianowy (lub innymi słowy, wycena w odniesieniu do liczba pierwsza p ) jest równa liczbie przeniesień , które występują, gdy n i m - n są dodawane do podstawy p .

Uogólnienia twierdzenia Lucasa na przypadek p będącego potęgą pierwszą podają Davis i Webb (1990) oraz Granville (1997).

Twierdzenie q -Lucasa jest uogólnieniem współczynników q -dwumianowych, które po raz pierwszy udowodnił J. Désarménien.

Linki zewnętrzne

Twierdzenie Lucasa w PlanetMath .
A. Laugiera; poseł Saikia (2012). „Nowy dowód twierdzenia Lucasa” (PDF) . Uwagi na temat teorii liczb i matematyki dyskretnej . 18 (4): 1–6. ar Xiv : 1301.4250 .
R. Meštrović (2014). „Twierdzenie Lucasa: jego uogólnienia, rozszerzenia i zastosowania (1878–2014)”. arXiv : 1409,3820 [ matematyka.NT ].