What is $65^{3903}$ $(\text{mod }81)$? How do you find $65^{3903}$ $(\text{mod }81)$?
I found that $65^{3903} \equiv 2 \ \text{ (mod } 3)$ with Fermat's Little Theorem. Is that the right first step? I don't know how I would apply the Chinese remainder theorem here.
 A: $65^{3903}\equiv(-16)^{3903}\equiv-2^{4\times3903}\equiv-2^6\equiv-64\equiv17\bmod81$
since $2^{54}\equiv81$ by Euler's theorem (a generalization of Fermat's, for composite numbers),
and $4\times3903=54\times289+6$.
The Chinese remainder theorem doesn't apply, 
since $81$ doesn't have non-trivial factors that are relatively prime.
A: We can't apply FLT since $81$ is not prime.
We can proceed by steps as follows
$$65\equiv -16  \implies \color{blue}{65^2\equiv 256 \equiv 13}  \implies 65^4 \equiv7\mod 81$$
$$\implies 65^6 \equiv 91 \equiv10\implies 65^7 \equiv-160 \equiv2 \implies \color{blue}{65^{56}\equiv 13 \mod 81}$$
therefore
$$65^{54}\equiv 1 \mod 81 \implies 65^{3903} \equiv 65^{15} \equiv 17 \mod 81$$
A: Apply $a^{\phi(n)} = 1 \pmod n$ by Fermat's little theorem, as generalised by Euler, provided $\gcd(a,n)=1$, which is indeed the case for $a=65$ and $n=81$. Of course $\phi(81)=3^4(1-\frac13)= 3^3\times 2 = 54$, so $$65^{54} = 1 \pmod{81}$$ 
Now $3903 = 15 + 72\times54$ so
$$65^{3903} = 65^{15} \pmod{81}$$
Now apply some squaring/multiplying to see that this equals $17$.
A: You probably need to ramp up Fermat's Theorem to Euler's Theorem.  You have $\phi(81) = 54$, and
$3903 \equiv 15 \pmod{54}$, so your problem reduces to $65^{15} \pmod{81}$.
Second, you might notice that $65 \equiv -16 \equiv -2^4 \pmod{81}$, so you have $-2^{4\cdot15} \equiv -2^{60} \equiv -2^6 \equiv -64 \equiv 17 \pmod{81}$
since $60 \equiv 6 \pmod{54}.$ 
Anyway, Euler's Theorem.
