Demostrar que $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$ ) para todos los primos $n\in\mathbb{N}$ .

Question

Demostrar que $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$ ) para todos los primos $n\in\mathbb{N}$ .

Me cuesta probar este problema. He podido comprobar que funciona para prime $n$ hasta 5000 utilizando Python.

¿Supongo que la inducción sería útil en este caso? Me encantaría recibir ayuda con este problema.

Answer 1

Es bueno que puedas hacer que Python calcule hasta 5000 por ti, pero a veces lo que realmente puede ayudarte es calcular dos o tres casos a mano para ver si puedes detectar algún patrón.

Probemos $n = 5$ :

• $1^4 = 1 \equiv 1 \pmod 5$ . Desde $1^x = 1$ independientemente de lo que $x$ es, podríamos seguir adelante y considerar 1 como la caída del taxímetro en este problema para todos los $n$ .
• $2^4 = 16 \equiv 1 \pmod 5$ .
• $3^4 = 81 \equiv 1 \pmod 5$ .
• $4^4 = 256 \equiv 1 \pmod 5$ .

Estos suman 4, que es uno menos que 5.

Ahora vamos a intentar $n = 6$ . Lo sé, eso no es de primera, pero aún así podría darnos una idea.

• 1 es la caída del taxímetro.
• $2^5 = 32 \equiv 2 \pmod 6$ .
• $3^5 = 243 \equiv 3 \pmod 6$ .
• $4^5 = 1024 \equiv 4 \pmod 6$ .
• $5^5 = 3125 \equiv 5 \pmod 6$ .

Estos suman 21, que es $3 \pmod 6$ . En cierto modo, el 6 es un poco inusual (no espere $i^{n - 1} \equiv i \pmod n$ siempre que $n$ es compuesto), pero aún podemos aprender de esto que si $\gcd(i, n) > 1$ entonces $i^{n - 1} \equiv 1 \pmod n$ es imposible.

De hecho, $i^{n - 1} \equiv d \pmod n$ où $d$ es un divisor no trivial de $n$ o 0 (que puede considerarse un divisor en el contexto de la aritmética modular). Por ejemplo, para $n = 8$ si $i$ es par, entonces $i^7 \equiv 0 \pmod 8$ . Esto se debe a que $8 = 2^3$ y $i$ ser par significa que $i = 2j$ . Entonces $i^7 = 2^7 j$ que obviamente es múltiplo de 8.

Por lo tanto, si $n$ es primo, entonces todos $i$ de 1 a $n - 1$ son coprimos de $n$ lo que significa que es posible que $i^{n - 1} \equiv 1 \pmod n$ para cada $i$ . De hecho, cada $i$ da $i^{n - 1} \equiv 1 \pmod n$ hecho del que se percató Pierre de Fermat.

No sé si el propio Fermat demostró este "pequeño teorema", pero mucha otra gente lo ha hecho, y la demostración es bastante fácil de seguir, aunque no la repetiré aquí. Tampoco repetiré la respuesta del Breve, que espero que ahora sea más fácil de entender.

Sólo queda una cosa por abordar, y es la inducción. Muchas cosas se pueden demostrar con la inducción, incluso cuando no es el mejor método de prueba. Para este problema en particular, creo que el mejor método es simplemente aplicar el pequeño teorema de Fermat y dejar que todo encaje.

Answer 2

Pista: por el pequeño teorema de Fermat, $i^{n-1}\equiv 1$ (mod $n$ ).

Answer 3

Es un caso evidente del pequeño teorema de Fermat o, como prefieren llamarlo los demonios como yo, el teorema de Fermat. Quien llegara primero a tu pregunta sabría inmediatamente que esa es la respuesta.

Si $p$ es primo y $a$ es coprimo de $p$ entonces $a^{p - 1} \equiv 1 \pmod p$ el teorema de Fermat nos dice.

Entonces, con $$\sum_{i = 1}^{n - 1} i^{n - 1},$$ si $n$ es primo, sabemos que todos $0 < i < n$ son coprimos de $n$ y, por tanto, cada $i^{n - 1} \equiv 1 \pmod n$ . Y puesto que hay $n - 1$ casos de $i$ que recorremos en bucle, encontramos que $$\sum_{i = 1}^{n - 1} i^{n - 1} \equiv n - 1 \pmod n,$$ y $n - 1$ no es más que otra forma de escribir $-1$ en este contexto.

Edita: Alguien intentó corregir uno de mis errores y se preguntó si era intencionado o no. Pues bien, permítanme tranquilizarles: todos mis errores son intencionados. Por una tonta razón, el intento de ese tipo de corregir mi error fue rechazado, así que lo he corregido yo mismo.