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.
 A: 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. 
A: You can compute $3^{2^n} \text{ mod } 95$ quickly by computing $3^2$, $3^4=(3^2)^2$, $3^8=(3^4)^2$, ...
From that, you can compute $3^n$ by represeting $n$ as a sum of powers of 2 (i.e., $n$'s binary representation). If $n = 2^{k_n} + \ldots + 2^{k_1}$, then $3^n = 3^{2^{k_n}}\cdot\ldots\cdot3^{2^{k_1}}$.
I've whipped up a ruby script to do that computation and get 66. Didn't test much, though, so verify before you use that result for anything important!
