¿Qué es

Question

Estoy tratando de evaluar $15^{15} + 16^{16} + 17^{17} + 18^{18} + 19^{19} + 20^{20} \pmod{7}$. He encontrado que $15^{15} \equiv 1 \pmod{7}$ y que $16^{16} \equiv 2 \pmod{7}$.

Para evaluar $15^{15} \pmod{17}$, hice lo siguiente: $$15 = 2 \times 7 + 1 \equiv 1 \pmod{7}$$ $$15^{15} \equiv 1 \pmod{7}$$

Entonces, para evaluar $16^{16}$, escribí: $$16 = 15 + 1 \equiv 1 + 1 = 2 \pmod{7}$$ $$16^{16} \equiv 2^{16} \pmod{7}$$

$$2^{3} = 8 = 7+1 \equiv 1 \pmod{7}$$ $$2^{16} = 2^{3} \times 2^{13} \equiv 2^{13} = 2^{3} \times 2^{10} \equiv 2^{10} \equiv \dots \equiv 2 \pmod{7}$$

Sin embargo, no he conseguido averiguar cómo evaluar $17^{17}$. ¿Cómo debo ir sobre esto y es mi enfoque general para la evaluación de la suma en la pregunta correcta?

Answer 1

El Teorema de Euler de los estados que $$ a^{\phi(n)}\equiv1 \pmod{n}$$ Para todos los $n$, donde $\phi(n)$ es el de Euler totient función, que indica el número de enteros positivos a menos de $n$ relativamente primer a $n$. Para los números primos, $\phi(n)=n-1$. Así $$ a^{n-1}\equiv1\pmod n. $$ Este resultado es también conocido como Fermat poco teorema. Ahora, $7$ es un número primo, así que cualquier cosa que el poder de la $6$ es congruente a $1$. Tenemos $$\begin{split} &15^{15}+16^{16}+17^{17}+18^{18}+19^{19}+20^{20}\\ \equiv\, & 15^3 + 16^4 + 17^5 + 18^0 + 19^1 + 20^2 \\ \equiv \, & 1^3 + 2^4 + 3^5 + 4^0 + 5^1 + 6^2\\ \equiv\, & 1+16+243+1+5+36\\ \equiv\, & 302\\ \equiv\, & 1\pmod{7}. \end{split}$$

Answer 2

Usted puede ir con el mismo proceso que yo creo:

$$17^{17} \equiv 3^{17} \mod{7}$$

y tenemos

$$3^1 \equiv 3 \mod{7}$$ $$3^2 \equiv 2 \mod{7}$$ $$3^3 \equiv 6 \mod{7}$$ $$3^4 \equiv 4 \mod{7}$$ $$3^5 \equiv 5 \mod{7}$$ $$3^6 \equiv 1 \mod{7} \text{ (We could have this by using Fermat's Little Theorem as well)}$$

A partir de aquí, podemos concluir que $3^{17} \equiv 5 \mod{7}$.

A continuación, observe que

$$18 \equiv 4 \equiv -3 \mod{7}$$ $$19 \equiv 5 \equiv -2 \mod{7}$$ $$20 \equiv 6 \equiv -1 \mod{7}$$ lo que significa que usted puede encontrar otros términos por el uso de sus resultados anteriores para $15,16$ e $17$.

Pero como se sugiere en los comentarios, que la mejor manera es el uso de Fermat Poco Teorema.