find remainder using modulo arithmetic 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?
 A: $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}$
A: The OP should verify the following fact:
If $n \equiv 0 \text{ mod 11}$ and $n \equiv r \text{ mod 13}$ then $n^2  \equiv n \cdot r \text{ mod 143}$ and $n^2  \equiv r^2 \text{ mod 13}$.
We plan on employing an algorithm and it makes sense to make a couple of preliminary calculations:
$\; 55^2 \equiv 55 \cdot 3 \equiv 22 \text{ mod 143}$
$\; 22^2 \equiv 22 \cdot 9 \equiv 55 \text{ mod 143}$
Now that is a stroke of luck!
$55^{142} \equiv 22^{71} \equiv 22 \cdot 22^{70} \equiv 22 \cdot 55^{35} \equiv 22 \cdot 55 \cdot 55^{34} \equiv 22 \cdot 55  \cdot 22^{17}  \equiv$
$\quad  22 \cdot 55  \cdot 22 \cdot 22^{16} \equiv  22 \cdot 55  \cdot 22 \cdot 55^{8}  \equiv$
$\quad 22 \cdot 55  \cdot 22 \cdot 22^{4} \equiv 22 \cdot 55  \cdot 22 \cdot 55^{2}  \equiv$
$\quad 22 \cdot 55  \cdot 22 \cdot 22 \equiv^\text{algorithm complete / now applying discretionary techniques}$
$\quad 55 \text{ mod 143}$
