szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 10:25 
Użytkownik
Avatar użytkownika

Posty: 72
Lokalizacja: Olsztyn
Wyznacz dwie ostatnie cyfry liczby 36^{403}. Czy ta liczba jest podzielna przez 4 i 3?
Proszę o jakieś wskazówki :)
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 10:56 
Użytkownik
Avatar użytkownika

Posty: 1392
Lokalizacja: Polska, Warmia, Olsztyn :)
wskazówka: (wszystko modulo 100)

36^1=36\equiv 36

36^2=1296\equiv 96

36^3\equiv 96 \cdot 36\equiv 56

36^4\equiv 56 \cdot 36\equiv 16

36^5\equiv 16 \cdot 36\equiv 76

36^6\equiv 76 \cdot 36\equiv 36

i cykl się zamyka
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 11:10 
Użytkownik
Avatar użytkownika

Posty: 1885
Lokalizacja: hrubielowo
Albo z twierdzenie Eulera wynika że:

3^{40}\equiv1\bmod 100

oraz

2^{20}\equiv1\bmod 25 \  \Rightarrow \  2^{22}\equiv4\bmod 100

poza tym

36^{403}\equiv \left( 2^{806}\bmod 100  \cdot 3^{806}\bmod 100\right)  \bmod 100

i można rzeźbić dalej. Nie takie złe ale Psiaczek ładniejsze rozwiązanie podał jednak.
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 13:18 
Użytkownik
Avatar użytkownika

Posty: 72
Lokalizacja: Olsztyn
Dzięki za obie wskazówki, chociaż rozwiązanie podane przez Janusz Tracz pozostaje dla mnie nadal enigmatyczne ze względu na twierdzenie Eulera. :P
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 23:00 
Użytkownik
Avatar użytkownika

Posty: 1885
Lokalizacja: hrubielowo
twierdzenie Eulera to twierdzenie teorii liczb mówiące o tym, że dla liczb względnie pierwszych a,m czyli innymi słowy takich że \NWD\left( a,m\right)=1. Liczba a^{\phi(m)}-1 jest podzielna (bez reszty) przez m. Przy czym \phi(m) to tocjent lub funkcja Eulera. To jak zdefiniowany jest tocjent znajdziesz w linku. Wracając do twierdzenia zauważamy, że podzielność a^{\phi(m)}-1 przez m można wyrazi jako podzielność a^{\phi(m)} z resztą 1 a to w języku kongruencji oznacza że:

a^{\phi(m)}\equiv1\bmod m


i teraz jako że interesują mnie dwie ostatnie liczby to równoważnie mogę pytać o resztę z dzielenia przez 100. Ustalam więc że m=100. W takim razie \phi(100)=40 to wynika z definicji tocjentu. A jako że \NWD\left( 3,100\right)=1 to wiem z tw Eulera, że:

3^{40}\equiv1\bmod 100

z 2 nie jest tak prosto bo \NWD\left( 2,100\right) \neq 1 dopiero \NWD\left( 2,25\right) = 1 wiec obliczam \phi(25)=20 i stąd mam za Eulerem, że:

2^{20}\equiv1\bmod 25

a pomnożenie kongruencji stronami przez 4 daje mi 2^{22}\equiv4\bmod 100

Teraz odnośnie zadania to zauważyłem że 36^{403}=2^{806} \cdot 3^{806} a wiemy z własności modulo że ab \equiv \left( a\bmod m \cdot b\bmod m\right) \bmod m więc stąd mamy wspomniane:

36^{403}\equiv \left( 2^{806}\bmod 100 \cdot 3^{806}\bmod 100\right) \bmod 100

Problem sprowadził się do tego, że trzeba policzyć 2^{806}\bmod 100 oraz 3^{806}\bmod 100. Zacznę od łatwiejszego:

3^{806}=3^{40 \cdot 20+6} \equiv 3^6=729\equiv 29 \bmod 100

2^{806}=2^{22 \cdot 36+14}\equiv 4^{36} \cdot 2^{14}=2^{86}=2^{22 \cdot 3+20}\equiv 4^3 \cdot 2^{20}\equiv 4 \cdot 2^4=64 \bmod 100

czyli

36^{403}\equiv \left( 2^{806}\bmod 100 \cdot 3^{806}\bmod 100\right)\equiv 64  \cdot 29 \equiv 56  \bmod 100

Hura! Po pierwsze Psiaczek wypisał możliwości jakimi 36^n może się kończyć. Na szczęście 56 jest w śród nich. Po drugie skończyliśmy bo pokazując że 36^{403}\equiv 56 \bmod 100 pokazałem, że w 36^{403} liczba 100 mieści się całkowitą liczbę razy i zostaje 56 które jest resztą i dwiema ostatnimi cyframi ów liczby.

edit: znaczek się zgubił.
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 23:36 
Użytkownik
Avatar użytkownika

