How to find the remainder of ${289 \times 144^{25}}$ divided by ${71^{71}}$ I am solving this question.
Finding the remainder of 
$$\frac{289\times 144^{25}}{71^{71}}$$
This is how I have tried solving it. First it can be simplified to $\frac{17^2 \times 2 ^{50} \times 3^{25}}{71^{71}}$. Now if we use Euler Totient rule we get for $\phi(71^{71}) = 71(1-\frac{1}{71}) = 70 $. 
For,
$$ \frac{a^{\phi(n)}}{n}$$
I would get remainder as $1$. 
I can't proceed from this point. Can someone help me to find out the remainder and where I went wrong? 
EDIT : My totient rule was wrong. It's  $\phi(71^{71}) = 71^{71}(1-\frac{1}{71}) = 71^{70} \times 70 $. 
EDIT #2 :  tried solving this in a different way.
$$ \frac{289}{71} \times \frac{144^{25}}{71^{70}}$$
For the first separated division we get $289 \equiv 5 \bmod 71$. Now further simplifying the second,
$$\frac{12^{50}}{71^{70}} = \left( \frac{12^5}{71^7} \right)^{10} = \left( \frac{12}{71} \right)^{70} \times \frac{1}{12^{20}}$$
Now I get $12 \equiv -59 \bmod 71$. 
I'm stuck again here. 

${289 \times 144^{25}} \approx 2.6 \times 10^{56} <  2.8 \times 10^{131}  \approx 71^{71}$. 
So the remainder is ${289 \times 144^{25}}$.
