# Calculating $17^{14}\mod{71}$ using Fermat's little theorem

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?

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

$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}\;.$$

-
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

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.

-

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.

-