[Math] find remainder using modulo arithmetic

Question

what is the remainder when $55^{142}$ is divided by 143?

Initially I wanted to use Fermat's little theorem but 143 is not prime. Euler's theorem does not seem to work here either as $(55,143)\neq 1$

The answer is 55.

Any ideas how to proceed?

Answer 1

$55\equiv3\pmod {13}\implies 55^3\equiv 3^3=27\equiv1\pmod{13}$

Method $1:$ As the highest power of $11$ in $55$ is $1,$ let us find $55^{141}\pmod{13}$

$55^{141}=(55^3)^{47}\equiv1^{47}\equiv1\pmod{13}=13c+1$ where $c$ is an integer

$\implies 55^{142}=55\cdot55^{141}=55(1+13c)\equiv55\pmod{13\cdot55}\equiv55\pmod{13\cdot11}$

Method $2:$ We have $55^{142}=55\cdot(55^3)^{47}\equiv3\cdot1^{47}\equiv3\pmod{13}$

and $55^{142}\equiv0\pmod {11}$

Now, using CRT, we can find $55^{142}\equiv 55\pmod {13\cdot11}$