6
$\begingroup$

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

  • 0
    See also: http://math.stackexchange.com/questions/81228/how-do-i-compute-ab-bmod-c-by-hand2016-10-06

3 Answers 3

2

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 $

6

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.

  • 1
    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.2011-11-09
3

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$