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