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?
$\endgroup$ 54 Answers
$\begingroup$$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}\;.$$
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ $\begingroup$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.
In this curious problem, the subgroup of order 5 of $(Z_{71}^*, \cdot)$ is formed by these 5 numbers (5 equivalence classes modulo 71):
$$ \{1, 5, 25, -17, -14\} $$
(When multiplying two, another one comes out of the same subgroup).
This group is isomorphic to the group $ (Z_5, +) $ and contains 4 generators.
The 4 different elements of 1 are generators of $\{1, 5, 25, -17, -14\}$
Using (-17) as a generator of the subgroup of order 5, gives us this order:
$$[1, -17, 5, -14, 25]$$
So that:
$$ 5 ^ 3 = -17 $$$$(-17) ^ 2 = 5$$$$(17) ^ {14} = (-17) ^ {14} = (-17)^{14 (mod \space 5)} = (-17) ^ 4 = 25$$
$\endgroup$
