# 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..

-

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$$

-

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.

-
See this, please. –  Sasha Nov 9 '11 at 6:29
Sorry, edit made. –  user5137 Nov 9 '11 at 6:33
How do you go from this to 70? –  Arvin Nov 9 '11 at 6:44
How do I go from what to 70? The only reason that 70 shows up is due to the statement of Fermat's Little Theorem: $a^{p-1}\equiv 1 \mod(p)$ if $p$ is prime and $gcd(a,p)=1$. In this particular case, $p=71$ is a prime. –  user5137 Nov 9 '11 at 6:47

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$$

-