suma i podzielność
-
entelechek
- Użytkownik
- Posty: 21
- Rejestracja: 28 cze 2013, o 17:15
- Płeć: Mężczyzna
- Lokalizacja: mOdErAcJaR
- Podziękował: 7 razy
suma i podzielność
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.
-
entelechek
- Użytkownik
- Posty: 21
- Rejestracja: 28 cze 2013, o 17:15
- Płeć: Mężczyzna
- Lokalizacja: mOdErAcJaR
- Podziękował: 7 razy
suma i podzielność
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.
-
Vax
- 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ł: 612 razy
suma i podzielność
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}}\).
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}}\).