Using Fermat's little theorem

Solution 1:

$12^{772}=12^{71\cdot 10+62}\equiv 12^{10+62}=12^{71+1}\equiv 12\cdot 12=144\equiv 2$ mod $71$. So $a=2$.

Alternately,

$12^{772}=12^{70\cdot 11+2}\equiv 12^2=144\equiv 2$ mod $71$.

The first one uses the form $a^p\equiv a$ mod $p$ and the second uses the form $a^{p-1}\equiv 1$ mod $p$ if $gcd(a,p)=1$ where $p$ is prime.

Solution 2:

Hint $\rm\ \ X^N \equiv X\ \ \Rightarrow\ \ X^{A + B\ N + C\ N^{\Large 2} + \cdots} \equiv\ X^{A + B + C + \cdots}\ (mod\ N)$

Note $\, $ This is simply "casting out orders" - a cyclic group analog of casting out nines. Namely, $\rm\ X^{N-1} = 1\ \Rightarrow\ X^N = X\ $ thus we can map $\rm\ N\to 1$ when calculating integral powers of $\rm\:X\:$.

When $\rm\:X\:$ has order dividing $\:9\:,\:$ then it amounts precisely to casting out nines from its exponents. For example, $\rm\ mod\ 27:\ (-2)^9 \equiv 1\ \Rightarrow\ (-2)^{721} \equiv -2\ \ $ since $\rm\ \ 721\equiv 7+2+1\equiv 1\ \:(mod\ 9)$