high power congruences finding $x$ trying to solve:
$$x^{13} \equiv 11 \pmod{135}$$
I came to the fact that $x = 11^{59}$ but its in mod $72$ and needs to be converted to mod $135$
any suggestions? I'm not sure how to change it to mod $135$ with such a large number
 A: $135 = 3^3 \cdot 5$, so $\varphi(135) = 72$. Using Euclid, you find that
$$
1 = 13 \cdot (-11) + 72 \cdot 2 = 13 \cdot 61 + 72 \cdot (-11), 
$$
so 
$$
x \equiv (x^{13})^{61} \equiv 11^{61} \pmod{135}.
$$
PS Once again, apologies for the initial mistake in this late-night post (never again!), and thanks to Gerry Myerson and user62340 for calling my attention to it.
To finish the calculation by hand, it is probably safer to compute first
$$
11^{11} = 11 \cdot 11^2 \cdot 11^{8} \equiv 41 \pmod{135}, 
$$
and then the inverse $56$ of $41$ modulo $135$, which is the required solution.
A: If $\rm\: x^{13}\equiv 11\,\ (mod\ 5\cdot27)\:$ then the same congruence holds mod $5$ and $27$, and we can use CRT (Chinese Remainder Theorem) to recombine the two solutions. It turns out to be very simple:
$\rm\quad\ mod\,\ 5\!:\ x^4\equiv 1,\:$ so $\rm\,x \equiv x (x^4)^3 \equiv x^{13}\equiv 11\equiv \color{#C00}1.\ \ $ Next $\ \phi(27) = 18,\:$ hence
$\rm\quad\ mod\ 27\!:\ 1 \equiv x^{18}\equiv x^{13} x^5 \equiv 11 x^5\:$ so $\rm\,x^5 \equiv \dfrac{1}{11}\equiv \dfrac{55}{11}\equiv 5\equiv 2^5\Rightarrow\:x\equiv \color{#0A0}2\  $ (unique, see Note)
$\rm\Rightarrow mod\ 5\cdot 27\!:\,\  x \equiv \color{#0A0}2 + 27\,\left[\dfrac{\color{#C00}1\!-\!\color{#0A0}2}{27}\ mod\ 5\right]\! \equiv 56,\ $ by  $\rm\ mod\ 5\!:\, \dfrac{-1}{27}\equiv \dfrac{4}2 \equiv 2,\ $ using Easy CRT.
Note $\,\ 5$'th roots are unique $\rm\,mod\ 27\:$ since $\rm\, (5,\phi(27)) = (5,18) = 1,\:$ so $\rm\:n\equiv 1/5\ mod\ 18\:$ exists, hence  $\rm\,x^5 = y^5\:\Rightarrow x\equiv x^{5n}\equiv y^{5n}\equiv y\,$ since $\rm\,5n\equiv 1\,\ (mod\ 18).$
