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
- Mistrz
- Użytkownik
- Posty: 637
- Rejestracja: 10 sie 2009, o 09:56
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz / Warszawa
- Podziękował: 19 razy
- Pomógł: 135 razy
[MTF] Reszta z dzielenia wykładnika o ogromnej potędze
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}}\)
\(\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}}\)