Let us say that there is a number $899$ which is the product of $29$ and $31$.
I want to work out the following: $$245^3 \pmod{899}$$
I know there is a way of doing it with $\phi(29)$ and $\phi(31)$ but I am not too sure. How do I break it down and do it more efficiently by hand?
Thank you
First we solve the problem $\pmod {29}$ and $\pmod {31}$. We get $$245\equiv 13\pmod {29}\implies 245^2\equiv 169\equiv 24\pmod {29}\implies 245^3\equiv 13\times 24\equiv 22\pmod {29}$$
Thus we know that $$245^3=22+29n$$ for some integer $n$.
A similar computation $\pmod {31}$ shows $$245^3\equiv 4 \pmod {31}$$
We want to compute $245^3 \pmod {29\times 31}$. By the Chinese Remainder Theorem there is a unique residue class $a$ such that $$a\equiv 22\pmod {29}\quad \&\quad a\equiv 4\pmod {31}$$
Thus, given that $245^3=22+29n$ we need to solve for $n\pmod {31}$ such that $$22+29n\equiv 4 \pmod {31}\implies 18\equiv -29n\equiv 2n\pmod {31}\implies n\equiv 9 \pmod {31}$$
Finally, we see that $$245^3\equiv 22+29\times 9\equiv 283\pmod {899}$$ and we are done.
As a check, I suggest doing the problem directly. First check that $245^2\equiv 691\pmod {899}$ and then that $$245^3\equiv 691\times 245\equiv 283\pmod {899}$$.