[argentinator]

Con razonamientos parecidos se obtendría que

\[ LCM_n(a,b) = \gcd(n,\hbox{lcm}(a,b))\cdot U_n.\]

[argentinator]

Vuelvo a reconciliarme con el resultado.

Si \(g,\gamma\), son maximales en \(GCD_n(a,b)\),
entonces \(\gcd(n,g)|\gamma\) y \(\gcd(n,\gamma)|g\),
con lo cual existen \(x,y\), tal que:
\(gx\equiv\gamma\) y \(\gamma y\equiv g\),
de donde \(gxy\equiv g\),
y así \(xy\equiv 1\) (estoy asumiendo \(g\not\equiv 0\)),
y por lo tanto \(x\) es una unidad,
mostrando así que \(g\) y \(\gamma\) difieren solamente en un factor que es una unidad.

Esto que hice vuelve a estar mal. 

El elemento \(u=xy\) no tiene por qué ser 1.
Bien podría ser otra cosa.
Por ejemplo, si \(g\) es idempotente, entonces \(g^g=g\),
y podría suceder que \(u=g\).

____________________________

De hecho encontré un contrajemplo a lo que se viene afirmando en el hilo, en \(\mathbb Z_{24}\).

Sean \(a=8,b=16\in\mathbb Z_{24}\).
Los divisores no unidades de \(a=8\) son: 2, 4, 8, 10, 14, 16, 20, 22.
Los divisores no unidades de \(b=16\) son los mismos.
Tomando \(\gcd(n,a,b) =\gcd(24,8,16) = 4\), se obtiene que \(g=4\)
ESTO ESTÁ MAL DE NUEVO AHHHH! 
Me quiero matar.
El mcd(24,8,16) = 8.

es un común divisor de \(a,b\),
pero no es un máximo común divisor,
ya que 8 es un común divisor de \(a,b\), pero 8 no es divisor de 4.

_____________________

[argentinator]

Creo que la solución sería la siguiente.

Definir y denotar:
\[n = \prod_j p_j^{n_j}.\]
\[a = \prod_j p_j^{a_j}.\]
\[b = \prod_j p_j^{b_j}.\]
\[d = \gcd(a,b) = \prod_j p_j^{d_j}.\]

MODIFICADO DESDE ACÁ...

Se tiene que \(d_j=\min(a_j,b_j)\).

\[\Gamma = \gcd(n,a,b) = \prod_j p_j^{\Gamma_j}.\]

Se tiene que \(\Gamma_j=\min(n_j,d_j)\leq d_j.\)

Tomar un número \(m = \prod p_j^{m_j}\), tal que:

\[\Gamma_j\leq d_j\]


Entonces \(m\) debiera ser un máximo divisor común de \(a,b\),
ya que \(\gcd(n,m)|a,b\) y además \(\Gamma |m\).

[argentinator]

Yo ya no sé qué probé o qué desprobé. 

Me estoy volviendo loco con números naturales... para variar.

Si \(\Gamma=\gcd(n,a,b)\), entonces \(\Gamma | n\) y \(\Gamma|\gcd(a,b)\).
Como \(\Gamma = \gcd(n,\Gamma)|a,b\),
resulta que \(\Gamma\) es un divisor común de \(a,b\).
Es cierto que es un máximo común divisor, y el razonamiento es sencillo.

Si \(\gamma\) es un divisor común en \(\mathbb Z_n\) de \(a,b\),
entonces \(\gcd(n,\gamma)|a,b\), luego también \(\gcd(n,\gamma)|n,\Gamma\),
por lo tanto \(\gcd(n,\gamma)|\Gamma\),
y esto prueba que \(\gamma\preceq_n\Gamma\).

Lo que faltaría es ver si hay otros elementos que sean máximos comunes divisores,
sin contar productos por unidades.

[argentinator]

