¿Cómo encontrar $3^{1000}\bmod 7$?

Question

Lo siento esto es un problema muy simple pero no pude averiguar. Estoy tratando de encontrar el valor de $3^{1000}\bmod 7$. Sé el valor real es de 4, pero utilicé una calculadora. ¿Cómo sería simplificar este problema para obtener la respuesta correcta sin una calculadora? No quiero una respuesta directa, pero tal vez un empujón en la dirección correcta, como podría utilizar trucos o tal vez una manera alternativa de escribirlo.

Answer 1

Si sabes pequeño Teorema de Fermat, usted sabe que puede reducir al exponente. Si no, simplemente puede hacer un poco de la prueba:\begin{align} 3 &\equiv 3 &\pmod{7}\ 3^2 &\equiv 2&\pmod{7}\ 3^3 &\equiv 2\times 3&\pmod{7}\ &\equiv -1 &\pmod{7}. \end{align} en este punto, usted sabrá también que $3^6 = (3^3)(3^3)\equiv (-1)^2 \equiv 1 \pmod{7}$.

Eso significa que los restos serán "ciclo" cada siete pasos, desde $3^7 = 3(3^6) \equiv 3(1) = 3 \pmod{7}$.

Ahora, observe que puesto que $1000 = 6(166) + 4$, $$3^{1000} = 3^{6(166)+4} = (3^6)^{166}3^4 = (3^6)^{166}3^33^1.$ $ sabes lo que cada uno de los factores entonces es modulo $7$, por lo que terminas.

Answer 2

Trate de dividir el número enorme en números más pequeños que conoce el valor de. Por ejemplo

$3^{1000} \text{mod} 7= (3^{10})^{100} \text{mod} 7= (59049)^{100} \text{mod} 7= 4^{100} \text{mod} 7 = \ldots$

Si $3^{10}=59049$ era todavía demasiado grande podría intentar reescribirlo otra vez etcetera.

Answer 3

Desde que mod7⁶3 = 1, entonces tenemos 3¹⁰⁰⁰= 3^{6 * 166 +4}= 3⁴= 4 mod7.

Answer 4

es difícil de calcular a mano debido al $3^{1000}$ $1000$. ¿Se puede aprender cualquier cosa, desde tratar de exponentes pequeños en su lugar?