Zad.
Znaleźć dwie ostatnie cyfry liczby:
\(\displaystyle{ 7^{9^{9^{9^{9}}}}}\).
Doszedłem do tego, że \(\displaystyle{ 9^{9^{9^{9}}} \equiv 89 (\mod{100})}\)( korzystałem z przykładu, który znalazłem w internecie), czyli \(\displaystyle{ 7^{10k+9}=7^{10k} \cdot 7^9 \equiv 49^k \cdot 7 (\mod{100})}\)
No i nie wiem jak dalej to zrobić
Bardzo proszę o pomoc.
Ostatnie cyfry liczby
-
BettyBoo
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Ostatnie cyfry liczby
A skunt takie cuś wziąłeś?
Masz obliczyć \(\displaystyle{ 7^{9^{9^{9^{9}}}} \mod100}\). Wiadomo (tw Eulera), że \(\displaystyle{ a^{\varphi(100)}\equiv 1 \mod100}\) o ile NWD(a,100)=1. Ponieważ dla 7 tak jest oraz \(\displaystyle{ \varphi(100)=100\frac{1}{2}\frac{4}{5}=40}\), to trzeba obliczyć \(\displaystyle{ {9^{9^{9^{9}}}} \mod40}\) żeby wiedzieć, jak się upraszcza potęga siódemki.
No i teraz ten sam bajer - wiadomo, że \(\displaystyle{ a^{\varphi(40)}\equiv 1 \mod40}\) o ile NWD(a,40)=1. Ponieważ dla 9 tak jest oraz \(\displaystyle{ \varphi(40)=40\frac{1}{2}\frac{4}{5}=16}\), to trzeba obliczyć \(\displaystyle{ {9^{9^{9}}} \mod16}\). Aby to zrobić, trzeba obliczyć \(\displaystyle{ {9^{9}} \mod \varphi(16)}\). To już łatwo zrobić, bo \(\displaystyle{ {9^{9}} \equiv 1^9\equiv 1 \mod 8}\).
A więc
\(\displaystyle{ {9^{9^{9}}} \equiv 9\mod16}\)
a stąd
\(\displaystyle{ {9^{9^{9^{9}}}}\equiv 9^9 \equiv 1 \mod40}\) (to trzeba obliczyć, co nie jest zbyt skomplikowane, jako, że \(\displaystyle{ 9^2\equiv 1\mod40}\))
a więc ostatecznie
\(\displaystyle{ 7^{9^{9^{9^{9}}}} \equiv 7^9\mod100}\), co też trzeba obliczyć.
Pozdrawiam.
Masz obliczyć \(\displaystyle{ 7^{9^{9^{9^{9}}}} \mod100}\). Wiadomo (tw Eulera), że \(\displaystyle{ a^{\varphi(100)}\equiv 1 \mod100}\) o ile NWD(a,100)=1. Ponieważ dla 7 tak jest oraz \(\displaystyle{ \varphi(100)=100\frac{1}{2}\frac{4}{5}=40}\), to trzeba obliczyć \(\displaystyle{ {9^{9^{9^{9}}}} \mod40}\) żeby wiedzieć, jak się upraszcza potęga siódemki.
No i teraz ten sam bajer - wiadomo, że \(\displaystyle{ a^{\varphi(40)}\equiv 1 \mod40}\) o ile NWD(a,40)=1. Ponieważ dla 9 tak jest oraz \(\displaystyle{ \varphi(40)=40\frac{1}{2}\frac{4}{5}=16}\), to trzeba obliczyć \(\displaystyle{ {9^{9^{9}}} \mod16}\). Aby to zrobić, trzeba obliczyć \(\displaystyle{ {9^{9}} \mod \varphi(16)}\). To już łatwo zrobić, bo \(\displaystyle{ {9^{9}} \equiv 1^9\equiv 1 \mod 8}\).
A więc
\(\displaystyle{ {9^{9^{9}}} \equiv 9\mod16}\)
a stąd
\(\displaystyle{ {9^{9^{9^{9}}}}\equiv 9^9 \equiv 1 \mod40}\) (to trzeba obliczyć, co nie jest zbyt skomplikowane, jako, że \(\displaystyle{ 9^2\equiv 1\mod40}\))
a więc ostatecznie
\(\displaystyle{ 7^{9^{9^{9^{9}}}} \equiv 7^9\mod100}\), co też trzeba obliczyć.
Pozdrawiam.
-
Hatcher
- Użytkownik
- Posty: 175
- Rejestracja: 1 maja 2008, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 57 razy
- Pomógł: 14 razy
Ostatnie cyfry liczby
Mam dwa pytania:
dlaczego tu jest \(\displaystyle{ \mod 8}\), a nie \(\displaystyle{ \mod6}\) przecież \(\displaystyle{ \varphi(16)=6}\)BettyBoo pisze: (...) Aby to zrobić, trzeba obliczyć \(\displaystyle{ {9^{9}} \mod \varphi(16)}\). To już łatwo zrobić, bo \(\displaystyle{ {9^{9}} \equiv 1^9\equiv 1 \mod 8}\).
I skąd się wzięły te przejścia ? Bo nie bardzo kumaBettyBoo pisze:
\(\displaystyle{ {9^{9^{9}}} \equiv 9\mod16}\)
a stąd
\(\displaystyle{ {9^{9^{9^{9}}}}\equiv 9^9 \equiv 1 \mod40}\) (to trzeba obliczyć, co nie jest zbyt skomplikowane, jako, że \(\displaystyle{ 9^2\equiv 1\mod40}\))
a więc ostatecznie
\(\displaystyle{ 7^{9^{9^{9^{9}}}} \equiv 7^9\mod100}\), co też trzeba obliczyć.
Pozdrawiam.
-
BettyBoo
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Ostatnie cyfry liczby
Ad Q1: \(\displaystyle{ \varphi(16)=16\frac{1}{2}=8}\)
Ad Q2: Jeśli chodzi o te przejścia, to wyjaśnię pierwsze, pozostałe biorą się z analogicznych rozważań.
Ustaliliśmy, że \(\displaystyle{ 9^9\equiv 1 \mod\varphi(16)\ \Leftrightarrow \ 9^9=1+k\varphi(16)}\). Z drugiej strony, ustaliliśmy, że \(\displaystyle{ 9^{\varphi(16)}\equiv 1 \mod 16}\), a więc
\(\displaystyle{ {9^{9^{9}}} \equiv 9^{1+k\varphi(16)}\equiv 9^1(9^{\varphi(16)})^k\equiv 9^1\cdot 1^k\equiv 9^1\mod16}\)
Czyli tak naprawdę masz coś takiego: \(\displaystyle{ 9^9\equiv 1 \mod \varphi(16)\ \Leftrightarrow \ {9^{9^{9}}} \equiv 9^1 \mod16}\)
Pozdrawiam.
Ad Q2: Jeśli chodzi o te przejścia, to wyjaśnię pierwsze, pozostałe biorą się z analogicznych rozważań.
Ustaliliśmy, że \(\displaystyle{ 9^9\equiv 1 \mod\varphi(16)\ \Leftrightarrow \ 9^9=1+k\varphi(16)}\). Z drugiej strony, ustaliliśmy, że \(\displaystyle{ 9^{\varphi(16)}\equiv 1 \mod 16}\), a więc
\(\displaystyle{ {9^{9^{9}}} \equiv 9^{1+k\varphi(16)}\equiv 9^1(9^{\varphi(16)})^k\equiv 9^1\cdot 1^k\equiv 9^1\mod16}\)
Czyli tak naprawdę masz coś takiego: \(\displaystyle{ 9^9\equiv 1 \mod \varphi(16)\ \Leftrightarrow \ {9^{9^{9}}} \equiv 9^1 \mod16}\)
Pozdrawiam.