|
[quote="slon"]da li netko moze objasniti sljedeci zadatak : odredi zadnje dvije znamenke u decimalnom zapisu broja 3^400.
u skripti pise rijesenje, ali mi nije jasno [/quote]
Probat cu ja, iako nisam siguran da znam objasniti puno bolje nego sto sam napisao u skripti.
Trazi se ostatak pri dijeljenju broja 3^400 sa 100.
100=4*25, pa to mozemo rijesiti tako da nadjemo ostatak pri dijeljenju tog broja sa 4 i sa 25. Pomoci ce nam to da znamo koja potencija broja 3 daje ostatak 1 pri dijeljenju sa m (to je phi(m)). Tako je 3^2 == 1 (mod 4) i 3^20 == 1 (mod 25). Prvu kongruenciju dignemo na potenciju 200, a drugu na potenciju 20. Dobijemo 3^400 == 1 (mod 4) i 3^400 == 1 (mod 25). Stoga je 3^400 == 1 (mod 100). Broj koji daje ostatak 1 pri dijeljenju sa 100, zavrsava znamenkama 01.
Drugi primjer (zadatak) iz skripte: isto pitanje za broj 2^1000.
Sada imamo 2^1000 = 0 (mod 4) i 2^1000 == 1 (mod 25).
Trazi se rjesenje sustava kongruencija x==0 (mod 4), x==1 (mod 25).
Kineskim teorem o ostacima (ili ispitivanjem redom brojeva 1, 1+25, 1+2*25, 1+3*25, ... koji od njih je == 0 (mod 4)), dobije se da je x==76 (mod 100), pa 2^1000 zavrsava znamenkama 76.
| slon (napisa): | da li netko moze objasniti sljedeci zadatak : odredi zadnje dvije znamenke u decimalnom zapisu broja 3^400.
u skripti pise rijesenje, ali mi nije jasno |
Probat cu ja, iako nisam siguran da znam objasniti puno bolje nego sto sam napisao u skripti.
Trazi se ostatak pri dijeljenju broja 3^400 sa 100.
100=4*25, pa to mozemo rijesiti tako da nadjemo ostatak pri dijeljenju tog broja sa 4 i sa 25. Pomoci ce nam to da znamo koja potencija broja 3 daje ostatak 1 pri dijeljenju sa m (to je phi(m)). Tako je 3^2 == 1 (mod 4) i 3^20 == 1 (mod 25). Prvu kongruenciju dignemo na potenciju 200, a drugu na potenciju 20. Dobijemo 3^400 == 1 (mod 4) i 3^400 == 1 (mod 25). Stoga je 3^400 == 1 (mod 100). Broj koji daje ostatak 1 pri dijeljenju sa 100, zavrsava znamenkama 01.
Drugi primjer (zadatak) iz skripte: isto pitanje za broj 2^1000.
Sada imamo 2^1000 = 0 (mod 4) i 2^1000 == 1 (mod 25).
Trazi se rjesenje sustava kongruencija x==0 (mod 4), x==1 (mod 25).
Kineskim teorem o ostacima (ili ispitivanjem redom brojeva 1, 1+25, 1+2*25, 1+3*25, ... koji od njih je == 0 (mod 4)), dobije se da je x==76 (mod 100), pa 2^1000 zavrsava znamenkama 76.
|
