¿Cómo puedo calcular el resto de $3^{2012}$ modulo 17?

Question

Hasta ahora esto es lo que puedo hacer:

Utilizando el pequeño Teorema de Fermat que saber que $3^{16}\equiv 1 \pmod {17} $

También: $3^{2012} = (3^{16})^{125}*3^{12} \pmod{17}$

Así que me quedo con $3^{12}\pmod{17}$.

Otra vez voy a usar Teorema de fermat así: $ 3^{12} = \frac{3^{16}}{3^{4}} \pmod{17}$

Aquí estoy atrapado porque me sale $3^{-4} \pmod{17}$ y no sé cómo calcular esto porque no sé qué $\frac{1}{81} \pmod{17}$ es.

Sé que $81 = 13 \pmod{17}$

Pero sé que la respuesta es 4. ¿Lo que hizo que mal?

Answer 1

De hecho, tenemos %#% $ #%

Además, $$3^{12}=31261\cdot17+4.$ $

Además, contamos con %#% $ #%

Answer 2

Sólo hazlo.

$3^4 = 81 \equiv -4$.

$3^{12} \equiv (3^4)^3 = (-4)^3 \equiv -81 \equiv 4 \mod 17$.

Insight:

Sabes $3^{16}\equiv 1 \mod 17$ lo $3^{8}\equiv \pm 4$ % que $3^4 \equiv \pm 1, \pm \sqrt{-1}$. Así $-1 \equiv 16$ de la $\sqrt {-1} \equiv 4\mod 17$. (el otro es $13$). Esto que te diga para intentar encontrar $3^{12}$ a través de iteraciones $3^4$.

También: $81 \equiv 13 \equiv - 4 \mod 17$. Así $\frac 1{81} \equiv -\frac 14$. Y $\frac 14$ no debería ser difícil $1 \equiv 18$ % que $\frac 12 \equiv 9 \mod 17$y $9 \equiv 26$ % que $\frac 14 \equiv 13\equiv -4$. Así $-\frac 14 = 4$. Y tiene sentido. $(-4)*4 = -16 \equiv 1 \mod 17$.

Answer 3

$3^{12}=(3^3)^4=10^4$ (mod $17$), así que tenemos que encontrar $10000$ (mod $17$), que es evidentemente $4$ (mod $17$).

Answer 4

Además de las respuestas inteligentes, cuadratura repetida directa se puede utilizar. $$ 3 ^ {12} = 3 ^ \cdot 8 3 ^ 4 $ y $$ 3 ^ 2 = 9 \equiv 9 \mod 17 $$ tan $$ 3 ^ \equiv 4 9 ^ \mod \equiv 13 2 17 $$ y $$ 3 ^ \equiv 8 13 ^ 2 \equiv 16 \mod 17 $$ finalmente $$ 3 ^ {12} = 3 ^ 8 \cdot 3 ^ 4 \equiv 16 \cdot 13 \equiv 4 \mod 17 $$

La línea final podría simplificarse aún más si lo desea $$ 16 \cdot 13 = 4 \cdot 52 \equiv 4 \cdot 1 \mod 17 $$