Question Number 104139 by bobhans last updated on 19/Jul/20

what is remainder when 61^(61)  divided  by 1001

Commented byaurpeyz last updated on 19/Jul/20

how?

Answered by floor(10²Eta[1]) last updated on 19/Jul/20

x≡61^(61) (mod 1001)  61^2 =3721≡718(mod 1001)  61^4 ≡718^2 =515524≡9(mod 1001)  61=4.15+1⇒61^(61) =(61^4 )^(15) .61≡9^(15) .61(mod1001)★  9^4 =6561≡555(mod 1001)  9^5 ≡555.9=4995≡−10(mod 1001)  9^(15) =(9^5 )^3 ≡−1000≡1(mod 1001)  ★9^(15) .61≡61(mod 1001)  ⇒x=61

Answered by OlafThorendsen last updated on 19/Jul/20

61^(61)  = 61.(61^2 )^(30)   61^(61)  = 61.3721^(30)   61^(61)  ≡ 61.718^(30)  [1001]  61^(61)  ≡ 61(718^2 )^(15)  [1001]  61^(61)  ≡ 61×(9)^(15)  [1001]  61