Find the remainder when $2^{837259739}+ 3^{23456}$ is divided by $31$ for $2$ I was able to solve it by going from 
$$(2^5)^{167451947} \cdot 2^4$$ which is congruent to $1(\mod 31)$ and $16(\mod31)$ respectively.  
I just don't know if I'm doing the $3$ part correctly.  Would $(3^3)^{7818} \cdot 3^2$ be $27(\mod31)$ and $9(\mod31)$ respectively?
 A: Below are a few easy ways to calculate $\,3^{\large 23456}\!\equiv 3^{\large 23456\bmod\color{#0a0}{30}}\!\pmod{\!31}\ $ by little $\rm\color{#0a0}{Fermat}$.
First note $\!\bmod\color{#0a0}{30}\!:\ 23456 \equiv 23430+26\equiv\color{#c00}{26}\,$ by $\,3,10\mid 23430\,$ by $\,3\mid 2\!+\!3\!+\!4\!+\!3$
So $\ \ 3^{\large 3}\equiv -2^{\large 2}\overset{(\ \ )^{\LARGE 8}}\Longrightarrow\,3^{\large 24}\equiv 2(2^{\large 5})^{\large 3}\equiv 2$ $\,\overset{\large \times 3^{\Large 2}}\Longrightarrow 3^{\large\color{#c00}{26}} \equiv 18,\, $ using only easy mental arithmetic.
Or $\,\ 3^{\large\color{#0a0}{30}}\!\equiv 1\,\Rightarrow\,3^{\large\color{#c00}{26}}\!\equiv \dfrac{1}{3\cdot 3^{\large 3}}\equiv \dfrac{1}{3(-4)}\equiv\dfrac{3}{-36}\equiv  \dfrac{3}{-5}\equiv \dfrac{18}{-30}\equiv 18\ $ by Gauss's algorithm
Alternatively by factoring above $\,  \dfrac{-1}3\,\dfrac{1}4\equiv \dfrac{30}3\,\dfrac{32}4\equiv 10(8)\equiv 18,\, $  easy mentally all $3$ ways!
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
