Calculate $11^{35} \pmod{71}$ Calculate $11^{35} \pmod{71}$
I have:
$= (11^5)^7 \pmod{71}$
$=23^7 \pmod{71}$
And I'm not really sure what to do from this point..
 A: 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.
A: 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$$
A: 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 $$