Me parece que sale bastante fácil probar que
todo máximo común divisor \(g\) tiene que satisfacer que
 \(\gcd(n,g) = \gcd(n,a,b)=\gcd(n,\Gamma\).

Eso caracterizaría a todos los máximos comunes divisores de \(\mathbb Z_n\).

Si a alguien le interesa, escribo el razonamiento.
Y si no, cierro el asunto acá.

[Luis Fuentes]

Hola

Grosso modo:

 En cualquier anillo conmutativo, si \( a|x \), es decir, \( ab=x \) entonces \( au(u^{-1}b)=x \), es decir, \( au|x \) para cualquier unidad.

 Por tanto el conjunto de divisores de un elemento es invariante por productos por unidades, y de ahí el \( gcd \) de dos números. Asi trabajaremos con los divisores "salvo producto por unidad".

 Ahora en \( \Bbb Z_n \) dado \( x\in \Bbb Z_n \) se tiene que \( a|x \) si:

\( ab+nk=x \)

 para \( bmk \) enteros. La ecuación diofántica tiene solución cuando \( mcd(a,n)|x \); dado que si \( d=mcd(a,n) \) entonces \( a=da' \) con \( a' \) coprimo con \( n \) (y por tanto unidad en \( \Bbb Z_n \)) y estamos considerando divisores salvo unidades, concluimos que los divisores de \( x \) en \( \Bbb Z_n \) son (salvo producto por unidad) los divisores de \( n \) comunes a \( x \).

 De ahí \( gcd_{\Bbb Z_n}(x,y) \) será el "mayor" divisor común de \( x,y \); pero por lo que acabamos de ver eso equivale al "mayor" divisor común de \( x,y,n \) y de todo esto:

\( gcd_{\Bbb Z_n}(a,b)=gcd_{\Bbb Z}(n,a,b)\cdot Unidades(\Bbb Z_n) \)

 Este fue mi punto de vista a falta de comprobar algún detalle.

 Lo que está en rojo es falso. Tengo pendiente revisar todo esto despacio.

Saludos.

[geómetracat]

Algunos comentarios sobre este tema.

Normalmente no se suele tratar la divisibilidad en anillos que no sean dominios de integridad, porque no se comporta demasiado bien con los divisores de cero. En particular, deja de ser cierto que \( d \mid d′ \) y \( d′ \mid d \) implica que \( d′=du \) con \( u \) unidad.

Lo que sí sigue siendo cierto en general es que el mcd de dos elementos (si existe) está definido salvo asociado, donde ahora decimos que dos elementos \( d,d′ \) son asociados si \( d \mid d′ \) y \( d′ \mid d \) (esto se sigue fácilmente de la definición de mcd).

Se puede estudiar cuándo dos elementos son asociados en \( \Bbb Z_n \). Si \( x,y \in \Bbb Z_n \) son asociados, \( x=ya \), \( y=xb \), luego \( x=abx \). Pasando a \( \Bbb Z \) esto quiere decir que la ecuación diofántica \( x=axb+nu \) en \( b,u \) tiene solución. Esto ocurre si y solo si \( mcd(ax, n) \mid x \).
Ahora, dado un primo \( p \) que divide a \( n \), sea \( p^k \) la mayor potencia de \( p \) que divide a \( x \). Si \( p \mid a \), como tenemos \( mcd(ax, n) \mid x \) necesariamente \( p^{k+1} \not\mid n \). Y recíprocamente, si esta condición se cumple para todo primo \( p \) que divida a \( n \), tendremos \( mcd(ax, n) \mid x \) y por tanto \( y=xa \) será asociado de \( x \).

Vamos a estudiar cuándo un asociado es también asociado por una unidad. Es decir, supongamos que tenemos \( x,y \) asociados, de forma que \( y=xa \), \( x=yb \), pero también que \( y=xu \) con \( u \) unidad. Entonces, \( xa=xu \), de donde \( x(a-u)=0 \), o pasando a \( \Bbb Z \), \( n \mid x(a-u) \).
Pongamos \( n=p_1^{a_1}\dots p_k^{a_k} q_1^{a_1} \dots q_n^{a_n} \), donde los \( p_i \) son los primos que dividen a \( a \) y los \( q_i \) los que no dividen a \( a \). Por la condición de asociado, tenemos que \( p_1^{a_1}\dots p_k^{a_k} \mid x \). Sea \( n' = q_1^{a_1} \dots q_n^{a_n} \) y tomemos \( u := a-n' \). Entonces, por un lado \( u \) es una unidad en \( \Bbb Z_n \), porque es coprimo tanto con los \( p_i \) (que dividen a \( a \) pero no a \( n' \)) como con los \( q_i \) (que dividen a \( n' \) pero no a \( a \)). Y por otro lado, \( x(a-u)=xn' \) por lo que \( n \mid x(a-u) \).

Resumiendo, todo asociado de \( x \) en \( \Bbb Z_n \) es de hecho también asociado de \( x \) por una unidad. Por lo tanto, si no me he equivocado en nada, la fórmula de Luis es correcta.

[argentinator]

Algunos comentarios sobre este tema.

Normalmente no se suele tratar la divisibilidad en anillos que no sean dominios de integridad, porque no se comporta demasiado bien con los divisores de cero. En particular, deja de ser cierto que \( d \mid d′ \) y \( d′ \mid d \) implica que \( d′=du \) con \( u \) unidad.

Asumo que estás hablando ahí de divisibilidad en \(\mathbb Z_n\).
Pero me cuesta seguirte porque a veces no entiendo del todo si \(r|s\) significa divisibilidad en \(\mathbb Z\) o en \(\mathbb Z_n\).
Por eso yo uso \(\preceq_n\) para divisibilidad en \(\mathbb Z_n\).
Aunque se podría usar una notación como \(r \mid_n s\).

Lo que sí sigue siendo cierto en general es que el mcd de dos elementos (si existe) está definido salvo asociado, donde ahora decimos que dos elementos \( d,d′ \) son asociados si \( d \mid d′ \) y \( d′ \mid d \) (esto se sigue fácilmente de la definición de mcd).

Se puede estudiar cuándo dos elementos son asociados en \( \Bbb Z_n \). Si \( x,y \in \Bbb Z_n \) son asociados, \( x=ya \), \( y=xb \), luego \( x=abx \). Pasando a \( \Bbb Z \) esto quiere decir que la ecuación diofántica \( x=axb+nu \) en \( b,u \) tiene solución. Esto ocurre si y solo si \( mcd(ax, n) \mid x \).
Ahora, dado un primo \( p \) que divide a \( n \), sea \( p^k \) la mayor potencia de \( p \) que divide a \( x \). Si \( p \mid a \), como tenemos \( mcd(ax, n) \mid x \) necesariamente \( p^{k+1} \not\mid n \).

Ahí no entiendo la vuelta. Ya era cierto, por la definición de \(k\), que \(p^{k+1}\not\mid n\).
A menos que te estés refiriendo a otra cosa... 

Y recíprocamente, si esta condición se cumple para todo primo \( p \) que divida a \( n \), tendremos \( mcd(ax, n) \mid x \) y por tanto \( y=xa \) será asociado de \( x \).

Creo que no entendí demasiado el argumento...
Por lo general, se usa que:
\(r\mid_n s\) sii \(r x\equiv s\mod(n)\) tiene solución sii \(\gcd(n,r) \mid_Z s\).

Pero es fácil ver que eso es equivalente a \(\gcd(n,r)\mid_Z\gcd(n,s)\),
por la mera definición de \(\gcd\), sin necesidad de mirar los divisores primeros.

Así que, lo que digo es que \(r,s\), son asociados sii \(\gcd(n,r) = Z\gcd(n,s)\).

Vamos a estudiar cuándo un asociado es también asociado por una unidad. Es decir, supongamos que tenemos \( x,y \) asociados, de forma que \( y=xa \), \( x=yb \), pero también que \( y=xu \) con \( u \) unidad. Entonces, \( xa=xu \), de donde \( x(a-u)=0 \), o pasando a \( \Bbb Z \), \( n \mid x(a-u) \).
Pongamos \( n=p_1^{a_1}\dots p_k^{a_k} q_1^{a_1} \dots q_n^{a_n} \),

Tendrías que cambiar el literal para los exponentes de los \(q\)'s, pero creo que no es muy relevante para entender lo que sigue.

donde los \( p_i \) son los primos que dividen a \( a \) y los \( q_i \) los que no dividen a \( a \). Por la condición de asociado, tenemos que \( p_1^{a_1}\dots p_k^{a_k} \mid x \). Sea \( n' = q_1^{a_1} \dots q_n^{a_n} \) y tomemos \( u := a-n' \). Entonces, por un lado \( u \) es una unidad en \( \Bbb Z_n \), porque es coprimo tanto con los \( p_i \) (que dividen a \( a \) pero no a \( n' \)) como con los \( q_i \) (que dividen a \( n' \) pero no a \( a \)). Y por otro lado, \( x(a-u)=xn' \) por lo que \( n \mid x(a-u) \).

Estaba entusiasmado leyendo tu argumento, pero al final creo que no tiene sentido cómo termina la historia, porque ya tenías por hipótesis que \(n|x(a-u)\).
No sé a qué llegaste.

Así que aún no me creo del todo lo que sigue:

Resumiendo, todo asociado de \( x \) en \( \Bbb Z_n \) es de hecho también asociado de \( x \) por una unidad. Por lo tanto, si no me he equivocado en nada, la fórmula de Luis es correcta.

[argentinator]

En realidad sí creo que es verdad,
lo que no creo es el argumento.

[argentinator]

Creo que el argumento que me convence es éste:

Supongamos que \(r\equiv s \mod(n)\), \(s\equiv r\mod(n)\).
O sea, son "asociados" según tu terminología (¿esa es la terminología usual?).

Tenemos que existen \(\alpha,\beta \in\mathbb Z_n\) tales que
\(s\equiv \alpha r\),
\(r\equiv\beta s\),
de donde
\(r\equiv \gamma r\), donde \(\gamma = \alpha\beta\).

Esa ecuación, con \(\gamma\) como incógnita, tiene solución, obviamente,
y todas las soluciones \(\gamma\) se pueden encontrar mediante
\(\gamma = \xi + j\, n /  \rho\),
donde \(\rho = \gcd(n,r)\),
y \(\xi\) es la única solución a la ecuación:

\[ \dfrac r\rho \xi \equiv \dfrac r\rho \mod(\nu); \qquad n/\gcd(n,r).\]

Notamos que hay solución única porque
\(R=\dfrac r\rho\) es coprimo con
\(N=n/\gcd(n,r)=n/\rho\).
Y entonces esa única solución no puede ser otra que \(\xi=1\).

Luego, las soluciones son
\(\gamma = \gamma_j = 1 + j \, N\),
para \(0\leq j<\rho\).

Si un primo \(p\) fuera divisor común de \(n\) y de \(\gamma\),
entonces no puede ser divisor de \(N\),
porque en tal caso sería divisor de \(1=j\,N-\gamma\).
Así que \(p\mid \rho=\gcd(n,r)\).
En particular, \(p\leq \rho \).

Sea \(j\) el mínimo número \(0\leq j<\rho\) tal que \(p\mid_{\mathbb Z} (1+jN)\).
Si \(j=0\), entonces estamos ante la unidad \(1\), que no es divisible por \(p\).
Por lo tanto, asumimos que \(j>0\).
Sea \(j = qp+c\), dado por el algoritmo de la división, al dividir por \(p\).

Si \(c>0\), se tiene \(c<j\), y además
\(p\mid_{\mathbb Z} (1+jN-pqN) = (1+cN)\), contradiciendo la minimalidad de \(j\)
si es que era \(q>0\), por lo tanto \(q = 0,j<p\).


LO QUE SIGUE YA NO SIRVE...


Luego \(c=0\).

Pero en ese caso \(j\) es múltiplo de \(p\), lo que implica que \(p\mid 1\), absurdo.

Por lo tanto, no hay divisores primos comunes de \(n\) y alguno de los números
\(\gamma=\gamma_j=(1+jN)\).
Es decir, son coprimos, y por lo tanto todos ellos son unidades.