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

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?

• Why is $42^{10}\equiv 1 \pmod{13}$? And have you ever hear of Fermat's Little Theorem? – fleablood Dec 7 '18 at 1:47
• Your method is correct, but as @fleablood points out you started with a wrong result – rsadhvika Dec 7 '18 at 1:49
• Actually your last step should be helpful : $$42^3\equiv 1\pmod{13}$$ – rsadhvika Dec 7 '18 at 1:51
• Hint $\bmod 13\!:\ 42\equiv 3\$ and $\,3^{\large 3}\equiv 1,\$ so $\,3^{\large 173}\equiv 3^{\large 2}\,$ by $\bmod 3\!:\ 173\equiv 1\!+\!7\!+\!3\equiv 2\$ – Bill Dubuque Dec 7 '18 at 1:51
• $42^{10} \not \equiv 1 \mod 13$. You can do $42\equiv 3\pmod{13}$ and $3^3 \equiv 27 \equiv 1 \pmod {13}$. And do what you did. But better if you know FLT. – fleablood Dec 7 '18 at 1:53

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}$$.
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}$$.