suma i podzielność

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
entelechek
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 28 cze 2013, o 17:15
Płeć: Mężczyzna
Lokalizacja: mOdErAcJaR
Podziękował: 7 razy

suma i podzielność

Post autor: entelechek » 25 lip 2013, o 12:46

Udowodnij, że \(\displaystyle{ 2 \sum_{b=1}^{\frac{n^{k}}{2}-1} b^{m}+\frac{n^{k}}{2}}\) dla dowolnych \(\displaystyle{ k \ge 2}\) oraz \(\displaystyle{ m}\) parzystego i \(\displaystyle{ n}\) parzystego jest podzielne przez \(\displaystyle{ n^{k-1}}\).
Ostatnio zmieniony 26 lip 2013, o 09:21 przez entelechek, łącznie zmieniany 4 razy.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

robertm19
Użytkownik
Użytkownik
Posty: 1847
Rejestracja: 8 lip 2008, o 21:16
Płeć: Mężczyzna
Lokalizacja: Staszów/Warszawa
Podziękował: 7 razy
Pomógł: 378 razy

suma i podzielność

Post autor: robertm19 » 25 lip 2013, o 12:55

Jest błąd w zapisie. Masz sumowanie po \(\displaystyle{ k}\) i od 1 do czegoś co zależy od \(\displaystyle{ k}\).

entelechek
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 28 cze 2013, o 17:15
Płeć: Mężczyzna
Lokalizacja: mOdErAcJaR
Podziękował: 7 razy

suma i podzielność

Post autor: entelechek » 26 lip 2013, o 09:24

Zadanie do bazy danych, jeśli ktoś chce, może je rozwiązać... Ah, zapomniałem dodać, że byłoby to bardzo mile widziane. Nagrody gwarantowane.

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

suma i podzielność

Post autor: Vax » 26 lip 2013, o 11:32

Piękne zadanie Na początku zauważmy, że \(\displaystyle{ n^{k-1} \mid \frac{n^k}{2}}\), więc wystarczy pokazać \(\displaystyle{ 2\sum_{b=1}^{\frac{n^k}{2}-1}b^m \equiv 0\pmod{n^{k-1}}}\).

Jednak skoro \(\displaystyle{ 2 \mid m}\) oraz \(\displaystyle{ n^{k-1} \mid n^k}\), to dla dowolnego \(\displaystyle{ t}\) mamy \(\displaystyle{ t^m \equiv (n^k-t)^m \pmod{n^{k-1}}}\), więc nasza suma \(\displaystyle{ \pmod{n^{k-1}}}\) jest równa:

\(\displaystyle{ 2\sum_{b=1}^{\frac{n^k}{2}-1}b^m \equiv \sum_{b=1}^{n^k-1}b^m \pmod{n^{k-1}}}\)

Rozbijamy naszą sumę dostając (odpowiednie wielokrotności \(\displaystyle{ n^{k-1}}\) od razu zerujemy, tj np po \(\displaystyle{ n^{k-1}-1}\) mamy \(\displaystyle{ n^{k-1}+1}\) itd):

\(\displaystyle{ \sum_{b=1}^{n^{k-1}-1}b^m + \sum_{b=n^{k-1}+1}^{2n^{k-1}-1}b^m + \sum_{b=2n^{k-1}+1}^{3n^{k-1}-1}b^m+ ... + \sum_{b=(n-1)n^{k-1}+1}^{n^k-1}b^m \pmod{n^{k-1}}}\)

Jednak jak łatwo zauważyć każda ta suma przystaje do \(\displaystyle{ \sum_{b=1}^{n^{k-1}-1}b^m \pmod{n^{k-1}}}\), więc całe wyrażenie jest równe:

\(\displaystyle{ n\sum_{b=1}^{n^{k-1}-1}b^m \pmod{n^{k-1}}}\)

Chcemy, żeby to było równe \(\displaystyle{ 0}\), co jest równoważne pokazaniu \(\displaystyle{ \sum_{b=1}^{n^{k-1}-1}b^m \equiv 0 \pmod{n^{k-2}}}\)

Jak łatwo zauważyć jest to ta sama suma co na początku jednak ze zmniejszoną wartością \(\displaystyle{ k}\) o jeden. Możemy więc powtarzać ten proces wiele razy, ostatecznie dostając do pokazania \(\displaystyle{ \sum_{b=1}^{n-1}b^m \equiv 0\pmod{1}}\)

Co jest prawdą \(\displaystyle{ \mathbb{QED}}\).

ODPOWIEDZ