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 $17^{14} \pmod{71}$

By Fermat's little theorem:
$17^{70} \equiv 1 \pmod{71}$
$17^{14} \equiv 17^{(70\cdot\frac{14}{70})}\pmod{71}$

And then I don't really know what to do from this point on. In another example, the terms were small enough that I could just simplify down to an answer, but in this example, I have no idea what to do with that $17^{(70\cdot\frac{14}{70})}$

What do I do from here?

share|improve this question
2  
Why not square it out once? $ 17^2 =289 \equiv 5 \pmod{71} $ so you need $ 5^7 \pmod{71} $. A bit of calculation gives $ 5^5 \equiv 1 \pmod{71}.$ –  Ragib Zaman Nov 7 '11 at 7:58
1  
Little Fermat only helps, when the exponent is large (in comparison to the modulus). Search for something else from your toolbox. –  Jyrki Lahtonen Nov 7 '11 at 8:10
    
@RagibZaman How did you get $5^7$? –  Arvin Nov 7 '11 at 8:18
    
@JyrkiLahtonen Do you mean Fermat's wont work on this problem or that there is an easier way? –  Arvin Nov 7 '11 at 8:19
    
Fermat is true, but the point of using it is to subtract an integer multiple of 70 from the exponent. I fail to see how that would help in this case. The others have already shown how to do this. –  Jyrki Lahtonen Nov 7 '11 at 8:21
add comment

3 Answers 3

up vote 3 down vote accepted

$17$ isn’t particularly close to a multiple of $71$, but as Ragib Zaman pointed out, $17^2=289$ is: $289=4\cdot71+5$. Thus, $17^{14}=(17^2)^7=289^7\equiv 5^7\pmod {71}$. At that point you can use brute force, or you might notice that $5^4=625$ is pretty close to $9\cdot71=639$. In fact $625=639-14$, so $5^4\equiv -14\pmod{71}$, $5^5\equiv -70\equiv 1\pmod{71}$, and finally $$17^{14}\equiv 5^7\equiv 5^2\equiv 25 \pmod{71}\;.$$

share|improve this answer
1  
ahhh, I didnt know you could square it like that, but it certainly makes sense that you can. thanks –  Arvin Nov 7 '11 at 8:28
    
@BrianMScott How did you go from $5^5 \equiv 1 \pmod{71}$ to $25 \pmod{71}$? –  Arvin Nov 9 '11 at 5:43
    
@Arvin: $5^7=5^5\cdot 5^2\equiv 1\cdot25\pmod {71}$. –  Brian M. Scott Nov 10 '11 at 8:33
add comment

We have that

$$ 17^{14}\equiv 17^{70} \cdot 17^{14} \equiv 17^{84} $$

or

$$ 17^{14}\equiv 17^{-70} \cdot 17^{14} \equiv 17^{-56} $$

I don't see any of these as especially easy to calculate, as $17^{14} = 289^{7} \equiv 5^{7}$. If you don't have to use Fermat's, I'd suggest going with that.

share|improve this answer
add comment

Here is the computation using an addition chain.

$\qquad 17^2\: \equiv\ 5$

$\qquad 17^3\: \equiv\ 17\cdot 17^2\:\equiv\ 5\cdot 17\ \equiv\ 14$

$\qquad 17^5\: \equiv\ 17^2\cdot 17^3\: \equiv\ 5\cdot 14\ \equiv\: -1$

$\qquad 17^7\: \equiv\ 17^2\cdot 17^5\: \equiv\ 5\:(-1)\ \equiv\: -5$

$\qquad 17^{14} \equiv\ 17^7\cdot 17^7\: \equiv\ (-5)^2\: \equiv\ 25$

See the leftmost path in the tree below.

enter image description here

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.