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
que satisfacen que para cualesquiera enteros positivos
primos relativos con
se cumple lo siguiente:
si y sólo si
.
Suerte.
Autor: ^DiAmOnD^ | Publicado el 10 de Noviembre de 2009
Envia este post a Twitter
Categorías: Juegos | 
Imprime este post
Manzano | 10 de Noviembre de 2009 | 10:57
Consideremos el grupo multiplicativo de las unidades módulo
, dado por
Entonces, la condición requerida implica que)
para todo )
, es decir, para un valor de 
que cumpla la condición tiene que ocurrir que todo elemento de )
tenga orden 
como máximo, pero )
es un grupo cíclico de orden )
donde 
es la función de Euler. De aquí deducimos que \leq 2)
y no es difícil demostrar que los únicos valores para los que esto se cumple son 
, 
, 
y 
. Ahora bien, estos valores verifican la condición ya que )
tiene sólo uno o dos elementos y, por tanto, son los únicos.
vengoroso | 10 de Noviembre de 2009 | 11:52
Cuidado,)
en general no es cíclico. Por ejemplo )
(que tiene orden 8 ) es isomorfo a 
. Dicho de otra forma, el grupo de Galois de una extensión ciclotómica no tiene por qué ser cíclico. = 2)
sino que es necesario descartar todos los casos en los que  = 2^k)
.
Para el caso del problema, en principio no basta con los casos en los que
vengoroso | 10 de Noviembre 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 = 2^k)
. ¿Puedes corregirlo, DiAmOnD?
vengoroso | 10 de Noviembre de 2009 | 15:53
He estado haciendo algunas cuentas, y para
la condicion tambien se verifica: los grupo multiplicativo de unidades tienen ordenes 4 y 8 respectivamente pero son isomorfo a 
y 
, me temo que va a hacer falta usar algo mas serio que la funcion de Euler…
andres | 10 de Noviembre 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}
vengoroso | 10 de Noviembre de 2009 | 16:15
Creo que lo tengo. Supongamos que
se descompone en factores primos como 
, entonces el anillo de enteros modulo
se descompone como 
y por tanto para los grupos de unidades tenemos
 \cong U(p_1^{e_1})\times \dotsb \times U(p_r^{e_r}))
. Si tenemos un factor primo 
mayor o igual a 5, entonces en 
el elemento 2 es una unidad que no tiene orden 2 (porque su cuadrado es 4 que no es congruente con 1 modulo 
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 
.
Si
es mayor o igual que 2, razonando como antes vemos que 2 es una unidad de orden mayor que 2 en el correspondiente 
, por lo que 
debe ser 0 o 1.
Si
es mayor o igual a 4, entonces el elemento 3 es una unidad en 
y no tiene orden 2 porque 
para 
mayor que 10, de manera que 
debe estar entre 0 y 3.
Esto muestra que las unicas opciones validas son
.
M | 10 de Noviembre 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.
Manzano | 10 de Noviembre 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
se cumple que )
es una potencia de 
? 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.
M | 10 de Noviembre de 2009 | 19:29
Manzano, eso último que comentas es cierto y se puede ver usando la multiplicatividad de la
. Si 
(con p primo y =1)
) entonces =p^{k-1}(p-1)\varphi(m))
. Y si 
entonces debe ser que 
y 
potencia de 2. Pero resulta, además, que si 
es primo, entonces 
, obteniendo un primo de Fermat.
http://gaussianos.com/construcciones-con-regla-y-compas-iii-los-poligonos-regulares/