noticias y última hora

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.

Artículos relacionados

Autor: ^DiAmOnD^ |  Publicado el 10 de November de 2009
Envia este post a Twitter
Categorías: Juegos |  Imprime este post Imprime este post

Sin comentarios

  1. Manzano | 10 de November de 2009 | 10:57

    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.

  2. vengoroso | 10 de November de 2009 | 11:52

    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.

  3. vengoroso | 10 de November de 2009 | 11:54

    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?

  4. vengoroso | 10 de November de 2009 | 15:53

    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…

  5. andres | 10 de November de 2009 | 16:03

    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}

  6. vengoroso | 10 de November de 2009 | 16:15

    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.

  7. M | 10 de November de 2009 | 16:56

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

  8. Manzano | 10 de November de 2009 | 17:04

    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.

  9. M | 10 de November de 2009 | 19:29

    Manzano, eso último que comentas es cierto y se puede ver usando la multiplicatividad de la \varphi. Si n=p^k\cdot m (con p primo y mcd(p,m)=1) entonces \varphi(n)=p^{k-1}(p-1)\varphi(m). Y si p\neq 2 entonces debe ser que k=1 y p-1 potencia de 2. Pero resulta, además, que si p=2^\alpha+1 es primo, entonces \alpha=2^\beta , obteniendo un primo de Fermat.

    http://gaussianos.com/construcciones-con-regla-y-compas-iii-los-poligonos-regulares/

Comentarios cerrados.