¿Cuál es la estrategia para encontrar $\sum_{k=2}^{300} k^k \pmod 7$ ?

Question

Estoy atascado en este problema de aritmética modular para practicar en casa: $$\sum_{k=1}^{300} k^k \pmod 7$$

No sé muy bien cómo enfocar este problema. He intentado encontrar un patrón entre las sumas pero no creo que haya ninguno. Sé cómo encontrar mods de a^b (mod c) pero para esta pregunta no tengo ni idea. Se agradece cualquier pista o ayuda.

Answer 1

Para cualquier $k$ hay números enteros $q,r$ tal que $k=7q+r$ donde $0\leq r\leq 6$ .

Así que $$k^k=(7q+r)^{(7q+r)}\cong r^{(7q+r)}\quad (mod 7).$$

A partir de que usted debe utilizar el pequeño teorema de Fermat.

¿Puedes llevarlo desde aquí?

Answer 2

Se repite, pero sólo después de $7*6 = 42$ términos (las bases se repiten en ciclos de 7 mientras que los exponentes se repiten en ciclos de 6). Prueba a dividirlo así $$\sum_{k=1}^{43} 1^{1 + 7(k-1)} + \sum_{k=1}^{43} 2^{2+7(k-1)} + \sum_{k=1}^{43} 3^{3+7(k-1)} + \sum_{k=1}^{43} 4^{4+7(k-1)} + \sum_{k=1}^{43} 5^{5+7(k-1)} + \sum_{k=1}^{43} 6^{6+7(k-1)} + \sum_{k=1}^{42} 7^{7+7(k-1)}$$ Ahora, los exponentes se pueden reducir $\bmod{6}$ ya que $a^{6} \equiv 1 \bmod{7}$ por cada $a \neq 0$ . Esto da $$\sum_{k=1}^{43} \left( 1^{1 + (k-1)} + 2^{2+(k-1)} + 3^{3+(k-1)} + 4^{4+(k-1)} + 5^{5+(k-1)} + 6^{(k-1)}\right)$$ o de forma equivalente $$7\sum_{k=1}^{6} \left(1^{1 + (k-1)} + 2^{2+(k-1)} + 3^{3+(k-1)} + 4^{4+(k-1)} + 5^{5+(k-1)} + 6^{(k-1)}\right) + 1^{1} + 2^{2} + 3^{3} + 4^{4} + 5^{5} + 6^{0}$$

Answer 3

Para resumir lo que hay a continuación, básicamente $(x+42)^{x+42}\equiv x^x\pmod{7}$ y como $300=42\times7+6$ hay $7$ periodos de los mismos restos más 6 cosas extra por lo que el resto tiene que ser igual a las 6 cosas extra.

---

Por conveniencia de la escritura, denotamos $0^0=0$ en esta respuesta.

Ahora aplique el pequeño teorema de Fermat $x^6\equiv1\pmod{7}$ obtenemos que su suma es congruente con

$$0^0+1^1+2^2+...+6^0+7^1+8^2+...+12^0+13^1+...299^5+300^0$$

que es congruente con

$$0^0+1^1+2^2+...+6^0+0^1+1^2+...+5^0+6^1+...5^5+6^0$$

Agrupamos cada siete:

$$(0^0+1^1+2^2+...+6^0)+(0^1+1^2+...+5^0+6^1)+...+(0^5+...+6^5)+...+(0^0+...+5^5+6^0)$$

Ahora cada periodo consiste en $6$ grupos.

Ahora cada "6-grupo" tiene 42 elementos y $300=42\cdot7+6$ por lo que hay $7$ "6-grupos" y su suma es congruente con $(0^0+1^1+2^2+3^3+4^4+5^5+6^0)\equiv 5\pmod{7}$