Computación $7^{13} \mod 40$

Question

Me quiere calcular el $7^{13} \mod 40$. Me mostró que $$7^{13} \equiv 2^{13} \equiv 2 \mod 5$$ y $$7^{13} \equiv (-1)^{13} \equiv -1 \mod 8$$.

Por lo tanto, tengo que $7^{13} - 2$ es un múltiplo de a $5$, mientras que el $7^{13} +1$ es un múltiplo de a $8$. Yo quería hacer dos iguales, por lo que he resuelto $-2 + 5k = + 8n$ para los números naturales $n,k$ y se encontró que el $n = 9, k = 15$ le dio una solución (sólo traté de hacer $3 + 8n$ un múltiplo de $5$. Por lo tanto, tengo que $$7^{13} \equiv -73 \equiv 7 \mod 40.$$

Es esto correcto? Además, hay una manera más fácil? (También he probado a utilizar el de Euler totient función, sino $\phi(40) = 16$, lo $13 \equiv -3 \mod 16$, pero no sabía cómo proceder con esto.)

Answer 1

Sí, más fácil, por Fermat/Euler (o directamente) $\ \color{}{7^{\large 4}\!\equiv 1}\,$ mod $\,5\,$ $\,8,\,$ $\,5,8\mid 7^{\large 4}\!-1.\,$

Por Lo Tanto $\, {\rm lcm}(5,8)\!=\!40\mid \color{#c00}{7^{\large 4}\!-1}.\,$ $\ {\rm mod}\ 40\!:\ 7^{\large 12}\!\equiv 7(\color{#c00}{7^{\large 4}})^{\large 3}\equiv 7(\color{#c00}1)^{\large 3}\equiv 7$

Comentario $\ $ Ver Carmichael Lambda Teorema de una manera general para hacer esto (combina Euler totient exponentes para cada fuente primaria de energía de manera más eficiente el uso de lcm, como hace implícitamente, arriba).

Answer 2

Usted no necesariamente tiene que utilizar el hecho de $40=8\times 5$ (pero si lo haces, busca el "teorema del resto Chino".)

---

De lo contrario, usted sabe que

$$7^2\equiv 49\equiv 9\pmod{40}.$$

Así

$$7^3\equiv 63\equiv 23\pmod{40},$$

así

$$7^4\equiv 161\equiv 1\pmod{40}.$$

Entonces

$$7^{13}\equiv 7^{4\times 3}\times 7\equiv 1\times 7\equiv 7\pmod{40}.$$

Answer 3

Usted podría tomar nota de que $\varphi(5) = 5-1 = 4$$\varphi(8) = 8- 4 = 4$. Por lo tanto $7^4 \equiv 1 \pmod 5$$7^4 \equiv 1 \pmod 8$, en cuyo caso $7^4 \equiv 1 \pmod{40}$.

Por lo tanto $7^{13} \equiv (7^4)^3 \cdot 7 \equiv 7 \pmod{40}$.

Answer 4

El Carmichael función de $\lambda$ es una versión más fuerte de Euler totient función para este propósito, que combina diferentes factores primos por $\rm lcm$ más que una simple multiplicación, y se ajusta a los poderes superiores de $2$.

Por lo $\lambda(40) = {\rm lcm}(\lambda(8),\lambda(5)) = {\rm lcm}(2,4) = 4$, y por lo tanto la longitud del ciclo de la $7$ es divisible por $4$. Desde $\gcd(7,40)=1$$13\equiv 1 \bmod 4$, esto nos da inmediatamente $7^{13}\equiv 7 \bmod 40$.

Answer 5

$$\phi(40)=16 \to 7^{16}\equiv 1$$mod 40 $$7^{16}\equiv 1 \\7^{13}7^3\equiv 1\\ 343.7^{13}\equiv 1 \\ (320+23).7^{13}\equiv 1\\ 23.7^{13}\equiv 1\\ 23.7^{13}\equiv 1+40 \equiv 1+80\equiv 1+120\equiv 1+160\\ 23.7^{13}\equiv 161 \\23.7^{13}\equiv 7(23)$$ divide by $23$ , $(23,40)=1 $ así $$23.7^{13}\equiv 7(23) \to 7^{13}\equiv 7$$