Calculate $11^{35} \pmod{71}$

Using Fermat's Little Theorem:

$11^{70}=(11^{35})^2\equiv 1 \mod(71)$,

so, we only need to find elements in $\mathbb{Z}_{71}$ that square to 1. Since 71 is a prime, $\mathbb{Z}_{71}$ is a field, so the only elements that square to 1 are 1 and -1. We can knock out the possibility of $11^{35}\equiv 1 \mod(71)$ by using quadratic reciprocity.

From Fermat's little theorem (and the fact that quadratic polynomials have at most two roots mod a prime), you can conclude that $11^{35} \equiv \pm 1\mod 71$. Euler's criterion can narrow this down to the correct answer of -1, but if you haven't yet studied quadratic reciprocity the very useful technique of repeated squaring offers a more low-brow approach to computing this exponent.

Modulo 71 we have

$$\begin{align*} 11^1 &\equiv 11\\ 11^2 &\equiv 50\\ 11^4 &\equiv (50)^2 \equiv 15\\ 11^8 &\equiv (15)^2 \equiv 12\\ 11^{16} &\equiv (12)^2 \equiv 2\\ 11^{32} &\equiv 4. \end{align*}$$

That's as many powers of $11$ as we need: $$11^{35} \equiv 11^{32}11^2 11^1 \equiv 4\cdot 50 \cdot 11 \equiv 70 \mod 71$$

If you know that $11^{4} \equiv 15 \bmod 71$ (taken from user7530 above), then:

$$ 11^{35} \equiv (-60)^{35} \equiv -(4 \cdot 15)^{35} \equiv -(2^2 \cdot 11^4)^{35} \equiv -(2 \cdot 11^2)^{70} \equiv -1 \bmod 71 $$