Witam, jak szybko obliczyć 6 ostatnich cyfr takiej liczby \(\displaystyle{ 2^{5 ^{9 ^{8 ^{12 ^{2 ^{4} } } } } }}\)? Poszczególne potęgi można wymnożyć i tym samym otrzymać \(\displaystyle{ 2^{34560}}\), ale co dalej z tym zrobić? Odpowiedzią do zadania jest \(\displaystyle{ 186432}\), ale czy ktoś mógłby mi wytłumaczyć jak do tego dojść?
Pozdrawiam
Sześć ostatnich cyfr liczby, duża potęga
-
Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Sześć ostatnich cyfr liczby, duża potęga
Raczej tych potęg tak mnożyć nie wolno.
Przy pomocy twierdzenia Eulera i chińskiego twierdzenia o reszyach można ten problem sprowadzić do problemu rozwiązywalnego na papierze. Choć posiłkowanie się kalkulatorem byłoby wskazane dla przyśpieszenia pracy.
Przy pomocy twierdzenia Eulera i chińskiego twierdzenia o reszyach można ten problem sprowadzić do problemu rozwiązywalnego na papierze. Choć posiłkowanie się kalkulatorem byłoby wskazane dla przyśpieszenia pracy.
-
foxbuur
- Użytkownik
- Posty: 34
- Rejestracja: 18 lis 2013, o 20:12
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 15 razy
Sześć ostatnich cyfr liczby, duża potęga
Mógłbyś powiedzieć coś więcej, jak zastosować tu to twierdzenie Eulera i chinskie twierdzenie o resztach?
-
Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Sześć ostatnich cyfr liczby, duża potęga
Masz liczbę postaci \(\displaystyle{ 2^{a}}\). Chcemy policzyć \(\displaystyle{ 2^{a} \mod 10^{6}}\). To wystarczy policzyć \(\displaystyle{ 2^{a} \mod 2^{6}}\) i \(\displaystyle{ 2^{a} \mod 5^{6}}\), a potem popracować z chińskim twierdzeniem o resztach. Oczywiście \(\displaystyle{ 2^{a} \mod 2^{6}=0}\), bo \(\displaystyle{ a\ge 6}\).
Zostało nam policzyć \(\displaystyle{ 2^{a} \mod 5^{6}}\). To teraz zgodnie z tw. Eulera fajnie by było się zająć \(\displaystyle{ a \mod \varphi \left(5^{6}\right)}\), czyli \(\displaystyle{ 5^{b} \mod 4\cdot 5^{5}}\). To teraz znów z chińskiego twierdzenia o resztach wystarczy policzyć \(\displaystyle{ 5^{b} \mod 4=1}\) i \(\displaystyle{ 5^{b} \mod 5^{5}=0}\), bo \(\displaystyle{ b \ge 5}\). Oczywiście \(\displaystyle{ 5^{5}}\) jest rozwiązaniem naszego układu, a w myśl chińskiego twierdzenia o resztach, z dokladnością do \(\displaystyle{ 4 \cdot 5^{5}}\) ten układ więcej rozwiązań nie ma. Zatem \(\displaystyle{ 5^{b} \equiv 5^{5} \pmod{4\cdot 5^{5}}}\), czyli \(\displaystyle{ 5^{b}= 4k \cdot 5^{5}+5^{5}}\), gdzie \(\displaystyle{ k\in\ZZ}\).
Wracamy do twierdzenia Eulera:
\(\displaystyle{ 2^{a}=2^{5^{b}}=2^{4k \cdot 5^{5}+5^{5}}=\left(2^{\varphi\left(5^{6}\right)}\right)^{k}\cdot 2^{5^{5}}\equiv 1 \cdot 2^{5^{5}}\equiv 2^{5^{5}} \pmod{5^{6}}}\)
Ta część zadania sprowadza się już tylko do względnie sprytnego obliczenia \(\displaystyle{ 2^{5^{5}} \mod 5^{6}=c}\).
Jak już to zrobimy, to zostanie nam układ:
\(\displaystyle{ \begin{cases} 2^{a} \equiv 0 \pmod{2^{6}} \\ 2^{a} \equiv c \pmod{5^{6}} \end{cases}}\)
Z pierwszego równania wnioskujemy, że \(\displaystyle{ 2^{a} = 2^{6} \cdot m}\). Jak podstawimy to do drugiego równania, to mamy:
\(\displaystyle{ 2^{6} \cdot m \equiv c \pmod{5^{6}} \Leftrightarrow m \equiv 2^{-6} \cdot c \pmod{5^{6}}}\)
To zostało jeszcze żmudne zadanie by policzyć \(\displaystyle{ 2^{-6} \pmod{5^{6}}}\). Ale możemy zwyczajnie policzyć w pamięci \(\displaystyle{ 2^{-1} \mod 15625 = 7813}\) (wiesz dlaczego?), a potem wynik podnieść do szóstej potęgi, czyli \(\displaystyle{ m\equiv 7813^{6} \cdot c \pmod{5^{6}}}\), co należy policzyć.
Jak już to będziemy mieli, to \(\displaystyle{ 2^{a} \equiv m\cdot 2^{6} \pmod{10^{6}}}\)
Zostało nam policzyć \(\displaystyle{ 2^{a} \mod 5^{6}}\). To teraz zgodnie z tw. Eulera fajnie by było się zająć \(\displaystyle{ a \mod \varphi \left(5^{6}\right)}\), czyli \(\displaystyle{ 5^{b} \mod 4\cdot 5^{5}}\). To teraz znów z chińskiego twierdzenia o resztach wystarczy policzyć \(\displaystyle{ 5^{b} \mod 4=1}\) i \(\displaystyle{ 5^{b} \mod 5^{5}=0}\), bo \(\displaystyle{ b \ge 5}\). Oczywiście \(\displaystyle{ 5^{5}}\) jest rozwiązaniem naszego układu, a w myśl chińskiego twierdzenia o resztach, z dokladnością do \(\displaystyle{ 4 \cdot 5^{5}}\) ten układ więcej rozwiązań nie ma. Zatem \(\displaystyle{ 5^{b} \equiv 5^{5} \pmod{4\cdot 5^{5}}}\), czyli \(\displaystyle{ 5^{b}= 4k \cdot 5^{5}+5^{5}}\), gdzie \(\displaystyle{ k\in\ZZ}\).
Wracamy do twierdzenia Eulera:
\(\displaystyle{ 2^{a}=2^{5^{b}}=2^{4k \cdot 5^{5}+5^{5}}=\left(2^{\varphi\left(5^{6}\right)}\right)^{k}\cdot 2^{5^{5}}\equiv 1 \cdot 2^{5^{5}}\equiv 2^{5^{5}} \pmod{5^{6}}}\)
Ta część zadania sprowadza się już tylko do względnie sprytnego obliczenia \(\displaystyle{ 2^{5^{5}} \mod 5^{6}=c}\).
Jak już to zrobimy, to zostanie nam układ:
\(\displaystyle{ \begin{cases} 2^{a} \equiv 0 \pmod{2^{6}} \\ 2^{a} \equiv c \pmod{5^{6}} \end{cases}}\)
Z pierwszego równania wnioskujemy, że \(\displaystyle{ 2^{a} = 2^{6} \cdot m}\). Jak podstawimy to do drugiego równania, to mamy:
\(\displaystyle{ 2^{6} \cdot m \equiv c \pmod{5^{6}} \Leftrightarrow m \equiv 2^{-6} \cdot c \pmod{5^{6}}}\)
To zostało jeszcze żmudne zadanie by policzyć \(\displaystyle{ 2^{-6} \pmod{5^{6}}}\). Ale możemy zwyczajnie policzyć w pamięci \(\displaystyle{ 2^{-1} \mod 15625 = 7813}\) (wiesz dlaczego?), a potem wynik podnieść do szóstej potęgi, czyli \(\displaystyle{ m\equiv 7813^{6} \cdot c \pmod{5^{6}}}\), co należy policzyć.
Jak już to będziemy mieli, to \(\displaystyle{ 2^{a} \equiv m\cdot 2^{6} \pmod{10^{6}}}\)