Dwie ostatnie cyfry liczby

[kamil13151]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 7 ^{9 ^{9 ^{9} } }}\).

Dałem radę wyznaczyć ostatnią cyfrę korzystając kongruencji, ale nie mam pomysłu jak przedostatnią wyliczyć.

[Marcinek665]

Oczywiście (7,100)=1. Zauważmy, że z twierdzenia Eulera mamy:

\(\displaystyle{ 7^{\varphi (100)} \equiv 1 (\hbox{mod} 100)}\),

\(\displaystyle{ \varphi (100) = \varphi (2^2 \cdot 5^2 ) = \varphi (4) \varphi (25) = 40}\)

Więc

\(\displaystyle{ 7^{40} \equiv 1 (\hbox{mod} 100)}\)

Wystarczy teraz przedstawić liczbę \(\displaystyle{ 9^{9^{9}}}\) w postaci \(\displaystyle{ 40k + n}\), czyli znaleźć resztę z dzielenia \(\displaystyle{ 9^{9^{9}}}\) przez \(\displaystyle{ 40}\). Szybki rachunek ukazuje, że \(\displaystyle{ 9^{9^{9}} \equiv 9 (\hbox{mod} 40)}\)

Zatem \(\displaystyle{ 7^{9^{9^{9}}} = 7^{40k + 9} = (7^{40})^k * 7^9 = 7^9 = 7(\hbox{mod} 100)}\)

Ostatecznie ostatnimi dwiema cyframi tej liczby są 07

EDIT: Dzięki Vax za obliczenie mi \(\displaystyle{ 9^2}\) :*

[Vax]

Bardzo ładnie, można zdecydowanie szybciej:

\(\displaystyle{ 9 \equiv 1 (mod \ 4) \Rightarrow 9^{9^9} \equiv 1 (mod \ 4) \Leftrightarrow 9^{9^9} = 4k+1 , k \in N}\)

Zauważmy, że \(\displaystyle{ 7^4 \equiv 1 (mod \ 100) /^k \Rightarrow 7^{4k} \equiv 1 (mod \ 100) \Rightarrow 7^{4k+1} \equiv 7 (mod \ 100)}\)

Czyli 2 ostatnie cyfry to 07.

Pozdrawiam.

[kamil13151]

Dziękuje Wam.

Co to za znak? \(\displaystyle{ \varphi}\)

[Vax]

Jest to funkcja Eulera:



Pozdrawiam.

[Kanodelo]

Dałem radę wyznaczyć ostatnią cyfrę korzystając kongruencji, ale nie mam pomysłu jak przedostatnią wyliczyć.

A pokażesz mi jak tą ostatnią cyfre wyznaczyć bo ja nawet ostatniej nie umim wyznaczyć

[kamil13151]

Zrobiłem to tak:
\(\displaystyle{ 7^1=7 \Rightarrow 7^5 \Rightarrow 7^9 \\
7^2=49 \Rightarrow 7^6 \\
7^3=343 \Rightarrow 7^7 \\
7^4=2401 \Rightarrow 7^8}\)
Następne potęgi będą kolejno dawać na końcu taką samą cyfrę, czyli 7,9,3,1.

Teraz sprawdźmy jaką ostatnią cyfrę ma: \(\displaystyle{ 9 ^{9 ^{9} }}\)

Skorzystamy z kongruencji:

\(\displaystyle{ 9 \equiv -1 \ (mod \ 10)}\)

\(\displaystyle{ 9 ^{9 ^{9}} \equiv (-1)^{9 ^{9}} \equiv -1 \equiv 9 \ (mod \ 10)}\)

Ostatnią cyfrą \(\displaystyle{ 9 ^{9 ^{9} }}\) jest 9, więc: \(\displaystyle{ 7 ^{...9}}\)

a dziewiątka podlega pod \(\displaystyle{ 7^1=7}\), czyli ostatnią cyfrą jest 7.

[Kanodelo]

Dzięki dałbym ci punkt ale się nie da.

[Vax]

Można trochę szybciej:

\(\displaystyle{ 9 \equiv 1 (mod \ 4) \Rightarrow 9^{9^{9}} \equiv 1 (mod 4) \Leftrightarrow 9^{9^{9}} = 4k+1}\)

Teraz zauważamy, że:

\(\displaystyle{ 7^4 \equiv 1 (mod \ 10) \Rightarrow 7^{4k} \equiv 1 (mod \ 10) \Rightarrow 7^{4k+1} \equiv 7 (mod \ 10)}\)

Pozdrawiam.

[95Villain95]

