El cálculo de $17^{14}\mod{71}$ el uso de Fermat poco teorema de

Question

Calcular el $17^{14} \pmod{71}$

Por Fermat poco teorema:
$17^{70} \equiv 1 \pmod{71}$
$17^{14} \equiv 17^{(70\cdot\frac{14}{70})}\pmod{71}$

Y entonces yo no sé realmente qué hacer a partir de este punto. En otro ejemplo, los términos eran lo suficientemente pequeñas como para que yo sólo podría simplificar a una respuesta, pero en este ejemplo, no tengo idea de qué hacer con ese $17^{(70\cdot\frac{14}{70})}$

¿Qué puedo hacer desde aquí?

Answer 1

$17$ no está particularmente cerca de un múltiplo de $71$, pero como Ragib Zaman señaló, $17^2=289$: $289=4\cdot71+5$. Por lo tanto, $17^{14}=(17^2)^7=289^7\equiv 5^7\pmod {71}$. En ese punto se puede utilizar la fuerza bruta, o usted podría notar que $5^4=625$ está muy cerca de la $9\cdot71=639$. De hecho,$625=639-14$, por lo que $5^4\equiv -14\pmod{71}$, $5^5\equiv -70\equiv 1\pmod{71}$, y, finalmente, $$17^{14}\equiv 5^7\equiv 5^2\equiv 25 \pmod{71}\;.$$

Answer 2

Tenemos que

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

o

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

No veo a ninguna de ellas como especialmente fácil de calcular, como $17^{14} = 289^{7} \equiv 5^{7}$. Si usted no tiene el uso de Fermat, te sugiero ir con eso.

Answer 3

Aquí está el cálculo mediante una adición de la cadena.

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

Ver a la izquierda de la ruta en el árbol de abajo.