Uno de congruencias

Ya que nuestro artículo de ayer lunes está relacionado con congruencias aquí os traigo como problema para esta semana uno también relacionado con ellas. Ahí va el enunciado:

Determina todos los enteros positivos n \ge 2 que satisfacen que para cualesquiera enteros positivos a,b primos relativos con n se cumple lo siguiente:

a \equiv b (mod \; n) si y sólo si ab \equiv 1 (mod \; n).

Suerte.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. Consideremos el grupo multiplicativo de las unidades módulo n, dado por

    U(n)=\{a\in\mathbb Z_n:\mbox{mcd}(a,n)=1\}

    Entonces, la condición requerida implica que a^2\equiv 1\ (\mbox{mod }n) para todo a\in U(n), es decir, para un valor de n que cumpla la condición tiene que ocurrir que todo elemento de U(n) tenga orden 2 como máximo, pero U(n) es un grupo cíclico de orden \varphi(n) donde \varphi es la función de Euler. De aquí deducimos que \varphi(n)\leq 2 y no es difícil demostrar que los únicos valores para los que esto se cumple son n=2, n=3, n=4 y n=6. Ahora bien, estos valores verifican la condición ya que U(n) tiene sólo uno o dos elementos y, por tanto, son los únicos.

    Publica una respuesta
  2. Cuidado, U(n) en general no es cíclico. Por ejemplo U(15) (que tiene orden 8 ) es isomorfo a \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z} . Dicho de otra forma, el grupo de Galois de una extensión ciclotómica no tiene por qué ser cíclico.
    Para el caso del problema, en principio no basta con los casos en los que \varphi(n) = 2 sino que es necesario descartar todos los casos en los que \varphi(n) = 2^k.

    Publica una respuesta
  3. Uff, el bicho con las gafillas deberia ser un 8 (el orden del grupo de unidades de los enteros módulo 15) y la última fórmula que no se ve debería poner \varphi(n) = 2^k. ¿Puedes corregirlo, DiAmOnD?

    Publica una respuesta
  4. He estado haciendo algunas cuentas, y para n=12,24 la condicion tambien se verifica: los grupo multiplicativo de unidades tienen ordenes 4 y 8 respectivamente pero son isomorfo a \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z} y \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}, me temo que va a hacer falta usar algo mas serio que la funcion de Euler…

    Publica una respuesta
  5. U(n) es cíclico cuando n=p,2,4,p^a, 2*p^a, con p primo impar
    es decir, tiene una raíz primitiva si n es de esa forma. Así 1,-1 cumplen con la propiedad para n={p,2,4,p^a, 2*p^a}

    Publica una respuesta
  6. Creo que lo tengo. Supongamos que n se descompone en factores primos como n=p_1^{e_1}\dotsm p_r^{e_r}, entonces el anillo de enteros modulon se descompone como \mathbb{Z}_n \cong \mathbb{Z}_{p_1^{e_1}} \times \dotsb \times \mathbb{Z}_{p_r^{e_r}} y por tanto para los grupos de unidades tenemos
    U(n) \cong U(p_1^{e_1})\times \dotsb \times U(p_r^{e_r}). Si tenemos un factor primo p mayor o igual a 5, entonces en \mathbb{Z}_{p^e} el elemento 2 es una unidad que no tiene orden 2 (porque su cuadrado es 4 que no es congruente con 1 modulo k para ningun k mayor que 5), por lo que el grupo de unidades tiene elementos de orden distinto de 2, y por tanto los naturales que buscamos se tienen que escribir de la forma n=2^r 3^s.

    Si s es mayor o igual que 2, razonando como antes vemos que 2 es una unidad de orden mayor que 2 en el correspondiente \mathbb{Z}_{3^s}, por lo que s debe ser 0 o 1.

    Si r es mayor o igual a 4, entonces el elemento 3 es una unidad en \mathbb{Z}_{2^r} y no tiene orden 2 porque 3^2 = 9 \not{\equiv} 1 \mod k para k mayor que 10, de manera que r debe estar entre 0 y 3.

    Esto muestra que las unicas opciones validas son n =  2,3,4,6,8,12,24.

    Publica una respuesta
  7. Estoy de acuerdo con la solución de vengoroso. Observemos que la solución dada es en esencia el teorema chino de los restos.

    Publica una respuesta
  8. Tienes razón, vengoroso, mi solución estaba mal. No obstante, esto me ha recordado un problema curioso, aunque muy fácil: ¿para qué valores de n se cumple que \varphi(n) es una potencia de 2? Creo que las soluciones coinciden justo con los números de lados que un polígono regular ha de tener para que sea constructible con regla y compás.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *