zadatak tipa koje su zadnje dvije znamenke broja

[ecan]

Recimo primjer sa vježbi:

Zadnje dvije znamenke broja 3^1000

Ne razumijem zadnji korak kada bi iz sustava kongruencija:
3^2=1(mod 4) i 3^20=1(mod 25) trebao zaključiti da su zadnje dvije znamenke 01 ?

Ako netko može pojasniti pliz?

[ecan]

Vidim da je preko 50 ljudi pogledalo ovaj post, zar stvarno nitko ne zna ili ste lijeni odgovoriti?

[daisy]

iz ovog 3^2=1(mod4) imaš x=1(mod 4). i isto za 3^20=1(mod 25) imas da je x=1(mod25) sustav rješavaš normalno, kako smo i radili, dobiješ da ti je x1=1, x2=19, pa je x=25*1+4*19=101 i imas x=1001(mod100) tj x=1(mod100), a taj 1 ti je ostatak pri dijeljenju. kako trebas zadnje 2 znam, onda pišeš da je to '01'.

[ponovno]

Znam da je vec puno proslo od kada je ovaj problem objavljen, ali eto mozda bude od koristi nekome...

1.)Iz 3^2=1(mod 4) dobijemo 3^400=1(mod 4) te isto tako iz 3^20=1(mod 25) dobijemo 3^400=1(mod 25) primjenom tvrdnje: ako x=y(mod m) onda x^k=y^k(mod m)

2.) jer vrijedi: x|a i y|a te x i y relativno prosti onda xy|a (za dokaz pogledati ovdje: https://math.stackexchange.com/questions/2092325/if-x-divides-z-y-divides-z-and-x-and-y-are-relatively-prime-then) u ovom zadatku imamo 4|3^400 -1 i 25 | 3^400 -1 i 4 i 25 su rel. prosti pa vrijedi 4*25=100| 3^400 -1, tj. 3^400=1(mod 100)

3.) zadnje dvije znamenke broja x su ostatak r koji dobijemo pri dijeljenju broja x sa 100, dakle nas zanima broj r u kongruenciji x=r(mod 100), a kod nas je x 3^400 i kako smo dobili 3^400=1(mod 100) slijedi da je ostatak 1, tj. zadnje dvije znamenke su 0 i 1