Find remainder when $777^{777}$ is divided by $16$ 
Find remainder when $777^{777}$ is divided by $16$.

$777=48\times 16+9$. Then $777\equiv 9 \pmod{16}$. 
Also by Fermat's theorem, $777^{16-1}\equiv 1 \pmod{16}$ i.e $777^{15}\equiv 1 \pmod{16}$.
Also $777=51\times 15+4$. Therefore, 
$777^{777}=777^{51\times 15+4}={(777^{15})}^{51}\cdot777^4\equiv 1^{15}\cdot 9^4 \pmod{16}$ leading to $ 81\cdot81 \pmod{16} \equiv 1 \pmod{16}$.
But answer given for this question is $9$. Please suggest.

Fermat's theorem will only work with primes.($16$ is not a prime)
But, it can be solved by the general formula, using Euler's theorem.
Since $gcd(9,16)=1, 9^{\phi(16)} \equiv 1 (mod 16)$. Since $16=2^4, \phi(16)=8$.
Therefore, $9^8 \equiv 1 (mod 16)$, and we have $777^{777} \equiv 9^{777} \equiv 9^9 \equiv 9*9^8 \equiv 9 (mod 16)$.
