Witam.
Znaleźć resztę z dzielenia liczby \(\displaystyle{ 10^{3^{n}} + 10^{3^{n} \cdot 2} + 10^{3^{n} \cdot 3} + \ldots + 10^{3^{n} \cdot n} \ (n \in \mathbb{N})}\) przez \(\displaystyle{ 3^{n+1}}\).
Od siebie tylko napiszę, że wychodzą mi głupoty, np. ułamkowe reszty...
Pozdrawiam, P.
Reszta z dzielenia, potęgi, suma
Reszta z dzielenia, potęgi, suma
Podpowiedź:
\(\displaystyle{ 10^{\varphi(3^{n+1})}=10^{2\;3^{n}} =(10^{3^n})^2\equiv 1 (mod 3^{n+1})}\)
\(\displaystyle{ 10^{\varphi(3^{n+1})}=10^{2\;3^{n}} =(10^{3^n})^2\equiv 1 (mod 3^{n+1})}\)
- Maciej87
- Użytkownik
- Posty: 377
- Rejestracja: 26 sty 2009, o 09:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
Reszta z dzielenia, potęgi, suma
To może być za słabe.
Można udowodnić taką własność dla liczby pierwszej \(\displaystyle{ p}\):
\(\displaystyle{ a \equiv b \mod p^n \Rightarrow a^p \equiv b^p \mod p^{n+1}}\)
Stąd wynika (przez indukcję) że
\(\displaystyle{ a \equiv b \mod p \Rightarrow a^{p^{n}}\equiv b^{p^{n}} \mod p^{n+1}}\)
W szczególności,
\(\displaystyle{ 10^{3^{n}} \equiv 1 \mod 3^{n+1}}\)
a więc również
\(\displaystyle{ 10^{3^{n}\cdot k} \equiv 1 \mod 3^{n+1}}\).
Każdy ze składników daje resztę \(\displaystyle{ 1}\)
Można udowodnić taką własność dla liczby pierwszej \(\displaystyle{ p}\):
\(\displaystyle{ a \equiv b \mod p^n \Rightarrow a^p \equiv b^p \mod p^{n+1}}\)
Stąd wynika (przez indukcję) że
\(\displaystyle{ a \equiv b \mod p \Rightarrow a^{p^{n}}\equiv b^{p^{n}} \mod p^{n+1}}\)
W szczególności,
\(\displaystyle{ 10^{3^{n}} \equiv 1 \mod 3^{n+1}}\)
a więc również
\(\displaystyle{ 10^{3^{n}\cdot k} \equiv 1 \mod 3^{n+1}}\).
Każdy ze składników daje resztę \(\displaystyle{ 1}\)
Reszta z dzielenia, potęgi, suma
To pokazuje, co można próbować udowodnić.Maciej87 pisze:To może być za słabe.
\(\displaystyle{ 10^{3^n}} \equiv 1 \quad 10^{3^{n}} \equiv -1}\)
z czego to pierwsze wydaje się bardziej pasujące na oko.
-- 7 marca 2009, 20:40 --
Wtedy jedziemy indukcyjnie, że
\(\displaystyle{ 3^{n+1}|10^{3^n} -1}\)
W kroku indukcyjnym korzystamy ze wzory na różnicę sześcianów.
- Maciej87
- Użytkownik
- Posty: 377
- Rejestracja: 26 sty 2009, o 09:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
Reszta z dzielenia, potęgi, suma
OK. Albo na sześcian sumy, pisząc podzielność z definicji. Tak wchodzi ten fakt ogólniejszy.
Ja jeszcze na wszelki wypadek dla niektórych czytających odniosę się do tego:
\(\displaystyle{ 10^{3^n}} \equiv 1 \quad 10^{3^{n}} \equiv -1}\)
Niech \(\displaystyle{ x=10^{3^{n}}}\).
Wiemy że \(\displaystyle{ x^2\equiv 1}\), ale to nie stąd wynika \(\displaystyle{ x\equiv \pm 1}\).
Choć chcielibyśmy tak równanie kwadratowe intuicyjnie potraktować.
W naszym przypadku \(\displaystyle{ x^2-1=(x-1)(x+1)}\) i \(\displaystyle{ 3}\) dzieli dokładnie jeden czynnik.
Stąd \(\displaystyle{ 3^{n}}\) dzieli dokładnie jeden czynnik.
Ogólnie dla \(\displaystyle{ p=2}\) lub choćby innego równania to się nie uda.
Ja jeszcze na wszelki wypadek dla niektórych czytających odniosę się do tego:
\(\displaystyle{ 10^{3^n}} \equiv 1 \quad 10^{3^{n}} \equiv -1}\)
Niech \(\displaystyle{ x=10^{3^{n}}}\).
Wiemy że \(\displaystyle{ x^2\equiv 1}\), ale to nie stąd wynika \(\displaystyle{ x\equiv \pm 1}\).
Choć chcielibyśmy tak równanie kwadratowe intuicyjnie potraktować.
W naszym przypadku \(\displaystyle{ x^2-1=(x-1)(x+1)}\) i \(\displaystyle{ 3}\) dzieli dokładnie jeden czynnik.
Stąd \(\displaystyle{ 3^{n}}\) dzieli dokładnie jeden czynnik.
Ogólnie dla \(\displaystyle{ p=2}\) lub choćby innego równania to się nie uda.
-
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Reszta z dzielenia, potęgi, suma
O, widzę, że dużo mądrych rzeczy tutaj Panowie napisaliście Dziękuję, choć zatrzymałem się już na samym początku, a mianowicie:
1) co oznacza symbol \(\displaystyle{ \varphi}\) i gdzie można znaleźć jakieś artykuły o tym?
2)
1) co oznacza symbol \(\displaystyle{ \varphi}\) i gdzie można znaleźć jakieś artykuły o tym?
2)
Nie bardzo rozumiem tej implikacji. Mógłby ktoś rozjaśnić?\(\displaystyle{ a \equiv b \mod p^n \Rightarrow a^p \equiv b^p \mod p^{n+1}}\)
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Reszta z dzielenia, potęgi, suma
1) Jest to funkcja Eulera
2) Wzory skróconego mnożenia.
A rozwiązanie masz na tacy, wystarczy się rozejrzeć:
2) Wzory skróconego mnożenia.
A rozwiązanie masz na tacy, wystarczy się rozejrzeć:
frej pisze:Jedziemy indukcyjnie, że
\(\displaystyle{ 3^{n+1}|10^{3^n} -1}\)
W kroku indukcyjnym korzystamy ze wzory na różnicę sześcianów.
- Maciej87
- Użytkownik
- Posty: 377
- Rejestracja: 26 sty 2009, o 09:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
Reszta z dzielenia, potęgi, suma
Skoro jest zapotrzebowanie to jako autor uzupełnię dziurę w swoim poście
\(\displaystyle{ a\equiv b \mod p^{n}}\)
Zatem \(\displaystyle{ a=b+c\cdot p^{n}}\). Rozwijamy
\(\displaystyle{ a^{p}-b^{p} = \sum_{k=1..p} {p \choose k}c^{k}p^{n\cdot k}b^{p-k}}\)
więc uwzględniając to że \(\displaystyle{ {p \choose 1}=p}\), wszystkie składniki sumy więc i całość dzieli się przez \(\displaystyle{ p^{n+1}}\).
Można z tego groźnie wyglądające zadania układać
\(\displaystyle{ a\equiv b \mod p^{n}}\)
Zatem \(\displaystyle{ a=b+c\cdot p^{n}}\). Rozwijamy
\(\displaystyle{ a^{p}-b^{p} = \sum_{k=1..p} {p \choose k}c^{k}p^{n\cdot k}b^{p-k}}\)
więc uwzględniając to że \(\displaystyle{ {p \choose 1}=p}\), wszystkie składniki sumy więc i całość dzieli się przez \(\displaystyle{ p^{n+1}}\).
Można z tego groźnie wyglądające zadania układać