Cuál es la forma más fácil y rápida de encontrar el resto cuando $17^{17}$ se divide por $64$ ?

Question

Cuál es la forma más fácil y rápida de encontrar el resto cuando $17^{17}$ se divide por $64$ ?

Answer 1

Si tienes un ordenador, lo más fácil es realizar 17 17 en aritmética de enteros de precisión fija y enmascarar los 6 bits inferiores. No se gana nada con esto, pero sólo se tarda unos segundos en teclear en un lenguaje apropiado. No está mal para ser fácil y rápido. (Scala: Seq.fill(17)(17).product & 63 .)

Answer 2

Todo número impar es congruente con $1$ mod $8$ después de la cuadratura.

Todo número impar es congruente con $1$ mod $16$ después de ser elevado a la $4$ de la potencia.

...

Todo número impar es congruente con $1$ mod $64$ después de ser elevado a la $16$ de la potencia.

(Si $n \geq 3$ entonces todo número impar es congruente con $1$ mod $2^n$ después de ser elevado a la $2^{n-2}$ y poder).

Por lo tanto, si $a$ es impar, $a^{17} \equiv a \bmod 64$ . En particular, $17^{17} \equiv 17 \bmod 64$ .

Answer 3

$17^4=(16+1)^4=16^4+4\cdot 16^3+6\cdot 16^2+4\cdot 16+1 \equiv 1 \pmod {64}$

(Obsérvese que todos los números $16^4$ , $16^3$ , $16^2$ y $4\cdot 16$ son múltiplos de $64$ .)

$17^{17} = (17^4)^4\cdot 17 \equiv 1\cdot 17 \pmod {64}$

Answer 4

Un poco más conciso que la solución de Martin Sleziak

$$17^n=(1+16)^n=1+\binom n116+16^2(\cdots)\equiv1+16n\pmod{16^2}$$

$$\implies 17^{17}\equiv1+16\cdot17\equiv1+16(16+1)\pmod{16^2}\equiv17\pmod{16^2}$$

Como $64$ divide $16^2,$ $$17^{17}\equiv17\pmod{64}$$