Si $N$ es el número entero $2^43^35^27$ encontrar el más pequeño entero positivo $m$ de tal manera que $x^m \equiv 1 \mod N$ para todos los enteros coprime a $N$

Question

Si $N$ es el número entero $2^43^35^27$ encontrar el más pequeño entero positivo $m$ de tal manera que $x^m \equiv 1 \mod N$ para todos los enteros coprime a $N$ .

Entiendo que puedo hacer esto por el individuo $N$ ( $N= 2^4, 3^3, 5^2, 7$ ) y luego tomar el LCM por el Teorema del Restos Chinos. Usar el Pequeño Teorema de Fermat no me da el más grande de tales $m$ para cada elección de $N$ . ¿Cuál es el teorema/herramienta relevante aquí?

EDITAR (por sugerencias): Aplicando la función phi de Euler nos da $ \phi (2^4) = 8, \phi (3^3) = 3^2 \times 2, \phi (5^2) = 5*4, \phi (7) = 6$ .

¿Por qué son estos los más pequeños $m$ ?

Answer 1

$ \color {Green}{ \text {Lemma}}$ :

• Por cada número primo de impar $p$ ; y por cada entero positivo $ \alpha $ ;
  el grupo multiplicador $ \mathbb {Z}_{p^{ \alpha }}^*$ ;
  es un grupo cíclico de orden $ \phi (p^{ \alpha })= (p-1)p^{ \alpha -1}$ .
  En otras palabras:

$$ \big ( \mathbb {Z}_{p^{ \alpha }}^* \ , \times \big ) \equiv \big ( \mathbb {Z}_{(p-1)p^{ \alpha -1}} \ , + \big ) . $$

• Para $ \color {Red}{p=2}$ ; y por cada entero positivo $ \color {Red}{3 \leq \alpha }$ ;
  el grupo multiplicador $ \mathbb {Z}_{2^{ \alpha }}^*$ ;
  es la suma directa de $ \mathbb {Z}_2$ y un grupo cíclico de orden $ \color {Red}{ \dfrac {1}{2}} \phi (2^{ \alpha })= \color {Red}{2^{ \alpha -2}}$ .
  En otras palabras:

$$ \big ( \mathbb {Z}_{2^{ \alpha }}^* \ , \times \big ) \equiv \big ( \mathbb {Z}_2 \oplus \mathbb {Z}_{ \color {Red}{2^{ \alpha -2}}} \ , + \big ) . $$

• El grupo multiplicador $ \mathbb {Z}_{2^2}^*$ ; es un grupo cíclico de orden $2$ .
  El grupo multiplicador $ \mathbb {Z}_{2}^*$ ; es el grupo trivial.

---

---

$ \color {Teal}{ \text {Remark}}$ :

Vamos a definir la función $ \psi $ de la siguiente manera:

• Por cada número primo de impar $p$ ; y por cada entero positivo $ \alpha $ ;
  $ \psi (p^{ \alpha }) = \phi (p^{ \alpha }) = (p-1)p^{ \alpha -1} . $

• Para $ \color {Red}{p=2}$ ; y por cada entero positivo $ \color {Red}{3 \leq \alpha }$ ;
  $ \psi (2^{ \alpha }) = \color {Red}{ \dfrac {1}{2}} \phi (2^{ \alpha }) = \color {Red}{2^{ \alpha -2}} . $

• $ \psi (4)= \phi (4)=2.$

• $ \psi (2)= \phi (2)=1.$

• $ \psi (1)= \phi (1)=1.$

---

• Si $n$ tiene la factorización principal $ n = \color {Red}{2^{ \alpha_0 }} p_1^{ \alpha_1 } p_2^{ \alpha_2 } ... p_k^{ \alpha_k } $ ;
  con $ \alpha_0 \in \mathbb {N}_0= \mathbb {N} \cup \{ 0 \} $ ; $ \alpha_1 \in \mathbb {N}$ , $ \alpha_1 \in \mathbb {N}$ , $...$ $ \alpha_k \in \mathbb {N}$ ; entonces definamos: $ \psi (n) = \text {lcm} \Big ( \psi (2^{ \alpha_0 }); \psi (p_1^{ \alpha_1 }), \psi (p_2^{ \alpha_2 }), ..., \psi (p_k^{ \alpha_k }) \Big ) $

---

---

---

---

Uno puede comprobar fácilmente que :

$$ \color {Teal}{ \psi (n)} \color {Green} { \text {is the least integer} \ m \ \\ \text {such that} \ x^m \overset {n}{ \equiv } 1 \ ; \\ \text {for all integers} \ x \ \text {coprime to} \ n \ }.$$

---

En tu caso la respuesta es:

$$ \psi ( \color {Red}{2^4} . 3^3 . 5^2 . 7) = \text {lcm} \Big ( \psi ( \color {Red}{2^4}); \ \psi (3^3), \ \psi (5^2), \ \psi (7) \Big ) = \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text {lcm} \Big ( \color {Red}{2^2}; 2 \times 3^2, 4 \times 5, 6 \Big ) = 2^2 \times 3^2 \times 5 = 180 . $$