wyznacz dwie ostatnie cyfry

[Bratower]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 36^{403}}\). Czy ta liczba jest podzielna przez \(\displaystyle{ 4}\) i \(\displaystyle{ 3}\)?
Proszę o jakieś wskazówki

[Psiaczek]

wskazówka: (wszystko modulo \(\displaystyle{ 100}\))

\(\displaystyle{ 36^1=36\equiv 36}\)

\(\displaystyle{ 36^2=1296\equiv 96}\)

\(\displaystyle{ 36^3\equiv 96 \cdot 36\equiv 56}\)

\(\displaystyle{ 36^4\equiv 56 \cdot 36\equiv 16}\)

\(\displaystyle{ 36^5\equiv 16 \cdot 36\equiv 76}\)

\(\displaystyle{ 36^6\equiv 76 \cdot 36\equiv 36}\)

i cykl się zamyka

[Janusz Tracz]

Albo z

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29

wynika że:

\(\displaystyle{ 3^{40}\equiv1\bmod 100}\)

oraz

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

poza tym

\(\displaystyle{ 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.

[Bratower]

Dzięki za obie wskazówki, chociaż rozwiązanie podane przez Janusz Tracz pozostaje dla mnie nadal enigmatyczne ze względu na twierdzenie Eulera.

[Janusz Tracz]

twierdzenie Eulera to twierdzenie teorii liczb mówiące o tym, że dla liczb względnie pierwszych \(\displaystyle{ a,m}\) czyli innymi słowy takich że \(\displaystyle{ \NWD\left( a,m\right)=1}\). Liczba \(\displaystyle{ a^{\phi(m)}-1}\) jest podzielna (bez reszty) przez \(\displaystyle{ m}\). Przy czym \(\displaystyle{ \phi(m)}\) to

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_%CF%86

. To jak zdefiniowany jest tocjent znajdziesz w linku. Wracając do twierdzenia zauważamy, że podzielność \(\displaystyle{ a^{\phi(m)}-1}\) przez \(\displaystyle{ m}\) można wyrazi jako podzielność \(\displaystyle{ a^{\phi(m)}}\) z resztą \(\displaystyle{ 1}\) a to w języku kongruencji oznacza że:

\(\displaystyle{ 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 \(\displaystyle{ 100}\). Ustalam więc że \(\displaystyle{ m=100}\). W takim razie \(\displaystyle{ \phi(100)=40}\) to wynika z definicji tocjentu. A jako że \(\displaystyle{ \NWD\left( 3,100\right)=1}\) to wiem z tw Eulera, że:

\(\displaystyle{ 3^{40}\equiv1\bmod 100}\)

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

\(\displaystyle{ 2^{20}\equiv1\bmod 25}\)

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

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

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

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

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

\(\displaystyle{ 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

\(\displaystyle{ 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 \(\displaystyle{ 36^n}\) może się kończyć. Na szczęście \(\displaystyle{ 56}\) jest w śród nich. Po drugie skończyliśmy bo pokazując że \(\displaystyle{ 36^{403}\equiv 56 \bmod 100}\) pokazałem, że w \(\displaystyle{ 36^{403}}\) liczba \(\displaystyle{ 100}\) mieści się całkowitą liczbę razy i zostaje \(\displaystyle{ 56}\) które jest resztą i dwiema ostatnimi cyframi ów liczby.

edit: znaczek się zgubił.

[Bratower]

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 \(\displaystyle{ 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 \(\displaystyle{ 2^{20}\equiv1\bmod 2}\) (też dla mnie nowość) wychodzi ładnie do \(\displaystyle{ 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 \(\displaystyle{ 2^{20}\equiv1\bmod 25}\), a \(\displaystyle{ 2^{22}\equiv4\bmod 25(1)}\), a \(\displaystyle{ 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?

[Janusz Tracz]

Ciekawą opcją było zauważenie, że \(\displaystyle{ \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 \(\displaystyle{ \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:

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

\(\displaystyle{ ac\equiv bd \bmod m}\)

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

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

Pewna uwaga.:    

Czasem w pewnych szczególnych przypadkach zachodzi twierdzenie które przypomina twierdzenie odwrotne (ale lepiej tak tego nie nazywać). Poprawna nazwa to prawo skracania. To jest,

\(\displaystyle{ ab\equiv ac \bmod m \ \Rightarrow \ b\equiv c \bmod m}\)

Pod warunkiem, że \(\displaystyle{ \NWD\left( a,n\right)=1}\). To bardzo ważne żeby warunek był spełniony.
Dowód jest prosty i polega na pomnożeniu kongruencji stronami przez \(\displaystyle{ a^{-1}}\) czyli element odwrotny do \(\displaystyle{ a}\) w \(\displaystyle{ \bmod m}\). Istnienie takiego elementu jest gwarantowane przez warunek \(\displaystyle{ \NWD\left( a,n\right)=1}\). Co swoją drogą też wymaga dowodu choć tego przeprowadzać nie będę (chyba że bardzo chcesz) wynika to z

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/To%C5%BCsamo%C5%9B%C4%87_B%C3%A9zouta

\(\displaystyle{ \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ś \(\displaystyle{ k\in\NN}\) i udowodnijmy

\(\displaystyle{ 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:

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

\(\displaystyle{ \left( \Leftarrow \right)}\) Wiemy, że \(\displaystyle{ ak\equiv bk \bmod mk}\) czyli \(\displaystyle{ \frac{ak-bk}{mk}\in\ZZ}\) zatem skracając ten ułamek przez \(\displaystyle{ k}\) dostajemy \(\displaystyle{ \frac{a-b}{m}\in\ZZ}\). A to jest nic innego jak \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ 3^{104}-1}\) jest podzielne przez \(\displaystyle{ 53}\). Możesz też wyznaczyć ostatnie dwie cyfry \(\displaystyle{ 7^{777}}\).

[Bratower]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 7^{777}}\)
\(\displaystyle{ \NWD(7,100)=1\\\phi(100)=40}\)
Z tw. Eulera
\(\displaystyle{ 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 \(\displaystyle{ 7^{777} \bmod 100}\) do postaci oblicz \(\displaystyle{ 7^{17} \bmod 100}\)
\(\displaystyle{ 7^{4}\equiv 1\bmod 100\\7^{17}=7^{4\cdot4+1}\equiv7\bmod100}\)
Stąd mam \(\displaystyle{ 7^{777}\bmod 100}\) wynosi \(\displaystyle{ \boxed{07}}\)
Jeszcze mam pytanie do tego \(\displaystyle{ 7^{4}\equiv 1\bmod 100\\7^{17}=7^{4\cdot4+1}\equiv7\bmod100}\)
Bo \(\displaystyle{ 7^{17}=7^{4\cdot4+1}=7^{16}\cdot7=(7^{4})^{4}\cdot7}\)
tutaj liczba \(\displaystyle{ 7^4\equiv 1 \bmod 100}\) czyli w wyrażeniu \(\displaystyle{ 7^{17}=(7^{4})^{4}\cdot7}\) zastępuję liczbę \(\displaystyle{ 7^{4}}\) liczbą \(\displaystyle{ 1}\) przystawaniu do \(\displaystyle{ \bmod 100}\) w ten sposób, że \(\displaystyle{ 7^{17}=(7^{4})^{4}\cdot7\equiv1^{4}\cdot7=7\bmod100}\)
Czy dobrze to zrozumiałem?

Udowodnij że \(\displaystyle{ 3^{104}-1}\) jest podzielne przez \(\displaystyle{ 53}\)
\(\displaystyle{ \NWD(3,53)=1\\\phi(53)=52}\)
Z tw. Eulera
\(\displaystyle{ 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: \(\displaystyle{ ab\equiv ac \bmod m \ \Rightarrow \ b\equiv c \bmod m}\) oraz \(\displaystyle{ \NWD\left( a,n\right)=1}\) nie bardzo rozumiem co oznacza \(\displaystyle{ \NWD\left( a,n\right)=1}\). \(\displaystyle{ a}\) i \(\displaystyle{ n}\) muszą być względnie pierwsze tylko co to te \(\displaystyle{ n}\)?

[Premislav]

Jest jakiś sprawny sposób obliczania tocjentu?

Jeżeli masz rozkład liczby całkowitej \(\displaystyle{ n>1}\) na czynniki pierwsze:
\(\displaystyle{ n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\ldots\cdot p_k^{\alpha_k}}\),
gdzie \(\displaystyle{ p_i}\) to parami różne liczby pierwsze, to
\(\displaystyle{ \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 \(\displaystyle{ \NWD(a,b)=1}\) dla pewnych liczb całkowitych dodatnich \(\displaystyle{ a,b}\), to
\(\displaystyle{ \phi(ab)=\phi(a)\cdot \phi(b)}\)

Ponadto dla dowolnej liczby pierwszej \(\displaystyle{ p}\) i liczby całkowitej dodatniej \(\displaystyle{ k}\) mamy
\(\displaystyle{ \phi\left(p^k\right)=(p-1)\cdot p^{k-1}}\)
To dość proste: liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ p^k}\), które są podzielne przez \(\displaystyle{ p}\) mamy
\(\displaystyle{ \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ż \(\displaystyle{ p^k}\), dostając \(\displaystyle{ p^k-p^{k-1}=(p-1)p^{k-1}}\) liczb w tym zakresie niepodzielnych przez liczbę pierwszą \(\displaystyle{ p}\) (co za tym idzie, względnie pierwszych z nią).

[Janusz Tracz]

Napisałeś w "Pewna uwaga" coś takiego: \(\displaystyle{ ab\equiv ac \bmod m \ \Rightarrow \ b\equiv c \bmod m}\) oraz \(\displaystyle{ \NWD\left( a,n\right)=1}\) nie bardzo rozumiem co oznacza \(\displaystyle{ \NWD\left( a,n\right)=1}\). \(\displaystyle{ a}\) i \(\displaystyle{ 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ć \(\displaystyle{ m}\) zamiast \(\displaystyle{ n}\) skoro się na nie zdecydowałem. Tak, że wszystko jest ok tylko podmień \(\displaystyle{ n \rightarrow m}\)