Strona 1 z 1

[MTF] Reszta z dzielenia wykładnika o ogromnej potędze

: 22 sty 2014, o 23:05
autor: dotMaciej
Hejka
Otóz mam za zadanie wyznaczyć resztę z dzielenia \(\displaystyle{ 34^{22234711}}\) przez 41.
41 - l. pierwsza ====> \(\displaystyle{ \left|Z_{41}^{*}\right|}\)=40=fi(41)
NWD(41, 34)=1 ====> \(\displaystyle{ 34^{fi(41)}}\) przystaje do 1(mod41)
\(\displaystyle{ \left[ \frac{22234711}{40} \right]}\) = 555867

\(\displaystyle{ 34^{22234711} = (34^{40})^{555867} \cdot 34^{31}}\)

No i mamy \(\displaystyle{ 1^{555867} \cdot34 ^{31} (mod41)}\)

No i tutaj pojawia się mój problem, bo nie wiem co dalej zrobić z tym:
\(\displaystyle{ 34 ^{31}}\), bo to wiadome, że jeszcze kilka razy podzieli się przez 41, ale jaka będzie reszta? I skąd mogę się tego dowiedzieć? ;/

[MTF] Reszta z dzielenia wykładnika o ogromnej potędze

: 23 sty 2014, o 01:14
autor: Mistrz
Dalej to już chyba ręcznie...
\(\displaystyle{ 34 \equiv -7 \pmod{41} \\ 34^2 \equiv (-7)^2 = 49 \equiv 8 \pmod{41} \\ 34^4 \equiv 8^2=64 \equiv 23 \pmod{41} \\ 34^5 \equiv (-7) \cdot 23 = -161 \equiv 3 \pmod{41} \\ 34^{31} = 34^{30} \cdot 34 = (34^5)^6 \cdot 34 \equiv 3^6 \cdot (-7) = 81 \cdot 9 \cdot (-7) \equiv (-1) \cdot 9 \cdot (-7) = 63 \equiv 22 \pmod{41}}\)