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

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
dotMaciej
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 22 sty 2014, o 22:47
Płeć: Mężczyzna
Lokalizacja: Sierakowice
Podziękował: 1 raz

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

Post 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ć? ;/
Awatar użytkownika
Mistrz
Użytkownik
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

Post 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}}\)
ODPOWIEDZ