MHB Find Remainder of $40^{110}$ and $3^{1000}$ Divided by 37 and 26

[Albert1]

(1)dividing $40^{110} \,\, by \,\, 37$

(2)dividing $3^{1000} \,\, by \,\, 26$

 

[kaliprasad]

(1)dividing $40^{110} \,\, by \,\, 37$

(2)dividing $3^{1000} \,\, by \,\, 26$

Spoiler

(1)
we have
40 = 3 mod 37
so we need
$3^{110}$ mod 37
as 37 is prime so we have as per flt
$3^{36} = 1$ mod 37
so
$3^{110} = 3^{3*36+2} = (3^{36})^{3} * 3^2$ mod 37 = 9 mod 37 = 9 that is the ans

so $40^{110}$ devided by 37 remainder is 9

(2)
$3^{3} = 27 = 1$ mod 26
hence
$3^{999} = (3^3)^{333} = 1$ mod 26
so $3^{1000}$ mod 26 = 3 so remainder divided by 26 is 3