oblicz reszte z dzielenia

[matematyka0]

oblicz resztę z dzielenia \(\displaystyle{ 3^{1105}}\)przez 20 .
Dobrze zrobiłam, sprawdzi ktoś??

czyli trzeba obliczyć \(\displaystyle{ 3^{1105}}\) w \(\displaystyle{ \mathbb{Z}_{20}}\)

\(\displaystyle{ \phi(20)=20(1-\frac{1}{2})(1-\frac{1}{2})(1-\frac{1}{5})=4}\)
\(\displaystyle{ 3^4=1 \w \ \mathbb{Z}_{20}}\)

\(\displaystyle{ 3^{1105}=3^{4 \cdot 276+1}=3^1=3}\)

i co dalej?
która to reszta 3 czy to 4 ? czy wgl coś innego?
prosze o pomoc, z góry dziękuje

[squared]

A dlaczego uważasz, że niby \(\displaystyle{ 4}\) to rozwiązanie?

Oczywiście odpowiedź to \(\displaystyle{ 3}\).

Patrząc jednak na Twoje rozpiski mam wrażenie, że nie do końca wiesz co się dzieje i dlaczego.

[matematyka0]

masz racje...próbowałam to robic na tej zasadzie co znalazłam taki "schemat" ...choc juz w nastepnym przykładzie i nie wyszło...
\(\displaystyle{ 2^{9980}}\) przez 63
robiąc tak samo
\(\displaystyle{ \phi(63)=...=24}\)
\(\displaystyle{ 2^{24}=1 w Z_{63}}\)
i potem wyszło mi \(\displaystyle{ 2^{9980}=...2^{20}=1048576}\)
ale przeciez to za duzo... to jak zrobic ten przykład?

[squared]

\(\displaystyle{ \phi(63)=...=24}\)

Nie, \(\displaystyle{ \varphi(63)=36}\)

Nie zawsze robimy wszystko, na "schemat", gdyż

\(\displaystyle{ 64 = 2^5 = 1 \mod 63 \\
5|9980 \rightarrow 9980=5k \\
2^{5k} = 1 \mod 63 \rightarrow 2^{9980}=1 \mod 63}\)

[matematyka0]

skąd sie wzieło 36 , anie 24?

[squared]

\(\displaystyle{ \varphi(63)=63\left( 1-\frac{1}{7}\right)\left( 1-\frac{1}{3}\right)= 36}\)

[matematyka0]

ok dziekuje i tą resztą jest 5?

[squared]

\(\displaystyle{ 2^{9980}=1 \mod 63}\), a to wprost z definicji oznacza, że resztą z dzielenia jest \(\displaystyle{ 1}\).