¿Cómo solucionarlo?

Question

¿Qué truco puedo usar para resolver la cuestión (en el título)?

Necesito resolverlo a mano, wihtout la ayuda de una computadora o calculadora. Y el truco simplemente no funciona con mi ejemplo, pero también con $3^{123456789}$ por ejemplo.

Answer 1

Escribir los primeros números de pocos. $2^0 \mod 17 = 1$. $2^1 \mod 17 = 2$. $2^2 \mod 17 = 4$. $2^3 \mod 17 = 8$. $2^4 \mod 17 = 16$. $2^5 \mod 17 = 15$. $2^6 \mod 17 = 13$. $2^7 \mod 17 = 9$. $2^8 \mod 17 = 1$.

Ahora si seguimos con esto, los resultados se repetición. Nos encontraremos con que $2^8 = 2^{16} = 2^{24} ... \mod 17 = 1$. Cada vez que la energía es un múltiplo de ocho, el modulo es de 1. Por lo tanto $2^{2999992} \mod 17 = 1$. Y 7 pasos más lejos, $2^{2999999} \mod 17 = 9$.

Answer 2

Tenga en cuenta que el pequeño Teorema de Fermat nos dice que $2^{16}\equiv 1 \bmod 17$

Ahora $2^{16n}=(2^{16})^n\equiv 1$

Siguiente $2999999+1=3000000$ y $16\mid 3000000$ - si esto no es obvio es porque $10000=16\cdot 625$ ($10^4=2^4\cdot 5^4$)

Para que $2x\equiv 2^{3000000}\equiv 1\equiv 18$ y $x\equiv 9$

Si no hay poco de Fermat $2^4=16\equiv -1$ como en los comentarios da $2^8\equiv 1$ y trabaja un argumento similar.

Se puede hacer en tu cabeza y no requiere dividir $2999999$ por cualquier cosa.

Answer 3

$2^{16} \equiv 1$ (mod $17$), y es divisible por $10000$ $16$. Por lo tanto, $2 ^ {2999999} \equiv 2 ^ {9999} $ (mod $ 17 $). Since $2 \times 2 ^ {9999} \equiv 1 $ (mod $17 $), so that $ 2 ^ {9999} \equiv #% 9 %#% 17$).

Del mismo modo, $ (mod $ (mod $3^{123456789} \equiv 3^{6789} \equiv 3^{789}$) puesto que es divisible por $17$ $6000$. Ahora $16$de % que $789 = (16 \times 49) +5,$ (mod $3^{789} \equiv 243 = (14 \times 17) +5 \equiv 5$).

Answer 4

$2^{16} \equiv 1\mod17$ y $2999999 = 187499 \times 16 + 15$, así que sabemos $(2^{16})^{187499} \equiv 1\mod17$, entonces la respuesta es $2^{15}+1 \equiv 10\mod 17$.