¿Hay una manera rápida de resolver $3^8 \equiv x \mod 17$?

Question

¿Hay una manera rápida de resolver $3^8 \equiv x \mod 17$?

Como el de arriba dice realmente, hay una manera rápida de resolver $x$? Ahora, lo que empecé haciendo fue $3^8 = 6561$, y luego iba a seguir restando $17$ hasta que me dieron mi respuesta.

Answer 1

Tratándose de poderes, la cuadratura es un buen truco para reducir cálculos (el ordenador lo hace demasiado!) Lo que esto significa es:

$\begin{array}{l l l l l} 3 & &\equiv 3 &\pmod{17}\\ 3^2 &\equiv 3^2 & \equiv 9 &\pmod{17}\\ 3^4 & \equiv 9^2 & \equiv 81 \equiv 13 & \pmod{17}\\ 3^8 & \equiv 13^2 & \equiv 169 \equiv 16 & \pmod{17}\\ \end{matriz} $

---

Nota un poco irrelevante: Teorema de por Euler, sabemos que $3^{16} \equiv 1 \pmod{17}$. Por lo tanto esto implica que el $3^{8} \equiv \pm 1 \pmod{17}$. Si usted sabe más acerca de la reciprocidad cuadrática, leer comentario De Thomas Andrew .

Answer 2

Generalmente solo hago pasos si es bastante razonable.
$3^3=10$
$3^4=10*3=13$
$3^5=13*3=5$
$3^8=5*3^3=5*10=16$

Answer 3

Aquí es una forma sencilla de calcular, que lamentablemente sólo funciona para estos números.

Tenga en cuenta que $2^4=16=-1 \pmod {17}$.

Entonces

$$3^8=-2^43^8=-2^49^4=-18^4=-1^4=-1 \pmod{17}$$

Answer 4

Mi respuesta inmediata fue que el $3^2=9$, que $3^4=81\equiv-4\pmod{17}$% y $3^8\equiv16\pmod{17}$, aunque si tuviera cualquier más computación para hacer, probablemente sería convertir que a $-1\pmod{17}$.

Answer 5

Estrictamente hablando, la manera más rápida sería probablemente al utilizar a algún tipo de software de computadora.

Por ejemplo, aquí está la respuesta en Wolfram | Alpha: $3^8 \equiv x \mod 17$