szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 17:25 
Użytkownik

Posty: 149
Lokalizacja: obecnie Łódź
Mam takie zadanie, raczej jedno z prostszych, ale niestety jakoś nigdy nie przepadałem za wykazywaniem podzielności ani za liczbami pierwszymi.

Wykazać, że jeżeli n jest potęgą liczby pierwszej p, to {n \choose k} jest podzielne przez p, o ile 1\le k \le n-1.

Nieco się nad tym zastanawiałem i ostatecznie doszedłem do wniosku, że uzasadnienie musi być dość proste. Proszę o weryfikację:

Rozpiszmy:

{p^m \choose k}=\frac{(p^m)!}{k!(p^m-k)!}=\frac{(p^m-k+1)(p^m-k+2)\cdot...\cdot p^m}{1\cdot 2\cdot...\cdot k}

Czy wystarczy stwierdzić, że:

1. W liczniku oraz w mianowniku mamy k kolejnych liczb, więc istnieje bijekcja (powiedzmy f) między czynnikami występującymy w mianowniku a czynnikami występującymi w liczniku, taka że x|f(x) dla każdego argumentu x,

oraz

2. p^m dzieli się tylko przez potęgi p i wynik tego dzielenia zawsze będzie podzielny przez p (bo w mianowniku na pewno nie znajdzie się p^m), co implikuje tezę?

Czy dodatkowo prawdą będzie, że jeżeli k=p^r+s, to p^{m-r}\Big|{p^m \choose k} ?

Edit:
Pospieszyłem się z punktem 1. Weźmy 5,6,7 oraz 1,2,3. Nie istnieje bijekcja, jakiej bym sobie życzył.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 17:52 
Użytkownik

Posty: 12305
Lokalizacja: Presslaw
Rozwiązanie nieelementarne:
mamy v_p(n!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{n}{p^j}\right\rfloor
gdzie dla liczby pierwszej p i liczby całkowitej a mamy v_p(a)=x \Leftrightarrow p^x|a\wedge p^{x+1}\nmid a.
Wobec tego jest
v_p((p^m)!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m}{p^j}\right\rfloor=p^{m-1}+p^{m-2}+\ldots+p+1
a ponadto dla k=1, \ldots p^m-1 mamy
v_p(k!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{k}{p^j}\right\rfloor\le  \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-1}{p^j}\right\rfloor=p^{m-2}+p^{m-1}+\ldots+1
oraz
v_p((p^m-k)!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-k}{p^j}\right\rfloor\le  \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-1}{p^j}\right\rfloor=p^{m-2}+p^{m-1}+\ldots+1,
a ponadto v_p(ab)=v_p(a)v_p(b), więc
v_p((p^m)!)=p^{m-1}+p^{m-2}+\ldots+p+1
oraz (tak naprawdę nierówność jest ostra)
v_p(k!(p^m-k)!}=v_p(k!)v_p((p^m-k)!) \le 2\left( p^{m-2}+p^{m-1}+\ldots+p+1\right)
i pozostaje stwierdzić, że
2\left( p^{m-2}+p^{m-1}+\ldots+p+1\right)=\\=2 \frac{p^{m-1}-1}{p-1} < \frac{p^{m}-1}{p-1}=p^{m-1}+p^{m-2}+\ldots+p+1=v_p\left( (p^m)!\right)
a ta nierówność wynika w sposób oczywisty z warunku p\ge 2.
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 17:53 
Moderator

Posty: 1967
Lokalizacja: Trzebiatów
{p^m \choose k} = {p^m - 1 \choose k - 1} \cdot  \frac{p^{m}}{k} - może bardziej w tym kierunku.
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 18:17 
Użytkownik

Posty: 12305
Lokalizacja: Presslaw
No cóż…
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność przez liczbę pierwszą - zadanie 2  marcel22  4
 podzielność przez liczbę pierwszą  anorian  3
 Dowód podzielności przez 3  asign123  4
 Dla jakich liczb naturalnych..... jest liczbą pierwszą  Arek Maciejak  3
 Oznaczanie wymierności liczb przez komputer  Bialozor6  9
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl