Reszta z dzielenia

Kanodelo · Post autor: **Kanodelo** » 1 cze 2011, o 17:27

Wyznacz resztęz dzielenia liczby \(\displaystyle{ 2^{9768}}\) przez \(\displaystyle{ 3}\) oraz \(\displaystyle{ 3^{73}}\) przez \(\displaystyle{ 4}\).

Errichto · Post autor: **Errichto** » 1 cze 2011, o 17:33

Rozpisz reszty z dzielenia \(\displaystyle{ 2^1, \ 2^2, \ 2^3, \ ...}\) aż znajdziesz zależność.

abc666 · Post autor: **abc666** » 1 cze 2011, o 17:34

\(\displaystyle{ 2^2\equiv 1 \pmod{3}\\
\left( 2^2 \right ) ^{4884} \equiv 1 \pmod{3}}\)
Z drugim prawie tak samo zrób.

smigol · Post autor: **smigol** » 1 cze 2011, o 22:43

Errichto pisze:Rozpisz reszty z dzielenia \(\displaystyle{ 2^1, \ 2^2, \ 2^3, \ ...}\) aż znajdziesz zależność.

A potem udowodnij, że taka zależność rzeczywiście zachodzi.

Kanodelo · Post autor: **Kanodelo** » 2 cze 2011, o 16:10

abc666 pisze: \(\displaystyle{ \left( 2^2 \right ) ^{4884} \equiv 1 \pmod{3}}\)

Niestety nie mam pojęcia jak to dalej rozwiązać, jeszcze jak by była normalna liczba to z algorytmu euklidesa, a jak jest kwadrat to już nie wiem

Errichto · Post autor: **Errichto** » 2 cze 2011, o 16:11

Jeśli coś daje resztę 1 to podniesione do dowolnej potęgi naturalnej będzie dawało resztę 1.

abc666 · Post autor: **abc666** » 2 cze 2011, o 16:16

Niestety nie mam pojęcia jak to dalej rozwiązać,

no to już koniec, przecież
\(\displaystyle{ 4884\cdot 2= 9768}\)

Kanodelo · Post autor: **Kanodelo** » 2 cze 2011, o 16:25

A drugie to ma być \(\displaystyle{ 3^{73}=x (mod 4)}\)?
Bo tutaj już się tak ładnie nie zrobi z kwadratem jak tam

abc666 · Post autor: **abc666** » 2 cze 2011, o 16:29

\(\displaystyle{ 3^2\equiv 1 \pmod{4} \\
\left(3^2 \right) ^{36} \equiv 1 \pmod{4}\qquad |\cdot 3 \\
3^{73}\equiv 3 \pmod{4}}\)