Show that $76^{2019} \equiv 45 \pmod{101}$ Using Euler's theorem I see that $76^{2019} = 76^{19} \pmod{101}$, how do I proceed?
 A: Here is an approach that requires minimum computation. We have:
$$76^{19} \equiv (-25)^{19} \equiv -5^{38} \pmod{101}$$
How we have that by quadratic reciprocity:
$$\left( \frac{5}{101} \right)=\left( \frac{5}{101} \right) \cdot \left( \frac{1}{5} \right) = \left( \frac{5}{101} \right) \cdot \left( \frac{101}{5} \right)=(-1)^{\frac{101-1}{2} \cdot \frac{5-1}{2}}=1$$
So $5$ is the quadratic residue modulo $101$ and therefore $5^{50} \equiv 1 \pmod{101}$. So we can write:
$$-5^{38} \equiv -5^{-12} \equiv -25^{-6}\pmod{101}$$
And since $25 \cdot (-4) \equiv -100 \equiv 1 \pmod{101}$ we have $25^{-1} \equiv -4 \pmod{101}$ and therefore:
$$-25^{-6} \equiv -(-4)^6 \equiv -4^6 \equiv -4096 \equiv 45\pmod{101}$$
A: $101$ is prime, so $76^{100}\equiv1\pmod{101}$ by Fermat's little theorem, so 
$76^{2019}\equiv76^{19}\pmod{101}$. 
$76^2\equiv19\pmod{101}$.  $76^4\equiv58\pmod{101}$. $76^8\equiv 31\pmod{101}$.  $76^{16}\equiv 52\pmod{101}$.  
Therefore $76^{19}\equiv76^{16}76^2 76^1\equiv52\times19\times76\equiv45\pmod{101}$.
