想問一條mod數

1. 123=41*3, 456=3*152
2. 456^789=0 (mod 3)
456^789= 5^789 (mod 41)
=125^263 (mod 41)
= 2^263=(2^7)^37*2^4= 5^37*16 (mod 41)
= 125^12*5*16 = 2^12*(-2) (mod 41)
=2^7* 2^5*(-2)= 5*32*(-2)= 8 (mod 41)
3. 456^789=8 (mod 41) so 456^789= 41*a+8
then 456^789=41*(3b+r)+8 (r=0,1,2)
while 456^789=0 (mod 3) so 41(3b+r)+8=0 (mod 3)
then 2r-1=0 (mod 3), thus r=2
456^789=41(3b+2)+8= 123b+ 90
thus 456^789=90 (mod 123)

(other method by Fermat's little thm)
Fermat: 5^40=1 (mod 41), then 5^760=1 (mod 41)
so 456^789= 5^789=5^29 (mod 41)
= (125^9)*25 =2^9*25 (mod 41)
= (2^7)*(2^2)*25 = 5*4*25=8 (mod 41)