0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Why is $42^{10}\equiv 1 \pmod{13}$? And have you ever hear of Fermat's Little Theorem? $\endgroup$ – fleablood Dec 7 '18 at 1:47
  • 1
    $\begingroup$ Your method is correct, but as @fleablood points out you started with a wrong result $\endgroup$ – rsadhvika Dec 7 '18 at 1:49
  • $\begingroup$ Actually your last step should be helpful : $$42^3\equiv 1\pmod{13}$$ $\endgroup$ – rsadhvika Dec 7 '18 at 1:51
  • 2
    $\begingroup$ 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\ $ $\endgroup$ – Bill Dubuque Dec 7 '18 at 1:51
  • $\begingroup$ $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. $\endgroup$ – fleablood Dec 7 '18 at 1:53
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.