Rozwiąż kongruencję

[cis123]

Oblicz \(\displaystyle{ (102^{75} + 1)^{35} \pmod{111}}\)

Pomoże ktoś z tym?-- 10 cze 2018, o 19:00 --Zrobiłem coś takiego:

\(\displaystyle{ 102^{70} \pmod{111} = (-9)^{70} \pmod{111} = 3^{140} \pmod{111} = (3^{10})^{14} \pmod{111} = \\ = (-3)^{14} \pmod{111} = (3^{7})^{2} \pmod{111} = 78^{2} \pmod{111} = 90}\)


\(\displaystyle{ 102^{70} + 1 \pmod{111} = 91}\)


\(\displaystyle{ (102^{70} + 1)^{35} \pmod{111} = 91^{35} \pmod{111} = (91^{5})^{7} \pmod{111} = \\ = 19^{7} \pmod{111} = 61}\)

Czy to jest w ogóle dobrze? I czy istnieje jakaś lepsza metoda (ta nie należy do przyjemnych rachunkowo)?

[Premislav]

Mamy
\(\displaystyle{ 111=3\cdot 37}\)
oraz
\(\displaystyle{ 102\equiv 0\pmod{3}\\102^{75}+1\equiv 1\pmod{3}\\(102^{75}+1)^{35}\equiv 1\pmod{3}}\)
a także
\(\displaystyle{ 102\equiv 28\pmod{37}}\)
i z małego twierdzenia Fermata dostajemy
\(\displaystyle{ 28^{36}\equiv 1\pmod{37}}\), gdyż liczba \(\displaystyle{ 37}\) jest pierwsza i nie dzieli \(\displaystyle{ 28}\).
Zatem
\(\displaystyle{ 102^{75}\equiv 28^3\pmod{37}}\)
oraz \(\displaystyle{ 28^3=(37-9)^3\equiv (-9)^3\pmod{37}}\)
zaś \(\displaystyle{ (-9)^3=-729=-20\cdot 37+11\equiv 11\pmod{37}}\),
czyli
\(\displaystyle{ 102^{75}\equiv 11\pmod{37}\\102^{75}+1\equiv 12\pmod{37}}\),
natomiast
z małego twierdzenia Fermata
\(\displaystyle{ 12\cdot 12^{35}=12^{36}\equiv 1\pmod{37}}\), czyli
\(\displaystyle{ r_{37}(12^{35})}\) jest elementem odwrotnym do \(\displaystyle{ 12}\) w \(\displaystyle{ \ZZ_{37}}\),
a ten znajdujemy z rozszerzonego algorytmu Euklidesa:
\(\displaystyle{ 37=3\cdot 12+1\\ 1=37-3\cdot 12\\ 1=37 \cdot(-11
)+34\cdot 12}\)
i poszukiwanym elementem odwrotnym jest \(\displaystyle{ 34}\), tj.
\(\displaystyle{ 12^{35}\equiv 34\pmod{37}}\)
Otrzymaliśmy układ:
\(\displaystyle{ \begin{cases} n\equiv 1\pmod{3} \\ n\equiv 34\pmod{37} \end{cases}}\),
stąd
\(\displaystyle{ n=(102^{75} + 1)^{35} \pmod{111}=34}\)

Wolfram mi to sprawdził, więc raczej jest dobrze, a Twoje jest źle, ale nie chce mi się szukać błędu w rachunkach.

[Jan Kraszewski]

Oblicz \(\displaystyle{ (102^{{\red 75}} + 1)^{35} \pmod{111}}\)

Zrobiłem coś takiego:

\(\displaystyle{ 102^{{\red 70}} \pmod{111}}\)

Mógłbyś się zdecydować...

JK

[cis123]

ehh powinno być 70.

Ale mimo wszystko dzięki za pokazanie sposobu rozwiązania