Wyznaczyć resztę z dzielenia...

[Finarfin]

Wyznaczyć resztę z dzielenia liczby
\(\displaystyle{ 100^{2006}}\) przez 19. Z jakiego twierdzenia korzystamy?


PRosiłbym o pomoc...myślałem, że to nie będzie trudne (:

[Intact]

Musisz znalezc co ile reszta sie powtarza.

\(\displaystyle{ r = \frac{5}{19} eq 0,26}\)

[palazi]

Tradycyjnie na modulo:
\(\displaystyle{ 100 \equiv 5(mod 19)}\) więc \(\displaystyle{ 100^2 \equiv 25(mod 19) \equiv 6(mod 19)}\)
\(\displaystyle{ 100^4 \equiv (100^2)^2 (mod 19) \equiv 36(mod 19) \equiv 17(mod 19)}\)
I tak dochodzimy do momentu, że: \(\displaystyle{ 100^9 \equiv 100 (100^4)^2 (mod 19) \equiv 5 (17)^2 (mod 19) \equiv 1 (mod 19)}\)
Więc teraz:
\(\displaystyle{ 100^{2006} = (100^{9})^{222} 10^{8} \equiv (1)^{ 222} (10^4)^2 (mod 19) \equiv (17)^2 (mod 19) \equiv 4 (mod 19)}\)
Więc resztą z dzielenia przez 19 jest liczba \(\displaystyle{ 4}\).

[Elvis]

Z twierdzenia Eulera (100 i 19 są względnie pierwsze):
\(\displaystyle{ 100^{\phi(19)} \equiv 1 \ (mod 19) \\
100^{18} \equiv 1 \ (mod 19)}\)