What is $5^{11\times31}$ congruent to in modulo $11\times 13$?

Question

My attempt:

$$ 5^{11\cdot31} ≡5^{341} \pmod {143}$$

Using FLT where $$a^{p-1} ≡ 1 \pmod p$$

I get

$$≡(5^{142})(5^{142})5^{57} \pmod {143}$$ $$≡5^{57} \pmod {143}$$

This is where I'm stuck.

Answer 1

Note that $5^{11\cdot 31} \equiv 5^{1\cdot1} \equiv 5 \pmod{11}$, by Fermat's little theorem. Also, note that $5^{11\cdot 31} \equiv 5^5 \equiv 625 \cdot 5 \equiv 5 \pmod{13}$, again by Fermat's little theorem. Then by the Chinese remainder theorem, we must have that $5^{11\cdot 31} \equiv 5 \pmod{11 \cdot 13}$.

Answer 2

While you cannot use Fermat's little theorem, you can use its generalization, Euler's theorem, which states that, if $a$ is relatively prime to $n$, then $a^{\phi(n)}\equiv 1 \pmod n$. The method you were using will then work to start you on your way.