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 (:
Wyznaczyć resztę z dzielenia...
-
- Użytkownik
- Posty: 175
- Rejestracja: 6 wrz 2006, o 21:58
- Płeć: Mężczyzna
- Lokalizacja: Łapy/Białystok
- Podziękował: 2 razy
- Pomógł: 37 razy
Wyznaczyć resztę z dzielenia...
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}\).
\(\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
- Użytkownik
- Posty: 765
- Rejestracja: 17 paź 2004, o 18:09
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 89 razy
Wyznaczyć resztę z dzielenia...
Z twierdzenia Eulera (100 i 19 są względnie pierwsze):
\(\displaystyle{ 100^{\phi(19)} \equiv 1 \ (mod 19) \\
100^{18} \equiv 1 \ (mod 19)}\)
\(\displaystyle{ 100^{\phi(19)} \equiv 1 \ (mod 19) \\
100^{18} \equiv 1 \ (mod 19)}\)