[MTF] Reszta z dzielenia wykładnika o ogromnej potędze
: 22 sty 2014, o 23:05
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ć? ;/
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ć? ;/