szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 lis 2017, o 21:00 
Użytkownik
Avatar użytkownika

Posty: 128
Lokalizacja: Nowy Sącz
Wyznacz dwie ostatnie cyfry liczby 17^{17^{17^{17}}} + 18{^{18^{18^{18}}} + 19^{19^{19^{19}}} +20^{20^{20^{20}}}}.
Prosiłbym gorąco o jakąś wskazówkę do tego zadania (wiem, że należy obliczyć modulo 100 tej liczby, ale ciągle wychodzą mi ogromne wyniki).
Góra
Mężczyzna Offline
PostNapisane: 4 lis 2017, o 01:00 
Gość Specjalny
Avatar użytkownika

Posty: 17850
Lokalizacja: Cieszyn
17^{20} daje resztę 1. Poszukaj, jakie potęgi 18,19,20 daję resztę 1. Wyznacz osobno reszty dla każdego ze składników, a potem dla sumy - to już będzie łatwe.
Góra
Mężczyzna Offline
PostNapisane: 4 lis 2017, o 01:13 
Użytkownik
Avatar użytkownika

Posty: 10588
Lokalizacja: Wrocław
Jeśli chodzi o 18 i 20, to raczej żadne, gdyż \NWD(18, 100)>1, podobnie \NWD(20,100)>1.
Pierwszą moją myślą w tym zadaniu było twierdzenie Eulera (bo przecież nie będziemy sprawdzać na kartce dwudziestu wykładników, a rozwiązanie z pomocą komputera chyba nie jest tu naszym celem), ale nie wiem, czy autor wątku je zna.
W każdym razie potęgę 17 i potęgę 19 załatwia twierdzenie Eulera, tylko trzeba je „zagnieździć" w wykładnikach, potęga 20 (mamy wszakże parzysty wykładnik) nie ma znaczenia (dlaczego?), najgorzej jest z potęgą 18, nie przychodzi mi do głowy nic lepszego niż rozbicie tego: 18^2=324\equiv -1\pmod{25}, zatem 18^{4k}\equiv 1 \pmod{25}, \ k=1,2\ldots. Ponadto 18^{l}\equiv 0 \pmod{4}, \ l=2,3\ldots, więc po prostym rozważeniu przypadków widzimy, że 18^{4k}\equiv 76\pmod{100}, \ k=1,2\ldots
Jakbyś miał, KrolKubaV, problem z tym Eulerem do 17 i 19, to pisz, ale może istnieje prostszy sposób.
Góra
Mężczyzna Offline
PostNapisane: 4 lis 2017, o 11:10 
Użytkownik
Avatar użytkownika

Posty: 128
Lokalizacja: Nowy Sącz
Premislav, mógłbyś pokazać jak z tym Eulerem zrobić, bo jak ja robię to i tak na końcu muszę sprawdzić 17^{17} \mod100 i zastanawiam się, czy można to ominąć w jakiś sposób?
Góra
Mężczyzna Offline
PostNapisane: 4 lis 2017, o 16:24 
Użytkownik
Avatar użytkownika

Posty: 10588
Lokalizacja: Wrocław
Bardzo mi się nie chciało zabierać do tych obliczeń, ale już trudno, głupio tak zostawiać wątek.

Warto na wstępie coś wiedzieć o funkcji Eulera: klik.
Mamy zatem \phi(100)=\phi(2^2\cdot 5^2)=\phi(2^2)\cdot \phi(5^2)=2\cdot 20=40.
Ponadto, rzecz jasna, \NWD(17,100)=1. A zatem na mocy twierdzenia Eulera mamy 17^{40}\equiv 1\pmod{100}. Po chwili refleksji widzimy, że wobec tego 17^{40k}\equiv 1\pmod{100} dla k=1,2,3\ldots.
Chcielibyśmy więc przedstawić ten wykładnik 17, czyli 17^{17^{17} w postaci 40k+r, gdzie konkretnie interesuje nas dokładna wartość r \in \left\{ 0,1\ldots 39\right\}. W tym celu ponownie użyjemy twierdzenia Eulera: mamy
\NWD(17,40)=1 oraz \phi(40)=\phi(2^3\cdot 5)=\phi(2^3)\phi(5)=4\cdot 4=16
Zatem 17^{16}\equiv 1\pmod{40} na mocy twierdzenia Eulera i stąd dla dowolnego m\in \NN^+ dostajemy też 17^{16m}\equiv 1\pmod{40}. Ponadto
17\equiv 1\pmod{16}, zatem łatwo uzyskać, że
17^{17}\equiv 1\pmod{16}, więc
17^{17}=16m+1, dla pewnego m\in \NN^+, czyli
17^{17^{17}}\equiv 17\pmod{40}, a stąd
17^{17^{17^{17}}}\equiv 17^{17}\pmod{100}.
A tego już nie będę obliczał, bo to jest jakiś syf, ale nie powinno to być bardzo trudne (wczesniej się pomyliłem).

Dla 19 można bardzo podobnie z twierdzenia Eulera, chociaż pewnie szybciej byłoby zauważyć, że 19^{10}\equiv 1 \pmod{100}.

-- 4 lis 2017, o 17:49 --

A nie, no nie umiem czytać po prostu, doszedłem do tego samego, co Ty.
To faktycznie jest obrzydlistwo. Moim zdaniem nic ładnego z tym nie można zrobić, tylko siłownia pozostaje.
17^2\equiv -11 \pmod{100}\\ (17^{2})^8\equiv 11^8 \pmod{100}
Dalej ze wzoru dwumianowego Newtona:
11^8=(10+1)^8=\ldots
możemy otrzymać, że 11^8 \equiv 81\pmod{100}
i w końcu 17^{17}=17\cdot 17^{16}\equiv 17\cdot 11^8 \pmod{100}
czyli 17^{17}\equiv 17\cdot 81\pmod{100}
no i z tym już nic ładnego nie zrobisz, ołówek w łapę i pod kreską albo 81=100-19\equiv -19\pmod{100} i mniejsze rzeczy pod kreską.
Ostatecznie 17^{17}\equiv 77 \pmod{100}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 dwie ostatnie cyfry  blackbird936  4
 dwie ostatnie cyfry - zadanie 2  patryk00714  3
 dwie ostatnie cyfry - zadanie 3  robertos18  4
 Dwie (proste) podzielności  Zaratustra  4
 Wstaw cyfry...  RAFAELLO14  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl