Find the remainder when $169\times144^{25}$ is divided by $13^{4}$ 
Find the remainder when $169\times144^{25}$ is divided by $13^{4}$

Meanwhile I reduced it to
$\dfrac{13^{2}\times 144^{25}}{13^{4}} \\
=\dfrac{144^{25}}{13^{2}} \\ 
=\dfrac{12^{50}}{13^{2}} \\ 
$
and Euler function of $13^{2}$ is coming to be $156$
I look for a short and simple way.

The problem boils down to computing $144^{25}\pmod{13^2}$, or $25^{25}\pmod{13^2}$, or $25^{26}\pmod{13^2}$, or $25^{13}\pmod{13^2}$. By the binomial theorem:
$$ 25^{13} = (26-1)^{13} = \sum_{k=0}^{13}\binom{13}{k}(-1)^{13-k}(26)^k $$
but for every $k\geq 2$ we have $26^k\equiv 0\pmod{13^2}$ and $\binom{13}{1}(26)^1\equiv 0\pmod{13^2}$ too, so
$$ 25^{13}\equiv -1\pmod{13^2},\qquad 25^{26}\equiv 1\pmod{13^2},$$
$$ 144^{25}\equiv -25^{25}\equiv 27\pmod{13^2} $$
and:

$$ 13^2\cdot 144^{25} \equiv \color{red}{4563}\pmod{13^4}.$$

