Dwie ostatnie cyfry liczby
-
95Villain95
- Użytkownik
- Posty: 55
- Rejestracja: 4 paź 2013, o 20:19
- Płeć: Mężczyzna
- Lokalizacja: kosmos
- Podziękował: 1 raz
Dwie ostatnie cyfry liczby
Czyli przy poszukiwaniach dwóch ostatnich cyfr liczby mogę od razu zaczynać od \(\displaystyle{ a ^{20} \equiv 1(mod100)}\)? Wtedy reszta po podzieleniu wykładnika potęgi będzie wynosić \(\displaystyle{ b<20}\). A propos wzoru dwumianowego Newtona, to według Ciebie najlepiej jest już później, po zredukowaniu wyliczać dokładnie tę potęgę w ten sposób \(\displaystyle{ (a+b) ^{12} \equiv {12 \choose 0} \cdot a ^{12}+{12 \choose 1} \cdot a ^{11} \cdot b+...+ {12 \choose 12} \cdot b ^{12}}\)? Trochę wydaje się to czasochłonnym procesem i może miałeś na myśli inny sposób?
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Dwie ostatnie cyfry liczby
Nie, źle mnie zrozumiałeś, to nie tak, że zawsze \(\displaystyle{ a^{20}\equiv 1\pmod{100}}\). Przykładowo dla \(\displaystyle{ a=2}\) to nie działa, bo \(\displaystyle{ 2^{20}=1048576}\)
Po prostu ja rozumowałem tak, że \(\displaystyle{ 123=125-2}\), więc \(\displaystyle{ 123^{k}\equiv (-2)^{k}\pmod{25}}\) oraz \(\displaystyle{ 123=124-1}\), zatem \(\displaystyle{ 123^{k}\equiv(-1)^{k}\pmod{4}}\) i szukałem takiego \(\displaystyle{ k}\), żeby to się zgodziło do \(\displaystyle{ 1}\), korzystając niestety ze sporej liczby, ale informatycy chyba znają potęgi dwójki, więc to nie powinien być problem: \(\displaystyle{ (-2)^{10}=2^{10}\equiv -1\pmod{25}}\). Stąd mi wyszło, że \(\displaystyle{ k=20}\) będzie w tym przypadku odpowiednie.
Jak już to mamy, to dostaniemy \(\displaystyle{ 123^{512}\equiv 123^{12}\pmod{100}}\), a dalej ponieważ \(\displaystyle{ 123\equiv 23\pmod{100}}\), to nasz problem redukuje się do obliczenia
\(\displaystyle{ 23^{12}\pmod{100}}\). A na to jest jednak lepszy sposób:mamy \(\displaystyle{ 23=25-2}\), zatem \(\displaystyle{ 23^{10}\equiv -1\pmod{25}}\) (bo \(\displaystyle{ (-2)^{10}=1024=1025-1}\)), czyli \(\displaystyle{ 23^{10}\equiv -1\pmod{25}}\), a ponieważ \(\displaystyle{ 23\equiv -2\pmod{25},}\) to stąd \(\displaystyle{ 23^{12}\equiv 20\pmod{25}}\). Analogicznie \(\displaystyle{ 23\equiv -1\pmod{4}}\), zatem \(\displaystyle{ 23^{12}\equiv 1\pmod{4}}\). Stąd mamy dwie ostatnie cyfry: \(\displaystyle{ 45}\), gdyż tylko \(\displaystyle{ 20, 45, 70}\) i \(\displaystyle{ 95}\) dają resztę \(\displaystyle{ 20}\) z dzielenia przez \(\displaystyle{ 25}\) spośród liczb dwucyfrowych, zaś pośród nich jest tylko jedna dająca resztę jeden z dzielenia przez cztery.
Ogólnie to wszystko cały czas są mniej czy bardziej sprytne sztuczki, nie znam ogólnej metody, więc jej nie przedstawię.-- 7 cze 2016, o 15:44 --EDIT: pod koniec pomyliłem się w arytmetyce, powinno być \(\displaystyle{ 23^{12}\equiv 21\pmod{25}}\), gdyż \(\displaystyle{ -4\equiv 21}\). Zatem dwie ostatnie cyfry tej liczby tworzą liczbę \(\displaystyle{ 21}\). Przepraszam, nigdy nie umiałem mnożyć i odejmować.
Po prostu ja rozumowałem tak, że \(\displaystyle{ 123=125-2}\), więc \(\displaystyle{ 123^{k}\equiv (-2)^{k}\pmod{25}}\) oraz \(\displaystyle{ 123=124-1}\), zatem \(\displaystyle{ 123^{k}\equiv(-1)^{k}\pmod{4}}\) i szukałem takiego \(\displaystyle{ k}\), żeby to się zgodziło do \(\displaystyle{ 1}\), korzystając niestety ze sporej liczby, ale informatycy chyba znają potęgi dwójki, więc to nie powinien być problem: \(\displaystyle{ (-2)^{10}=2^{10}\equiv -1\pmod{25}}\). Stąd mi wyszło, że \(\displaystyle{ k=20}\) będzie w tym przypadku odpowiednie.
Jak już to mamy, to dostaniemy \(\displaystyle{ 123^{512}\equiv 123^{12}\pmod{100}}\), a dalej ponieważ \(\displaystyle{ 123\equiv 23\pmod{100}}\), to nasz problem redukuje się do obliczenia
\(\displaystyle{ 23^{12}\pmod{100}}\). A na to jest jednak lepszy sposób:mamy \(\displaystyle{ 23=25-2}\), zatem \(\displaystyle{ 23^{10}\equiv -1\pmod{25}}\) (bo \(\displaystyle{ (-2)^{10}=1024=1025-1}\)), czyli \(\displaystyle{ 23^{10}\equiv -1\pmod{25}}\), a ponieważ \(\displaystyle{ 23\equiv -2\pmod{25},}\) to stąd \(\displaystyle{ 23^{12}\equiv 20\pmod{25}}\). Analogicznie \(\displaystyle{ 23\equiv -1\pmod{4}}\), zatem \(\displaystyle{ 23^{12}\equiv 1\pmod{4}}\). Stąd mamy dwie ostatnie cyfry: \(\displaystyle{ 45}\), gdyż tylko \(\displaystyle{ 20, 45, 70}\) i \(\displaystyle{ 95}\) dają resztę \(\displaystyle{ 20}\) z dzielenia przez \(\displaystyle{ 25}\) spośród liczb dwucyfrowych, zaś pośród nich jest tylko jedna dająca resztę jeden z dzielenia przez cztery.
Ogólnie to wszystko cały czas są mniej czy bardziej sprytne sztuczki, nie znam ogólnej metody, więc jej nie przedstawię.-- 7 cze 2016, o 15:44 --EDIT: pod koniec pomyliłem się w arytmetyce, powinno być \(\displaystyle{ 23^{12}\equiv 21\pmod{25}}\), gdyż \(\displaystyle{ -4\equiv 21}\). Zatem dwie ostatnie cyfry tej liczby tworzą liczbę \(\displaystyle{ 21}\). Przepraszam, nigdy nie umiałem mnożyć i odejmować.