Posty: 72
Lokalizacja: Olsztyn
Dziękuje bardzo za szczegółowe wyjaśnienie twierdzenia Eulera Janusz Tracz. Wielokrotnie próbowałem zrozumieć to sam czy na przykładzie innych zadań ale dopiero teraz wiem na czym rzecz polega. Ciekawą opcją było zauważenie, że NWD(2,100) \not= 1(i z tego co zrozumiałem tutaj jeszcze nie można owego tw. wykorzystać) i po wymnożeniu stronami kongruencji 2^{20}\equiv1\bmod 2 (też dla mnie nowość) wychodzi ładnie do 2^{22}\equiv4\bmod 100. Do tego czasu myślałem, że gdy mnożę stronami kongruencje to dotyczy to liczb w układzie, a nie samej liczby modulo. Jaka jest różnica miedzy 2^{20}\equiv1\bmod 25, a 2^{22}\equiv4\bmod 25(1), a 2^{22}\equiv4\bmod 100(2)
W (1) mogę taką operacje na liczbach wykonać i dalej jest to prawdziwy układ bo wymnażam dwie liczby o taka samą wartość, natomiast w (2) jak to nazwać? mnożę cały układ wraz z liczbą modulo o dana wartość i jest to dalej prawdziwe?
PS. Mógłbyś mi podać jakiś przykład(może nie jakiś skomplikowany :)) w którym sprawdzę czy w praktyce potrafię zastosować twierdzenie Eulera?
Góra
Mężczyzna Offline
PostNapisane: 19 gru 2018, o 10:47 
Użytkownik
Avatar użytkownika

Posty: 1885
Lokalizacja: hrubielowo
Cytuj:
Ciekawą opcją było zauważenie, że \NWD(2,100)  \neq  1(i z tego co zrozumiałem tutaj jeszcze nie można owego tw. wykorzystać)
Tak. Twierdzenia Eulera nie można tu stosować. To znaczy tw. Eulera ma założenie i jest konieczne by to założenie było spełnione inaczej nie można mówić, że korzystamy z tw. Eulera. Dlatego najpierw zauważam, że dopiero \NWD(2,25) = 1 i tym samym wchodzę w zakres stosowalności twierdzenia (i je stosuję). Teraz opowiem o mnożeniu kongruencji w dwóch wersjach:

\bullet Mnożenie kongruencji przez siebie. Jeśli a\equiv b\bmod m oraz c\equiv d\bmod m to:

ac\equiv bd \bmod m

To twierdzenie ma postać implikacji i twierdzenie odwrotne jest fałszywe. A dowód polega na tym by zapisać:

ac-bd=\left( a-b\right)c+b\left(c-d \right)
I zauważmy że a-b jest podzielne przez m co wynika z założenia tak samo jak c-d też jest podzielne przez m co również jest założeniem. Skoro liczba po prawej jest podzielna to liczba po lewej też, czyli ac-bd jest podzielne przez m. Co kończy dowód.
Pewna uwaga.:    

\bullet Mnożenie kongruencji przez liczbę naturalną wraz z mnożeniem modułu. Jeśli udało Ci się przebrnąć przez to co już napisałem to teraz będzie już tylko prościej. Ustalmy jakieś k\in\NN i udowodnijmy

a\equiv b \bmod m \  \Leftrightarrow \ ak\equiv bk \bmod mk


Dowód twierdzenie jest bardzo przyjemny. Można (choć nie trzeba) udowodnić implikację w dwie strony. Czyli:

\left(  \Rightarrow \right) Wiemy, że a\equiv b \bmod m czyli \frac{a-b}{m}\in\ZZ zatem rozszerzając ten ułamek przez k dostajemy \frac{ak-bk}{mk}\in\ZZ. A to jest nic innego jak ak\equiv bk \bmod mk.

\left(  \Leftarrow \right) Wiemy, że ak\equiv bk \bmod mk czyli \frac{ak-bk}{mk}\in\ZZ zatem skracając ten ułamek przez k dostajemy \frac{a-b}{m}\in\ZZ. A to jest nic innego jak a\equiv b \bmod m.

Co dowodzi implikacji w prawo i w lewo a to dowodzi równoważności i jednocześnie kończy dowód.

Podczas pisania 2^{20}\equiv1\bmod 25 \ \Rightarrow \ 2^{22}\equiv4\bmod 100 skorzystałem z drugiego twierdzenia o "mnożeniu kongruencji przez liczbę naturalną wraz z mnożeniem modułu" a dokładnie jego implikacji w prawo. Mam nadzieję że teraz rozumiesz różnicę w mnożeniu kongruencji.

Co do przykładów to nie znam jakichś dydaktycznie dobrych, może za mało ich zrobiłem. Nie chcę żeby były za proste ale może udowodnij że 3^{104}-1 jest podzielne przez 53. Możesz też wyznaczyć ostatnie dwie cyfry 7^{777}.
Góra
Mężczyzna Offline
PostNapisane: 19 gru 2018, o 19:36 
Użytkownik
Avatar użytkownika

