Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
1  
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
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. –  user5137 Nov 9 '11 at 6:47
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.