Question

PLEASE HELP!Calculate $40^{13} \pmod{85}.$

Answer 1

In this type of calculations, we decompose 13 by checking the lowest powers of the base, that is 40. for example we check 40^2, or 40^3 and compare it to 85

Notice

40*40*40=64,000

so we check how many time does 85 fit into 64,000:

64,000/85=752.94

85*753=64,005;       64000-64,005=-5

this means that 

$40^{3} =-5\pmod{85}$

thus

$40^{13} =40^{3*4+1}={(40^{3})}^{4}*40=(-5)^{4}*40 \pmod{85}=\\\\625*40\pmod{85}=(7*85+30)*40\pmod{85}=30*40\pmod{85}\\\\=1200\pmod{85}=(14*85+10)\pmod{85}=10\pmod{85}$


Answer: 10 (mod85)

Remark, the set of all solutions is:

{......-75, 10, 95, .....}, that is 85k +10