Answer :
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
[tex]40^{3} =-5\pmod{85}[/tex]
thus
[tex]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}[/tex]
Answer: 10 (mod85)
Remark, the set of all solutions is:
{......-75, 10, 95, .....}, that is 85k +10
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
[tex]40^{3} =-5\pmod{85}[/tex]
thus
[tex]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}[/tex]
Answer: 10 (mod85)
Remark, the set of all solutions is:
{......-75, 10, 95, .....}, that is 85k +10