Wyznacz dwie ostatnie cyfry

[max123321]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 3^{2016}}\).

Jak to zrobić?

[Premislav]

Innymi słowy, mamy obliczyć \(\displaystyle{ 3^{2016}\pmod{100}}\).
Zauważ, że \(\displaystyle{ 100=4\cdot 25}\) i \(\displaystyle{ \NWD(4,25)=1}\).
Mamy \(\displaystyle{ \phi(4)=2, \ \phi(25)=20}\), toteż z twierdzenia Eulera otrzymujemy
\(\displaystyle{ 3^2\equiv 1\pmod{4}}\) (zwróć uwagę, że \(\displaystyle{ \NWD(3,4)=1}\))
oraz
\(\displaystyle{ 3^{20}\equiv 1\pmod{25}}\) (zwróć uwagę, że \(\displaystyle{ \NWD(3,25)=1}\)).
Zatem
\(\displaystyle{ 3^{2016}=(3^2)^{1008}\equiv 1\pmod{4}}\)
oraz
\(\displaystyle{ 3^{2016}=\left(3^{20}\right)^{100}\cdot 3^{16}\equiv 3^{16}\pmod{25}}\)
a nietrudno zauważyć, że \(\displaystyle{ 3^3\equiv 2\pmod{25}}\), więc
\(\displaystyle{ 3^{16}=(3^3)^5\cdot 3\equiv 21\pmod{25}}\), otrzymaliśmy zatem:
\(\displaystyle{ 3^{2016}\equiv 1\pmod{4}\\ 3^{2016}\equiv 21\pmod{25}}\)
ale z chińskiego twierdzenia o resztach układ
\(\displaystyle{ \begin{cases} x\equiv 1\pmod{4} \\ x\equiv 21\pmod{25}\end{cases}}\)
ma jedyne rozwiązanie modulo \(\displaystyle{ 4\cdot 25}\) i łatwo stwierdzić, że jest to \(\displaystyle{ 21}\).
Ostatecznie \(\displaystyle{ 3^{2016}\equiv 21\pmod{100}}\), czyli szukane dwie ostatnie cyfry to \(\displaystyle{ 21}\).

[Bratower]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 3^{2016}}\)
\(\displaystyle{ \NWD(3,100)=1\\\phi(100)=40}\)
Z tw. Eulera
\(\displaystyle{ 3^{40}\equiv1\bmod100\\3^{2016}=3^{40\cdot50+16}\equiv3^{16}\bmod100\\3^{16}=9^{8}=81^{4}\equiv61\cdot61\equiv\boxed{21}\bmod100}\)
Premislav czy moje rozwiązanie jest również poprawne?

[Premislav]

Tak. Może niektórzy by się zainteresowali, dlaczego \(\displaystyle{ 81^4\equiv 61^2\pmod{3}}\) itd. ale to łatwo wynika ze wzoru na kwadrat sumy.

[Bratower]

ale z chińskiego twierdzenia o resztach układ
\(\displaystyle{ \begin{cases} x\equiv 1\pmod{4} \\ x\equiv 21\pmod{25}\end{cases}}\)
ma jedyne rozwiązanie modulo \(\displaystyle{ 4\cdot 25}\) i łatwo stwierdzić, że jest to \(\displaystyle{ 21}\).

Tak przy okazji jak znajdujesz rozwiązanie takiego układu?(skoro łatwo stwierdzić )
Z tego co mi wiadomo to rozwiązanie jest w przedziale od \(\displaystyle{ \left\langle 0;100\right\rangle}\)(dokładnie jedno?), teraz bym wypisał liczby spełniające pierwsze równanie czyli \(\displaystyle{ x_{1}\in\left\{ 1,5,9,13,17,{\red 21},25,29,33,37,41,45,49,53,57,61,65,69,73,77,81,85,89,93,97\right\}\\x_{2}\in\left\{{\red 21},46,71,96 \right\}}\)
Czyli oba te układy spełnia liczba \(\displaystyle{ 21}\) i ona jest rozwiązaniem?
Czy jest jakiś sprawniejszy sposób w znalezieniu danej liczby?
Premislav

[Premislav]

Są algorytmy, które pozwalają takie rozwiązanie wygenerować, tutaj akurat najsprawniej było własnie wypisać parę i zgadnąć (przy czym lepiej zacząć od tych, które dają resztę \(\displaystyle{ 21}\) z dzielenia przez \(\displaystyle{ 25}\), bo ich jest mniej po prostu).
O tej porze na pewno bym się pomylił przy rozpisywaniu szczegółów algorytmu, ale tutaj masz:

... ongruencji

[max123321]

Dzięki.

A tak swoją drogą idąc tym tropem próbuję wyznaczyć dwie ostatnie cyfry liczby \(\displaystyle{ 2^{2016}}\). Proszę o sprawdzenie czy tak jest dobrze:
\(\displaystyle{ 2^{2016}\mod 100=2^{2016} \mod 4 \cdot 25}\)
\(\displaystyle{ 2^{2016} \mod 4=4^{1008}=0\mod 4}\)
\(\displaystyle{ \varphi (25)=20}\) więc
\(\displaystyle{ 2^{2016}=(2^{20})^{100} \cdot 2^{16}=2^{16} \mod 25=256^2 \mod 25=6^2 \mod 25=11}\).
Czyli mamy układ kongruencji:
\(\displaystyle{ x \mod 4=0}\)
\(\displaystyle{ x \mod 25 =11}\)
i z chińskiego twierdzenia o resztach zgadujemy, że jedyne rozwiązanie to \(\displaystyle{ 36}\). A zatem dwie ostatnie cyfry danej liczby to \(\displaystyle{ 36}\).
Czy tak jest dobrze? Ewentualnie czy można było to jakoś sprawniej zrobić?

[Premislav]

Jest OK. Można też zauważyć, że
\(\displaystyle{ 2^{12}=4096\equiv -4\pmod{100}}\), zaś \(\displaystyle{ 2016=12^2\cdot 14}\), więc
\(\displaystyle{ 2^{2016}=(4096)^{12\cdot 14}\equiv (-4)^{12\cdot 14}\pmod{100}}\)
a dalej
\(\displaystyle{ (-4)^{12\cdot 14}=2^{24\cdot 14}=(2^{12})^{28}\equiv (-4)^{28}\pmod{100}}\)
i w końcu
\(\displaystyle{ (-4)^{28}=2^{56}=2^8\cdot (2^{12})^4\equiv 256^2\pmod{100}}\),
a ze wzoru skróconego mnożenia na kwadrat sumy (\(\displaystyle{ 256=250=6\ldots}\)) wynika, ze to wynosi \(\displaystyle{ 36.}\) Ale nie każdy pamięta duże potęgi dwójki (choć te są jeszcze dość małe).