Podzielność różnicy

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Podzielność różnicy

Post autor: mol_ksiazkowy »

Udowodnić, że jeśli \(\displaystyle{ p}\) jest liczba pierwszą to \(\displaystyle{ {n \choose p} - \left\lfloor \frac{n}{p} \right\rfloor}\) jest podzielne przez \(\displaystyle{ p}\)
Ostatnio zmieniony 22 lip 2019, o 16:21 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Podzielność różnicy

Post autor: Premislav »

Dla \(\displaystyle{ p=2}\) teza jest oczywista, dalej przyjmujemy, że \(\displaystyle{ p>2}\). Zapiszmy \(\displaystyle{ n=pk+q, \ k\in \NN, \ q\in\left\{ 0,1,\ldots p-1\right\}}\), wówczas
\(\displaystyle{ {n\choose p}-\left\lfloor \frac n p\right\rfloor={pk+q\choose p}-k}\)
czyli chcemy wykazać, że
\(\displaystyle{ {pk+q\choose p}\equiv k\pmod{p}}\)
a innymi słowy tezę udało się sprowadzić do:
\(\displaystyle{ \frac{(pk+q)(pk+q-1)\ldots (pk+q-p+1)}{p!}\equiv k\pmod{p}\\\frac{(pk+q)(pk+q-1)\ldots (pk+q-p+1)}{p}\equiv k(p-1)!\pmod{p}}\)

Ponieważ zaś
\(\displaystyle{ pk+q, \ pk+q-1, \ldots pk+q-p+1}\) to jest kolejnych \(\displaystyle{ p}\) liczb naturalnych, no i \(\displaystyle{ p}\) jest pierwsza, więc reprezentują one bez powtórzeń wszystkie możliwe reszty z dzielenia przez \(\displaystyle{ p}\) (trywialne; przez sprzeczność, gdyby któraś reszta się powtórzyła, to różnica czynników dających tę samą resztę dzieliłaby się przez \(\displaystyle{ p}\), co jest wykluczone). W szczególności dokładnie jedna z nich, mianowicie
\(\displaystyle{ pk+q-q=pk}\), dzieli się przez \(\displaystyle{ p}\). Możemy więc zapisać:
\(\displaystyle{ \frac{(pk+q)(pk+q-1)\ldots (pk+q-p+1)}{p}=\\=k \prod_{r=0, \ r\neq q}^{p-1}(pk+q-r)}\)
i w tym ostatnim iloczynie reprezentowane są po jednym razie wszystkie niezerowe reszty z dzielenia przez \(\displaystyle{ p}\), stąd \(\displaystyle{ \prod_{r=0, \ r\neq q}^{p-1}(pk+q-r)\equiv (p-1)!\pmod{p}}\)
i
\(\displaystyle{ k\prod_{r=0, \ r\neq q}^{p-1}(pk+q-r)\equiv k(p-1)!\pmod{p}}\)
co należało dowieść. Myślę, że można to bardzo skrócić, cudując jakoś ze współczynnikami dwumianowymi, ale ja nie znam zbyt wielu ich własności…
ODPOWIEDZ