Find the least nonnegative residue of: $42^{173} modulo 13$

Question

I can across this question:

Find the least nonnegative residue of:

$42^{173} modulo 13$

I have done the following:

$42^{10} ≡ 1 mod 13$

$42^{173} = 42^{10 (17) +3}$

$ 42^{173} ≡ 42^{3} mod 13$

$ 42^{3} = 74088$

We can write $74088 = a(13)+r$

so $74088 = 5699(13)+1$

Therefore,

$ 42^{173} ≡ 42^{3}= 74088=5699(13)+1 ≡ 1 mod 13$

Is this the correct way to solve it?

Answer 1

By Fermat's little theorem, $42^\color{blue}{12}\cong1\pmod{13}$.

So, $42^{173}=({42^{12}})^{14}\cdot 42^5\cong42^5\pmod{13}\cong3^5\pmod{13}\cong243\pmod{13}\cong9\pmod{13}$.

Answer 2

I don't know why you think $42^{10} \equiv 1 \pmod{13}$.

But note: $42=39 + 3 \equiv 3\pmod {13}$ and $3^3 = 27 \equiv 1 \pmod {13}$

So $42^{173} \equiv 3^{3*57+2} \equiv (3^3)^{57}*3^2 \equiv 1*9\equiv 9 \pmod {13}$.

By Fermat's little theorem we know $42^{12} \equiv 1 \mod 13$ and we could do $42^{12*14 +5}\equiv 42^5\equiv 3^5 = 243 \equiv 9\pmod{13}$.