Wystarczy teraz przedstawić liczbę \(\displaystyle{ 9^{9^{9}}}\) w postaci \(\displaystyle{ 40k + n}\), czyli znaleźć resztę z dzielenia \(\displaystyle{ 9^{9^{9}}}\) przez \(\displaystyle{ 40}\). Szybki rachunek ukazuje, że \(\displaystyle{ 9^{9^{9}} \equiv 9 (\hbox{mod} 40)}\)

Czy ktoś może mi wyjaśnić w jaki sposób zostało wyliczone \(\displaystyle{ 9^{9^{9}} \equiv 9 (\hbox{mod} 40)}\)?

[Premislav]

Tego nikt oprócz Autora Ci nie powie, trochę "niesprytne" jest takie pytanie. Można zrobić np. tak:
\(\displaystyle{ \phi(40)=\phi(5)\cdot \phi(8)=16}\) oraz \(\displaystyle{ (9,40)=1}\).
Zatem z tw. Eulera mamy \(\displaystyle{ 9^{16}\equiv 1\pmod{40}}\). Ponadto \(\displaystyle{ 9^{9}=9\cdot (9^{2})^{4}}\) i \(\displaystyle{ 9^{2}\equiv 1\pmod{16}}\), więc \(\displaystyle{ (9^{2})^{4}\equiv 1^{4}\pmod{16}}\)
i \(\displaystyle{ 9\cdot(9^{2})^{4}\equiv 9\pmod{16}}\). Stąd istnieje takie \(\displaystyle{ m}\) naturalne, że
\(\displaystyle{ 9^{9^{9}}=9^{16m+9}=9^{9} \cdot (9^{16})^{m}}\),
zaś \(\displaystyle{ 9^{9}\equiv 9\pmod{40}}\), bo \(\displaystyle{ 9^{9}=9\cdot (2\cdot 40+1)^{4}}\) i \(\displaystyle{ (9^{16})^{m}\equiv 1\pmod{40}}\), a więc
\(\displaystyle{ 9^{9^{9}}\equiv 9\pmod{40}}\)

-- 5 cze 2016, o 13:44 --

Można o wiele prościej. Uogólnijmy obserwację \(\displaystyle{ 9^{9}\equiv 9\pmod{40}}\) na \(\displaystyle{ 9^{2k+1}\equiv 9\pmod{40} dla k\in \NN}\). Istotnie, mamy
\(\displaystyle{ 9\equiv 9\pmod{40}}\) a także \(\displaystyle{ 9^{2k+1}=9\cdot (80+1)^{k}}\)...

[95Villain95]

Co nowy temat przeglądam z tego typu zadaniami, to napotykam coraz to nowsze metody ich rozwiązywania. Czy istnieje jakaś uniwersalna?

[Premislav]

Miałeś może na myśli uniwersalną.

Raczej nie ma takiej (choć może taki pogląd to kwestia mojej ignorancji), jest za to pewien zestaw chwytów i sztuczek, które się przydają:
sprawdzanie modulo małe liczby, podstawowe własności kongruencji, twierdzenie Eulera, jego szczególny przypadek, czyli małe twierdzenie Fermata, wzór dwumianowy Newtona...

[95Villain95]

Mam jeszcze pytanie do jednej z metod, mamy przykład \(\displaystyle{ 123 ^{512}}\). Oczywiście wyznaczamy dwie ostatnie cyfry.
\(\displaystyle{ 123 ^{40} \equiv 1(mod100)}\)
\(\displaystyle{ 123 \equiv 123(mod100)}\)
\(\displaystyle{ 512 = 40*12+32}\)
\(\displaystyle{ 123 ^{40*12+32} \equiv 123 ^{32} (mod100)}\)
Metoda sprawdza się w przypadku, gdy zostaje nam mała reszta po podzieleniu wykładnika potęgi przez \(\displaystyle{ 40}\). Jednak w tym przypadku mamy 32, w związku z tym szukam jakiegoś w miarę uniwersalnego i szybkiego sposobu policzenia dwóch ostatnich cyfr liczby postaci \(\displaystyle{ a^{b}}\), gdzie \(\displaystyle{ b}\) doprowadzę do wartości \(\displaystyle{ b<40}\). Jakieś sugestie?

[Premislav]

Mamy też \(\displaystyle{ 123^{20}\equiv 1\pmod {100}}\) - bo taka liczba daje resztę jeden z dzielenia przez \(\displaystyle{ 4}\) i przez \(\displaystyle{ 25}\). To nam zredukuje wykładnik do \(\displaystyle{ 12}\), a takie pitki to dobić można choćby ze wzoru dwumianowego Newtona.
Ogólnie gdy Euler zostawia za duże wykładniki, to dobrze jest szukać mniejszego n takiego, że \(\displaystyle{ a^n \equiv 1\pmod{b}}\) (lub minus jeden).