What is the least residue mod $N = 95$ of $3^{1.1 \cdot 10^{43}}$? This is a practice problem. Since $5 \cdot 19$ are prime factors of $95$ I tried to break it into two congruence equations and use CRT, but I can't seem to work this out. By Fermat's little theorem we have $3^5 \equiv 3 \pmod 5$, but squaring that multiple times cannot be the solution because then we have to square the RHS of the equation, which is some ridiculous thing. Also $3^{19} \equiv 3 \pmod{19}$, which doesn't help much (I think?) and $3^{18} \equiv 1 \pmod{19}$ which also doesn't help much (I think...). Some help would be appreciated.

By Fermat's Theorem (twice) $3^{36}\equiv 1\pmod{95}$. Now we want what $1.1\times 10^{43}$ is congruent to modulo $36$. This big number modulo $4$ is very tame. And modulo $9$, we are looking at $11\times 10^{42}$. Note that $10$ is very nice modulo $9$. 
Remark: It is often more efficient to work separately modulo the prime power factors, in this case $5$ and $19$. Modulo $5$, there is no problem, since $3^4\equiv 1\pmod{5}$ and $4$ divides our exponent. So now we examine the exponent modulo $18$. The exponent, modulo $18$, is congruent to $2$. So our power $3^N$ is congruent to $1$ modulo $5$, and to $3^2$ modulo $19$. An easy CRT problem, done by inspection. 