Posty: 72
Lokalizacja: Olsztyn
Wyznacz dwie ostatnie cyfry liczby 7^{777}
\NWD(7,100)=1\\\phi(100)=40
Z tw. Eulera
7^{40}\equiv1\bmod 100\\7^{777}=7^{19\cdot40+17}\equiv7^{17}\bmod 100
Z tego co widzę dzięki temu twierdzeniu w tym miejscu uprościło mi się obliczanie 7^{777} \bmod 100 do postaci oblicz 7^{17} \bmod 100
7^{4}\equiv 1\bmod 100\\7^{17}=7^{4\cdot4+1}\equiv7\bmod100
Stąd mam 7^{777}\bmod 100 wynosi \boxed{07}
Jeszcze mam pytanie do tego 7^{4}\equiv 1\bmod 100\\7^{17}=7^{4\cdot4+1}\equiv7\bmod100
Bo 7^{17}=7^{4\cdot4+1}=7^{16}\cdot7=(7^{4})^{4}\cdot7
tutaj liczba 7^4\equiv 1 \bmod 100 czyli w wyrażeniu 7^{17}=(7^{4})^{4}\cdot7 zastępuję liczbę 7^{4} liczbą 1 przystawaniu do \bmod 100 w ten sposób, że 7^{17}=(7^{4})^{4}\cdot7\equiv1^{4}\cdot7=7\bmod100
Czy dobrze to zrozumiałem?

Udowodnij że 3^{104}-1 jest podzielne przez 53
\NWD(3,53)=1\\\phi(53)=52
Z tw. Eulera
3^{52}\equiv1\bmod 53\\3^{104}=3^{52\cdot2}\equiv1\bmod53\Rightarrow3^{104}-1\equiv0\bmod53
co należało dowieść
Najpierw zabrałem się za zrobienie drugiego zadania wydawało się prostsze, a jednak pierwsze dużo szybciej wyszło :)
Jeszcze mam dwa pytanka. Jest jakiś sprawny sposób obliczania tocjentu?
Napisałeś w "Pewna uwaga" coś takiego: ab\equiv ac \bmod m \ \Rightarrow \ b\equiv c \bmod m oraz \NWD\left( a,n\right)=1 nie bardzo rozumiem co oznacza \NWD\left( a,n\right)=1. a i n muszą być względnie pierwsze tylko co to te n?
Góra
Mężczyzna Offline
PostNapisane: 19 gru 2018, o 19:53 
Użytkownik
Avatar użytkownika

Posty: 13226
Lokalizacja: Wrocław
Cytuj:
Jest jakiś sprawny sposób obliczania tocjentu?

Jeżeli masz rozkład liczby całkowitej n>1 na czynniki pierwsze:
n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\ldots\cdot p_k^{\alpha_k},
gdzie p_i to parami różne liczby pierwsze, to
\phi\left( n\right) =\phi\left(p_1^{\alpha_1}\right)\cdot \phi\left( p_2^{\alpha_2}\right) \ldots\cdot \phi\left(p_k^{\alpha_k\right)
Ogólnie jeśli \NWD(a,b)=1 dla pewnych liczb całkowitych dodatnich a,b, to
\phi(ab)=\phi(a)\cdot \phi(b)

Ponadto dla dowolnej liczby pierwszej p i liczby całkowitej dodatniej k mamy
\phi\left(p^k\right)=(p-1)\cdot p^{k-1}
To dość proste: liczb od 1 do p^k, które są podzielne przez p mamy
\left\lfloor \frac{p^k}{p}\right\rfloor=p^{k-1}
i odejmujemy tę liczbę od liczby wszystkich liczb całkowitych dodatnich nie większych niż p^k, dostając p^k-p^{k-1}=(p-1)p^{k-1} liczb w tym zakresie niepodzielnych przez liczbę pierwszą p (co za tym idzie, względnie pierwszych z nią).
Góra
Mężczyzna Offline
PostNapisane: 20 gru 2018, o 11:32 
Użytkownik
Avatar użytkownika

Posty: 1885
Lokalizacja: hrubielowo
Cytuj:
Napisałeś w "Pewna uwaga" coś takiego: ab\equiv ac \bmod m \ \Rightarrow \ b\equiv c \bmod m oraz \NWD\left( a,n\right)=1 nie bardzo rozumiem co oznacza \NWD\left( a,n\right)=1. a i n muszą być względnie pierwsze tylko co to te n?
Ah faktycznie. Zmęczenie z nieuwagą spowodowało pewną niekonsekwencję. Powinienem wszędzie pisać m zamiast n skoro się na nie zdecydowałem. Tak, że wszystko jest ok tylko podmień n \rightarrow m
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznacz dwie ostatnie cyfry  qmandos  1
 Wyznacz dwie ostatnie cyfry - zadanie 2  studciak123  2
 Wyznacz dwie ostatnie cyfry - zadanie 3  max123321  7
 Zmieniamy cyfry dziesiątek i jednosci - co to za liczba ?  Anonymous  3
 Wyznacz liczby 5-cio cyfrowe podzielne przez 36  tuti  2
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl