szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 17:32 
Użytkownik

Posty: 163
Lokalizacja: Polska
Oblicz (102^{75} + 1)^{35} \pmod{111}

Pomoże ktoś z tym?

-- 10 cze 2018, o 19:00 --

Zrobiłem coś takiego:

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


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


(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)?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 19:32 
Użytkownik

Posty: 12307
Lokalizacja: Presslaw
Mamy
111=3\cdot 37
oraz
102\equiv 0\pmod{3}\\102^{75}+1\equiv 1\pmod{3}\\(102^{75}+1)^{35}\equiv 1\pmod{3}
a także
102\equiv 28\pmod{37}
i z małego twierdzenia Fermata dostajemy
28^{36}\equiv 1\pmod{37}, gdyż liczba 37 jest pierwsza i nie dzieli 28.
Zatem
102^{75}\equiv 28^3\pmod{37}
oraz 28^3=(37-9)^3\equiv (-9)^3\pmod{37}
zaś (-9)^3=-729=-20\cdot 37+11\equiv 11\pmod{37},
czyli
102^{75}\equiv 11\pmod{37}\\102^{75}+1\equiv 12\pmod{37},
natomiast
z małego twierdzenia Fermata
12\cdot 12^{35}=12^{36}\equiv 1\pmod{37}, czyli
r_{37}(12^{35}) jest elementem odwrotnym do 12 w \ZZ_{37},
a ten znajdujemy z rozszerzonego algorytmu Euklidesa:
37=3\cdot 12+1\\ 1=37-3\cdot 12\\ 1=37 \cdot(-11
)+34\cdot 12
i poszukiwanym elementem odwrotnym jest 34, tj.
12^{35}\equiv 34\pmod{37}
Otrzymaliśmy układ:
\begin{cases} n\equiv 1\pmod{3} \\ n\equiv 34\pmod{37} \end{cases},
stąd
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.
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 19:36 
Administrator

Posty: 22534
Lokalizacja: Wrocław
cis123 napisał(a):
Oblicz (102^{{\red 75}} + 1)^{35} \pmod{111}
cis123 napisał(a):
Zrobiłem coś takiego:

102^{{\red 70}} \pmod{111}

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

JK
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2018, o 20:02 
Użytkownik

Posty: 163
Lokalizacja: Polska
ehh powinno być 70.

Ale mimo wszystko dzięki za pokazanie sposobu rozwiązania
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiąż kongruencję - zadanie 2  0jejku  1
 Rozwiąż kongruencję  Minnie_  14
 rozwiąż kongruencję - zadanie 3  pastorczyk  4
 Rozwiąż kongruencje - zadanie 6  karl153  2
 rozwiąż kongruencję - zadanie 8  lilith123  1
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl