My working so far:
$71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$
Check $a=7$:
$7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$
How do I find $x$? Usually I would use Fermat's little theorem and firstly find $\phi(71)$ except 71 is prime (giving the value as $71-1=70$ but this is a fact that we're trying to prove in the first place!!
I could of course use my calculator to calculate it, but this assumes the numbers aren't too extremely horrible.
How else do you calculate this nicely?