¿Cómo puedo mostrar $e^2 \equiv 1 \bmod 24$, dado que el $\gcd(e, 24) = 1$?

Question

El problema viene de una práctica final para un examen final que más tarde hoy.

Dice "Mostrar eso si $\gcd(e, 24) = 1$ y $e^2 \equiv 1 \bmod 24$".

He encontrado φ función % de Euler $\phi(24) = 8$así que ahora sé $e^8 \equiv 1 \bmod 24$, pero no sé dónde ir desde allí.

Encontré que si $\sqrt[4]e$ es un entero, entonces es obvio que $\sqrt[4]e \mid e$, por lo que $\gcd(\sqrt[4]e, 24) = 1$ que puedo usar para probar $e^2 \equiv 1 \bmod 24$, sino que sólo la prueba en el caso donde $\sqrt[4]e$ es un número entero (y no creo que realmente voy en la dirección correcta aquí).

Answer 1

Euler $\varphi$-la función es a menudo no es la herramienta adecuada para este tipo de problema. Me gustaría trabajar por separado modulo $3$ y el modulo $8$.

Si $\gcd(e,24)=1$,$\gcd(e,3)=1$. Por lo tanto, por el Teorema de Fermat (pero eso es una exageración!) tenemos $e^2\equiv 1\pmod 3$. Es una exageración, porque si $e$ no es divisible por $3$,$e\equiv \pm 1\pmod{3}$, y por lo tanto $e^2\equiv 1\pmod 3$.

Si $\gcd(e,24)=1$, $e$ es impar. Es un estándar de hecho de que si $e$ es impar, entonces $e^2\equiv 1\pmod 8$. Por un bajo nivel de pruebas, todo lo que tenemos que hacer es comprobar el resultado de $e=1$, $3$, $5$, y $7$, o más simplemente para$e=\pm 1$$e=\pm 3$. O bien, podemos notar que si $e$ es impar, entonces $e=2k+1$ algunos $k$. Así $e^2=4k^2+4k+1=4k(k+1)+1$. Desde $k$ $k+1$ son números enteros consecutivos, uno de ellos es par, y por lo tanto $4k(k+1)$ es divisible por $8$.

A partir de los hechos que $e^2\equiv 1\pmod 3$$e^2\equiv 1\pmod 8$, llegamos a la conclusión de que $e^2\equiv 1\pmod{24}$.

Answer 2

La respuesta por Andre Nicolas es el camino a seguir. Sin embargo, siempre tenga en mente que usted podría haber sido seleccionada a mano, debido a que el módulo del problema ($24$) es bastante pequeño!

Si $\gcd(e,24)=1$, y vamos a calcular un valor modulo $24$, entonces basta para comprobar que la afirmación es verdadera para todos los congruencia clases de $e\bmod 24$ tal que $\gcd(e,24)=1$, es decir, necesitamos revisar la declaración de $$e\equiv 1,5,7,11,13,17,19,23 \bmod 24.$$ Ahora el problema se ha reducido a la comprobación de que el cuadrado de cada uno de estos ocho números es congruente a $1\bmod 24$. En efecto: $$1^2\equiv 1,\ 5^2\equiv 25\equiv 24+1\equiv 1,\ 7^2\equiv 49\equiv 48+1\equiv 1,\ 11^2\equiv 121 \equiv 24\cdot 5+1\equiv 1 \bmod 24,$$ y $$23^2\equiv (-1)^2\equiv 1^2\equiv 1,\ 19^2\equiv (-5)^2\equiv 5^2\equiv 1,\ 17^2\equiv (-7)^2\equiv 7^2\equiv 1,\ 13^2\equiv (-11)^2 \equiv 1 \bmod 24.$$ Por lo tanto, $e^2\equiv 1 \bmod 24$ siempre $\gcd(e,24)=1$.

Answer 3

Decir $gcd(e, 24) = 1$. Desde $24 = 2^3 \times 3$, sabemos que $e$ no es aún y no un múltiplo de 3. Así $e$ es de % de forma $6k \pm 1$, para algún entero $k$.

Entonces $$(6k \pm 1)^2 = 36k^2 \pm 12k + 1$ $ y por lo que basta para mostrar que $36k^2 + 12k$ es un múltiplo de $24$. Nosotros podemos factor $12k(3k+1)$; para cualquier opción de $k$, uno de los $k$ y $3k+1$ es, incluso, así es $k(3k+1)$ $12k(3k+1)$ es un múltiplo de 24.

Answer 4

Una respuesta más sofisticada es que $U_{24} \cong U_8 \times U_3 \cong C_2 \times C_2 \times C_2$, y por lo tanto tiene exponente $2$.

En general, el exponente de $U_m$ es $\lambda(m)$, donde $\lambda$ función de Carmichael.