¿Cómo puedo encontrar el resto de $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ ¿dividido entre 17?

Question

Hace poco me encontré con una pregunta,

Encuentra el resto de $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ ¿dividido entre 17?

Al principio apliqué la fórmula de la suma de G.P. pero acabé con la expresión $1\cdot \dfrac{4^{41}-1}{4-1}$ . No pude averiguar cómo seguir adelante. En segundo lugar pensé en utilizar el hecho $(a+b+\cdots) \pmod {17} = (r_a+r_b\dots) \pmod {17}$ pero cada vez está más desordenado.

Por favor, explique con detalle. Y también mencione la fórmula que se utiliza.

Answer 1

$$\frac{4^{41}-1}{4-1}\equiv \frac{2^{82}-1}{4-1}\equiv \frac{2^2-1}{4-1}\equiv 1\pmod{17}.$$ Se utilizó el pequeño teorema de Fermat: $2^{16}\equiv 1\pmod{17}$ implica: $$ 2^{82} = 2^{5\cdot 16+2} = 4\cdot \left(2^{16}\right)^5 \equiv 4\pmod{17}.$$

---

Otro enfoque. Dejemos que $a_n = 4^0+4^1+\ldots+4^n$ . Entonces, obviamente $a_{n+1}=4a_n+1$ Así que, teniendo en cuenta $a_n\pmod{17}$ para calcular $a_{n+1}\pmod{17}$ es sencillo. $a_0=1$ , por lo que nuestra secuencia $\pmod{17}$ va así: $$ 1 \to 5 \to 4 \to 0 \to 1 \to 5 \to 4 \to \ldots $$ por lo que es $4$ -periódico. Esto implica $a_{40}\equiv a_{0}\equiv 1\pmod{17}$ .

Answer 2

SUGERENCIA:

Obsérvese que para cualquier entero no negativo $a,$ $$1+4+4^2+4^3=(1+4)(1+4^2)\equiv0\pmod{17}$$

$$\implies\sum_{a=m}^n4^{4a}(1+4+4^2+4^3)\equiv0\pmod{17}$$

Aquí $m=0,n=9$

Answer 3

Si calcula $4^{k}\ (\operatorname{mod}\ 17)$ para algunos $k$ se puede notar rápidamente que los valores son periódicamente $1,4,-1,-4$ . Esto no es una coincidencia, ya que $4^4 \equiv 1 \ (\operatorname{mod}\ 17)$ y por lo tanto $$4^{4k+l}\equiv 4^{4k}\cdot 4^l \equiv (4^4)^k\cdot 4^l \equiv 4^l \ (\operatorname{mod}\ 17)$$ Por lo tanto, concluimos $$4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}\equiv 4 + (-1) + (-4) + 1 \equiv 0 \ (\operatorname{mod}\ 17)$$ y puede calcular $$4^0+4^1+4^3+\cdots 4^{40} \equiv (4^0+4^1+4^3+4^4)+\sum_{k=1}^9(4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}) \equiv 4^0+4^1+4^3+4^4 \equiv 1 + 4 + (-4) + 1 \equiv 2\ (\operatorname{mod}\ 17)$$ Por supuesto, si $4^2$ falta accidentalmente en la pregunta, la suma se evalúa fácilmente como $1$ .

Answer 4

Una pista: $$4^2 = 16 \equiv -1 \mod 17$$ $$4^4 \equiv (-1)^2 \equiv 1 \mod 17$$