设N=1997的1997次方,那么N的末三位数是多少?我知道要用同余,可是不知道怎么用,

Question

设N=1997的1997次方,那么N的末三位数是多少?我知道要用同余,可是不知道怎么用,

Answer 1

1987≡997(mod1000),
φ(1000)=400,(997,1000)=1,997^400≡1(mod1000)
1997=4*400+397,
N≡997^397(mod1000)
≡997*997^396(mod1000)
≡997*9^198(mod1000)
≡997*729^66(mod1000)
≡997*441^33(mod1000)
≡997*441*441^32(mod1000)
≡997*441*361^8(mod1000)
≡997*441*41^2(mod1000)
≡997*441*681(mod1000)
≡037(mod1000)
所以N的末三位数是037.
设a是1997^1997的末三位数,a≡1997^1997（mod1000）,φ(1000)=400,1997^400≡1(mod1000)
a≡1997^1997≡1997^(4*400+397)≡1997^397(mod1000)
又1997^2≡009(mod1000)
397=2*198+1
a≡1997^397≡1997^(2*198+1)≡9^198*1997 (mod1000)