znaleźć ostatnie dwie cyfry liczby
\(\displaystyle{ 2^{999}}\)
z góry dzięki
ostatnie dwie cyfry liczby 2^999
-
jacekvool
- Użytkownik
- Posty: 31
- Rejestracja: 28 cze 2005, o 19:59
- Płeć: Mężczyzna
- Lokalizacja: skądinąd
ostatnie dwie cyfry liczby 2^999
Ostatnio zmieniony 4 gru 2006, o 22:33 przez jacekvool, łącznie zmieniany 1 raz.
-
rahl
ostatnie dwie cyfry liczby 2^999
wyjdzie chyba 08 ale zrobilem to w dosc malo elegancki i nudny sposob - ostatnia liczba sie powtarza co 4 n, a przedostatnia co 20 n , liczysz np reszte z dzielenia przez 4 i 20 i powinno wyjsc, ale jak juz mowilem, pewnie jest ladniejszy i szybszy sposob rozwiazania
-
spajder
- Użytkownik
- Posty: 735
- Rejestracja: 7 lis 2005, o 23:56
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 2 razy
- Pomógł: 133 razy
ostatnie dwie cyfry liczby 2^999
mozna bezpośrednio z kongruencji. Na kalkulatorze sprawdzasz, że \(\displaystyle{ 2^{10}\equiv 24\pmod{100}}\), podnosząc do kwadratu
\(\displaystyle{ 2^{20}\equiv 76\pmod{100}}\),
podnosząc to znów do kwadratu dostajesz:
\(\displaystyle{ \left(2^{20}\right)^2\equiv 76\pmod{100}}\)
czyli ogólniej:
\(\displaystyle{ \left(2^{20}\right)^{2^n}\equiv 76\pmod{100}}\) gdzie \(\displaystyle{ n\in \mathbb{N}}\)
zachodzi więc:
\(\displaystyle{ \left(2^{20}\right)^{32}=2^{640}\equiv ft(2^{20}\right)^{16}=2^{320}\equiv 76\pmod{100}}\)
\(\displaystyle{ 2^{20}\cdot 2^{640}\cdot 2^{320}=2^{980}\equiv 76\pmod{100}}\)
\(\displaystyle{ 2^{10}\cdot 2^{980}=2^{990}\equiv 24\cdot 76\equiv 24\pmod{100}}\)
a korzystając z tego, że \(\displaystyle{ 2^9=512\equiv 12\pmod{100}}\) masz:
\(\displaystyle{ 2^{9}\cdot 2^{990}=2^{999}\equiv 12\cdot 24\equiv 88\pmod{100}}\)
\(\displaystyle{ 2^{20}\equiv 76\pmod{100}}\),
podnosząc to znów do kwadratu dostajesz:
\(\displaystyle{ \left(2^{20}\right)^2\equiv 76\pmod{100}}\)
czyli ogólniej:
\(\displaystyle{ \left(2^{20}\right)^{2^n}\equiv 76\pmod{100}}\) gdzie \(\displaystyle{ n\in \mathbb{N}}\)
zachodzi więc:
\(\displaystyle{ \left(2^{20}\right)^{32}=2^{640}\equiv ft(2^{20}\right)^{16}=2^{320}\equiv 76\pmod{100}}\)
\(\displaystyle{ 2^{20}\cdot 2^{640}\cdot 2^{320}=2^{980}\equiv 76\pmod{100}}\)
\(\displaystyle{ 2^{10}\cdot 2^{980}=2^{990}\equiv 24\cdot 76\equiv 24\pmod{100}}\)
a korzystając z tego, że \(\displaystyle{ 2^9=512\equiv 12\pmod{100}}\) masz:
\(\displaystyle{ 2^{9}\cdot 2^{990}=2^{999}\equiv 12\cdot 24\equiv 88\pmod{100}}\)
-
kuch2r
- Użytkownik
- Posty: 2302
- Rejestracja: 18 paź 2004, o 18:27
- Płeć: Mężczyzna
- Lokalizacja: Wrocław/Ruda Śląska
- Podziękował: 9 razy
- Pomógł: 408 razy
ostatnie dwie cyfry liczby 2^999
mozna inaczej:
skorzystajmy z twierdzenie Eulera :
\(\displaystyle{ a^{\phi(p)}\equiv 1 (modp)}\) gdzie \(\displaystyle{ NWD(a,p)=1}\), i \(\displaystyle{ \phi(p)}\)- funkcja Eulera
Oznaczmy sobie przez \(\displaystyle{ x=2^{999}}\)
Wiemy, ze
\(\displaystyle{ x\equiv0 (mod4)}\)
oraz na mocy twierdzenie Eulera:
\(\displaystyle{ 2^{\phi(25)}\equiv 1 (mod25)\\2^{20}\equiv 1 (mod25)}\)
Zatem:
\(\displaystyle{ x=2^{999}\equiv 2^{19}\equiv 13(mod 25)}\)
Rozwazmy teraz uklad kongruencji:
\(\displaystyle{ \left\{\begin{array}{l}x\equiv 0 (mod4)\\x\equiv 13 (mod25)\end{array}}\)
Rozwiazaniem tego ukladu jest \(\displaystyle{ x=88}\)
skorzystajmy z twierdzenie Eulera :
\(\displaystyle{ a^{\phi(p)}\equiv 1 (modp)}\) gdzie \(\displaystyle{ NWD(a,p)=1}\), i \(\displaystyle{ \phi(p)}\)- funkcja Eulera
Oznaczmy sobie przez \(\displaystyle{ x=2^{999}}\)
Wiemy, ze
\(\displaystyle{ x\equiv0 (mod4)}\)
oraz na mocy twierdzenie Eulera:
\(\displaystyle{ 2^{\phi(25)}\equiv 1 (mod25)\\2^{20}\equiv 1 (mod25)}\)
Zatem:
\(\displaystyle{ x=2^{999}\equiv 2^{19}\equiv 13(mod 25)}\)
Rozwazmy teraz uklad kongruencji:
\(\displaystyle{ \left\{\begin{array}{l}x\equiv 0 (mod4)\\x\equiv 13 (mod25)\end{array}}\)
Rozwiazaniem tego ukladu jest \(\displaystyle{ x=88}\)