Witam
Jak obliczyć takie coś: \(\displaystyle{ 3^{259} \ mod \ 252}\) ?
modulo
-
Artist
- Użytkownik
- Posty: 865
- Rejestracja: 27 sty 2008, o 21:07
- Płeć: Mężczyzna
- Lokalizacja: Brodnica
- Podziękował: 27 razy
- Pomógł: 239 razy
modulo
Na piechotkę z kongruencji:
\(\displaystyle{ 3\equiv3 \ mod \ 252}\)
\(\displaystyle{ 3^{2}\equiv9 \ mod \ 252}\)
\(\displaystyle{ 3^{4}\equiv81 \ mod \ 252}\)
\(\displaystyle{ 3^{8}\equiv9 \ mod \ 252}\)
\(\displaystyle{ 3^{16}\eqiuv81 \ mod \ 252}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ 3^{259}=3*3^{2}*3^{256}\equiv3*9*81=3^{7}\equiv 171\ mod \ 252}\)
EDIT: Źle przepisałem wartości.
\(\displaystyle{ 3\equiv3 \ mod \ 252}\)
\(\displaystyle{ 3^{2}\equiv9 \ mod \ 252}\)
\(\displaystyle{ 3^{4}\equiv81 \ mod \ 252}\)
\(\displaystyle{ 3^{8}\equiv9 \ mod \ 252}\)
\(\displaystyle{ 3^{16}\eqiuv81 \ mod \ 252}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ 3^{259}=3*3^{2}*3^{256}\equiv3*9*81=3^{7}\equiv 171\ mod \ 252}\)
EDIT: Źle przepisałem wartości.
Ostatnio zmieniony 16 wrz 2008, o 20:17 przez Artist, łącznie zmieniany 1 raz.
-
Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
modulo
\(\displaystyle{ 252=2^2 3^2 7 \\ 3^{259} \equiv (-1)^{259} \equiv -1 \equiv 3 \ (mod \ 4) \\ 3^{259} \equiv 0 \ (mod 3^2) \\ 3^{259} \equiv 27^{86} 3 \equiv (-1)^{86}\cdot 3 = 3 \ (mod 7)}\)
Z chińskiego twierdzenia o resztach: \(\displaystyle{ 3^{259} \equiv 3 \ (mod 28) 3^{252} \equiv 0 \ (mod 9) 3^{259} \equiv 171 \ (mod 252)}\).
Z chińskiego twierdzenia o resztach: \(\displaystyle{ 3^{259} \equiv 3 \ (mod 28) 3^{252} \equiv 0 \ (mod 9) 3^{259} \equiv 171 \ (mod 252)}\).