Reszta z dzielenia, potęgi, suma

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
patry93
Użytkownik
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

Post autor: patry93 »

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.
frej

Reszta z dzielenia, potęgi, suma

Post autor: frej »

Podpowiedź:
\(\displaystyle{ 10^{\varphi(3^{n+1})}=10^{2\;3^{n}} =(10^{3^n})^2\equiv 1 (mod 3^{n+1})}\)
Awatar użytkownika
Maciej87
Użytkownik
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

Post autor: Maciej87 »

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}\)
frej

Reszta z dzielenia, potęgi, suma

Post autor: frej »

Maciej87 pisze:To może być za słabe.
To pokazuje, co można próbować udowodnić.

\(\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.
Awatar użytkownika
Maciej87
Użytkownik
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

Post autor: Maciej87 »

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.
patry93
Użytkownik
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

Post autor: patry93 »

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)
\(\displaystyle{ a \equiv b \mod p^n \Rightarrow a^p \equiv b^p \mod p^{n+1}}\)
Nie bardzo rozumiem tej implikacji. Mógłby ktoś rozjaśnić?
Awatar użytkownika
Sylwek
Użytkownik
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

Post autor: Sylwek »

1) Jest to funkcja Eulera
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.
Awatar użytkownika
Maciej87
Użytkownik
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

Post autor: Maciej87 »

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ć
ODPOWIEDZ