Demostrando que $a^{25} \bmod 65 = a \bmod 65$?

Question

Demostrar que para todos los $a \in \mathbb{Z}$ a^{25} \bmod 65 = a \bmod 65. $$

Tenemos $65 = 5 \cdot 13$ donde $5$ $13$ son primos. Así que yo quería para el cálculo de la primera expresión utilizando el teorema del Resto Chino. Tengo que encontrar una $x$ que satisface el sistema de $$\begin{cases} x \bmod 5 = a^{25} \bmod 5 \\ x \bmod 13 = a^{25} \bmod 13 \end{cases}.$$ But how can I solve this system when I don't know what $un$ is? I tried using Fermat's little theorem for the prime number $23$, but the above equation has to hold for all $un \in \mathbb{Z}$, not only with $mcd(a,p) = 1$.

Entonces, ¿cómo podemos resolver este problema?

Answer 1

Si $a=0$, entonces esto es trivial, por lo que asumen $a\neq 0$.

$\mathbb{Z}_5=\mathbb{Z}/5\mathbb{Z}$ es un campo, por lo $\mathbb{Z}_5^\times$, el grupo de los invertible elementos, es un grupo de $4$ elementos.

En particular, se ha $a^4\equiv 1\bmod 5$, lo $a^{24}=(a^4)^6\equiv 1\bmod 5$, e $a^{25}\equiv a\bmod 5$.

Del mismo modo, $\mathbb{Z}_{13}$ es un campo, y de su grupo de invertible elementos de ha $12$ elementos, por lo que $a^{12}\equiv 1\bmod 13$, $a^{24}\equiv 1\bmod 13$, y por lo tanto $a^{25}\equiv a\bmod 13$.

---

Nota: Usted puede evitar los campos y el uso de Fermat poco teorema directamente: $$a^5\equiv a\bmod 5.\tag{5.1}$$ Tomando el $5$-ésima potencia, obtenemos $$a^{25}\equiv a^5\bmod 5\tag{5.2}$$ y poner $(5.1)$ $(5.2)$ juntos, $$a^{25}\equiv a\bmod 5.$$ Ahora para $13$: $$a^{13}\equiv a\bmod{13}\tag{13.1}$$ Multiplicar por $a^{12}$: $$a^{25}\equiv a^{13}\bmod{13}\tag{13.2}$$ poner $(13.1)$ $(13.2)$ juntos: $$a^{25}\equiv a\bmod{13}.$$

Answer 2

El Teorema del Resto Chino rara vez es útil cuando usted está buscando en expresiones variables. Pero factoring $65$ $5 \cdot 13$ es útil.

Primero, observe que no se $65$ combinaciones posibles de $x \mod 5$$x \mod 13$; por lo que cada número $0$ a través de $64$ tiene un tipo de firma. Por Fermat poco teorema, $a^5 \equiv a \mod 5$, lo $a^{25} = (a^5)^5 \equiv a^5 \equiv a \mod 5$. De nuevo por Fermat, $a^{13} \equiv a \mod 13$, lo $a^{12} \equiv 1 \mod 13$ (a menos que $a \equiv 0 \mod 13$). Desde $a^{25} = a \cdot (a^{12})^2$, de cualquier manera tenemos $a^{25} \equiv a \mod 13$. Por lo $a^{25}$ $a$ tienen la misma firma mod $5$$13$, y, por tanto,$a^{25} \equiv a \mod 65$.

Answer 3

Aviso de $\, n = 65 = 5\cdot 13 \,$ es un producto de distintos números primos $\rm \,p\,$ tal que $\rm \ \color{#c00}{p\!-\!1\mid 25\!-\!1},\:$, con lo que

Teorema $\ $ Para los números naturales $\rm\:a,e,n\:$ $\rm\:e,n>1$

$\qquad\rm n\:|\:a^e-a\:$ todos los $\rm\:a\:\iff n\:$ es squarefree, y el primer $\rm\:p\:|\:n\,\Rightarrow\, \color{#c00}{p\!-\!1\mid e\!-\!1}$

Prueba de $\ (\Leftarrow)\ $ Sugerencia: dado que un squarefree natural que divide a otro iff todos sus los factores primos de hacer, sólo necesitamos mostrar $\rm\:p\:|\:a^e\!-\!a\:$ para cada uno de los prime $\rm\:p\:|\:n,\:$ o, que $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$, lo que, desde el $\rm\:p\!-\!1|\:e\!-\!1,\:$ sigue de $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ a poco de Fermat.

$(\Rightarrow)\ $ No se necesita aquí, ver a esta respuesta