[argentinator]

No he usado aún el Teorema Chino del Resto.

Si \(m=p^e\), para algún \(e>0\),
supongamos que \(\rho \equiv u\rho\mod(m)\),
con \(\rho\) que no sea una unidad en \(\mathbb Z_m\).

Entonces \(\rho = \alpha p ^k\), \(1\leq k< e\), con \(\gcd(\alpha,p) = 1\).
Se sigue que \(\gcd(m,\rho)=p^k\), con lo cual
\(p^k\equiv u p^k \mod(m)\).

Esto implica que \(p^e \mid p^k(1-u)\), con lo cual \(p^{e-k}\mid 1 - u\).
Por lo tanto \(p\mid 1 - u\).
Pero entonces \(u\) es coprimo con \(p\),
y por lo tanto es una unidad.

Creo que ahora bastaría aplicar el Teorema chino del resto a un producto de potencias de primos.

NOTA: AL FINAL NO PUEDO SEGUIR POR ACÁ, SINO QUE RETOMO EL CAMINO DEL POST ANTERIOR.

[geómetracat]

argentinator, no puedes pretender demostrar que si \( r \equiv \gamma r \mod (n) \) entonces \( \gamma \) es una unidad porque eso es falso.
Por ejemplo, en \( \Bbb Z_6 \), tienes \( 4=2\cdot 2 \) y \( 2 =4\cdot 2 \) (a partir de ahora pongo igualdades en lugar de congruencias, supongo que se entiende), por lo que \( 2 \) y \( 4 \) son asociados, y también tienes \( 4=4\cdot 4 \), y \( 4 \) no es coprimo con \( 6 \).

Lo máximo que uno puede aspirar a probar es que si \( x,y \) son asociados en \( \Bbb Z_n \) (de forma que \( y=xa, x=yb \) con \( a,b \) quizás no unidades), también son asociados por una unidad. Es decir, que existe una unidad \( u \) tal que \( y=xu, x=yu^{-1} \).

Por ejemplo, en el caso de arriba teníamos \( 4=2\cdot 2 \) y \( 2=4\cdot 2 \), pero también se cumple \( 4=2\cdot 5 \) y \( 2=4\cdot 5 \), y \( 5 \) es una unidad en \( \Bbb Z_6 \). Así pues, \( 4 \) y \( 2 \) también son asociados por una unidad.

Esto es lo que afirmo que sucede en general, y sigo pensando que el argumento que esbocé en el mensaje anterior funciona bien, pero tienes razón en que no se entiende mucho porque fui escribiendo el mensaje sobre la marcha y está bastante mal escrito. Si tengo tiempo y acceso a un ordenador este fin de semana (este mensaje lo estoy escribiendo desde el móvil), intentaré escribir el argumento completo con más cuidado, y si quieres discutimos sobre ese mensaje.

Por cierto, sobre la nomenclatura de "asociado". Es nomenclatura estándar en dominios de integridad, pero ahí es lo mismo decir \( x\mid y \) y \( y \mid x \) que decir \( y=xu \) con \( u \) unidad.
En anillos arbitrarios son dos conceptos diferentes y el segundo es más fuerte que el primero. Por lo poco que he visto no parece haber demasiado acuerdo en la nomenclatura entre distintos autores. Algunos llaman a lo primero "asociados" (como yo) y a lo segundo "fuertemente asociados". Otros llaman a lo primero "débilmente asociados" y a lo segundo "asociados". Y probablemente hay aún más variantes.

[argentinator]

argentinator, no puedes pretender demostrar que si \( r \equiv \gamma r \mod (n) \) entonces \( \gamma \) es una unidad porque eso es falso.
Por ejemplo, en \( \Bbb Z_6 \), tienes \( 4=2\cdot 2 \) y \( 2 =4\cdot 2 \) (a partir de ahora pongo igualdades en lugar de congruencias, supongo que se entiende), por lo que \( 2 \) y \( 4 \) son asociados, y también tienes \( 4=4\cdot 4 \), y \( 4 \) no es coprimo con \( 6 \).

Sí, ya me había percatado de que estaba mal pretender probarlo así.
Lo había puesto en un mensaje, pero que lo borré porque estaba el resto todo mal.

Igual con la potencia de un primo creo que lo probé en mi post anterior.
No funcionaría con productos de primos distintos.

A la unidad habrá que construirla.

[argentinator]

Las cuentas que presentaste no tienen en cuenta el valor \(b\),
y por eso le perdí la fe, porque no veía cómo arreglarlo.
(Aunque con este problema no estoy viendo nada, así que ya eso es otro problema  mayor).

A mí sólo se me ocurre tratar de usar el Teorema Chino del Resto, o lo que se le parezca.

Disculpá que use otras letras, pero es que las \(x,y\), yo las prefiero como incógnitas,
y me resulta más fácil usar cualesquiera otras.

Sean \(\gamma,\Gamma\) asociados en \(\mathbb Z_n\).
Las ecuaciones en congruencias
 \(\Gamma \equiv \xi \gamma,\qquad \gamma\equiv \zeta\Gamma\mod(n)\)
tienen solución.

Sea \(n=\prod p_i^{e_i} = \prod P_i\), donde he denotado \(P_i=p_i^{e_i}\).
Por lo tanto, tienen solución las ecuaciones
\(\Gamma\equiv \xi_j\gamma,\qquad \gamma\equiv\zeta_j\Gamma\mod(P_j)\), todo \(j\).

De ahí sale \(\Gamma\equiv (\xi_j\zeta_j) \Gamma\mod(P_j)\), todo \(j\).

Asumiendo que esté bien lo que probé sobre módulos que son potencias de primos,
tendríamos que \(\omega_j=\xi_j\zeta_j\) son unidades de \(\mathbb Z_{p_j}\).

Por lo tanto, también lo son \(\xi_j,\zeta_j\), siendo además uno inverso del otro  en dicho anillo.

Para cada \(j\), sea \(N_j=n/P_j\), que es coprimo con \(P_j\).
Existe único inverso \(\nu_j\) tal que \(N_j\nu_j\equiv 1\mod(P_j)\).

Ahora sea \(u=\sum_j \nu_j N_j\zeta_j\).
Claramente, \(u\equiv \zeta_j\mod(P_j)\), todo \(j\).

Por lo tanto \(\gamma \equiv u\Gamma\mod(P_j)\), todo \(j\).

Como \(u\) es coprimo con todo \(P_j\), es coprimo con \(n\),
así que es una unidad en \(\mathbb Z_n\).

Luego \(\gamma - u\Gamma \equiv 0\mod(P_j)\),
con lo cual \(P_j\,\mid\,\gamma-u\Gamma\), todo \(j\),
y por ser \(P_j\) coprimos entre sí,
resulta que \(n=\prod_j P_j \,\mid\, \gamma-u\Gamma\),
o sea que:
\[\gamma\equiv u\Gamma\mod(n).\]

[argentinator]

Por cierto, sobre la nomenclatura de "asociado". Es nomenclatura estándar en dominios de integridad, pero ahí es lo mismo decir \( x\mid y \) y \( y \mid x \) que decir \( y=xu \) con \( u \) unidad.
En anillos arbitrarios son dos conceptos diferentes y el segundo es más fuerte que el primero. Por lo poco que he visto no parece haber demasiado acuerdo en la nomenclatura entre distintos autores. Algunos llaman a lo primero "asociados" (como yo) y a lo segundo "fuertemente asociados". Otros llaman a lo primero "débilmente asociados" y a lo segundo "asociados". Y probablemente hay aún más variantes.

Gracias por el comentario.

La distinción es importante.
Habrá que ser explícito en cada caso entonces.

[geómetracat]

A primera vista yo veo bien el argumento con el teorema chino del resto. 

De todas formas, mañana intento escribir con más detalle lo que pensé yo. Sobre lo de que no uso el valor de \( b \) es porque no hace falta para nada. En realidad lo único que me interesa dado un \( x \) es saber para qué elementos \( a \) son asociados \( x \) y \( xa \), y eso depende únicamente de \( n,x,a \).

[argentinator]

Mi prueba tiene imperfecciones pero son soluciobables.

Falra clnsiderar el caso en que algún \(P_j \) divida a \(\Gamma\),
pero se arregla eligiendo a 1 como unidad para ese j.

Y la misma idea general luego  funciona.

[argentinator]

Nunca creí que iba a darme tantos tortazoz contra \(  Z_n \).

[geómetracat]

Mi prueba tiene imperfecciones pero son soluciobables.

Falra clnsiderar el caso en que algún \(P_j \) divida a \(\Gamma\),
pero se arregla eligiendo a 1 como unidad para ese j.

Y la misma idea general luego  funciona.

Justo venía a decir esto. De hecho, el que haya \( P_j \) que dividan a \( \Gamma \) es lo que hace que se puedan tener asociados \( \gamma \) y \( \Gamma = \gamma \xi \) con \( \xi \) no unidad. Pero ahora sí estoy bastante convencido de que esto funciona (con el arreglo que mencionas).

Por completar un poco y zanjar el tema, escribo un poco mejor lo que pensé el otro día, aunque en realidad creo que la demostración usando el teorema chino del resto es más clara.

Notación: Usaré \( \mid \) y \( = \) para la relación de divisibilidad y la igualdad en \( \Bbb Z \), y \( \mid_n, =_n \) para la divisibilidad e igualdad en \( \Bbb Z_n \). Por comodidad y para no cargar mucho la notación, usaré indistintamente letras \( x,y,a,b,\dots \) tanto para enteros como para sus clases de equivalencia en \( \Bbb Z_n \). Espero que esto no cause confusión. Usaré \( mcd(a,b) \) para el máximo común divisor (positivo) en \( \Bbb Z \). El conjunto de los máximos comunes divisores de \( a,b \) en \( \Bbb Z_n \) lo denotaré por \( mcd_{\Bbb Z_n}(a,b) \).

Diremos que dos elementos \( x,y \in \Bbb Z_n \) son asociados si \( x \mid_n y \) y \( y \mid_n x \). Diremos que son asociados por una unidad si existe \( u \in U(\Bbb Z_n) \) tal que \( y=_n xu \), donde \( U(\Bbb Z_n) \) denota las unidades de \( \Bbb Z_n \).

Usaré varias veces el siguiente resultado elemental:
Lema: \( x \mid_n y \) si y solo si \( mcd(x,n) \mid y \).
Demostración: \( x \mid_n y \) es equivalente a que exista \( u \) tal que \( y=_n xu \), que a su vez es equivalente a que la ecuación diofántica \( y = xu + nv \) en \( u,v \) tenga solución. Pero esto es equivalente a que \( mcd(x,n) \mid y \).

El primer resultado es una caracterización de los elementos \( a \) tales que \( x \) y \( xa \) son asociados.Para enunciarlo más cómodamente, usaremos la siguiente nomenclatura. Dado un entero \( a \), escribimos \( n=p_1^{e_1}\dots p_k^{e_k}q_1^{f_1}\dots q_l^{f_l} \) donde los \( p_i \) son primos que dividen a \( a \) y \( q_i \) son primos que no dividen a \( a \). Decimos que \( n=n'n'' \) es la descomposición de \( n \) asociada a \( a \), donde \( n' := p_1^{e_1}\dots p_k^{e_k} \) y \( n'':=q_1^{f_1}\dots q_l^{f_l} \). Si \( k=0 \) o \( l=0 \) ponemos \( n'=1 \) o \( n''=1 \), respectivamente.

Proposición 1: Sean \( n,x,a \) enteros y \( n=n'n'' \) la descomposición de \( n \) asociada a \( a \). \( x \) y \( xa \) son asociados en \( \Bbb Z_n \) si y solo si \( n' \mid x \).
Demostración: Como \( x \mid_n xa \), tenemos que \( x, xa \) son asociados en \( \Bbb Z_n \) si y solo si \( xa \mid_n x \), que por el lema es equivalente a \( mcd(ax,n) \mid x \).
Sea \( p \) un primo cualquiera, y sean \( p^e, p^f, p^l \) las mayores potencias de \( p \) que dividen a \( x,a,n \) respectivamente. Entonces, la mayor potencia de \( p \) que divide a \( mcd(ax,n) \) es \( p^{min(e+f,l)} \). Por tanto, \( mcd(ax,n) \mid x \) si y solo si para todo primo \( p \) se cumple \( p^{min(e+f,l)} \mid p^e \) o equivalentemente, si \( min(e+f,l) \leq e \). Si \( f=0 \) (que es equivalente a que \( p \not\mid a \)), esta desigualdad siempre se cumple. Si en cambio \( f>0 \) (equivalente a \( p \mid a \)), se cumple la desigualdad si y solo si \( l \leq e \), que es equivalente a decir que \( p^l \mid p^e \). Observemos también que si \( p \not\mid n \), entonces \( l=0 \) y siempre se cumple \( p^l \mid p^e \).
Resumiendo la discusión anterior, hemos visto que \( x \) y \( xa \) son asociados si y solo si para todo primo \( p \) que divida a la vez a \( a \) y a \( n \), la mayor potencia de \( p \) que divide a \( n \) debe dividir también a \( x \). Esto es equivalente a decir que \( n' \mid x \).

Proposición 2: Si \( x,y \) son asociados en \( \Bbb Z_n \), también son asociados por unidades.
Demostración: Supongamos que \( x,y \) son asociados. En particular, podemos escribir \( y=_n xa \), y \( x,xa \) son asociados. Sea \( n=n'n'' \) la descomposición de \( n \) asociada a \( a \). Por la proposición 1, tenemos que \( n' \mid x \). Definimos ahora \( u:=a-n'' \). Sea \( p \) un primo tal que \( p \mid n \). Si \( p \mid a \), entonces por definción de \( n'' \) se tiene que \( p \not\mid n'' \), luego \( p \not\mid u \). Si \( p \not\mid a \), entonces de nuevo por definición, \( p \mid n'' \), luego \( p\not\mid u \). Es decir, \( u \) es coprimo con \( n \), y por tanto es una unidad en \( \Bbb Z_n \). Finalmente, como \( n' \mid x \), \( n'' = a-u \) y \( n',n'' \) son coprimos, tenemos que \( n=n'n'' \mid x(a-u) = xa - xu \). Luego \( xa =_n xu \), de donde \( y =_n xa =_n xu \) es asociado por unidades de \( x \). Esto prueba que todo par de asociados en \( \Bbb Z_n \) es también asociado por unidades.

Ahora, una vez demostrada la proposición 2 ya sea de esta manera o con el argumento del teorema chino del resto de argentinator, podemos demostrar el siguiente:
Teorema: \( mcd_{\Bbb Z_n}(a,b) = mcd(a,b) \cdot U(\Bbb Z_n) \)
Demostración: Primero vemos que \( mcd(a,b) \) es un máximo común divisor de \( a,b \) en \( \Bbb Z_n \). Como \( mcd(a,b) \mid a,b \) también se cumple \( mcd(a,b) \mid_n a,b \). Sea ahora \( d \) con \( d \mid_n a \) y \( d \mid_n b \), y vamos a probar que \( d \mid_n mcd(a,b) \). Por el lema, \( mcd(d,n) \mid a \) y \( mcd(d,n) \mid b \), luego \( mcd(d,n) \mid mcd(a,b) \), y por tanto \( mcd(d,n) \mid_n mcd(a,b) \). Por otro lado, como \( mcd(d,n) \mid mcd(d,n) \), por el lema tenemos que \( d \mid_n mcd(d,n) \). En definitiva, \( d \mid_n mcd(d,n) \mid_n mcd(a,b) \). Luego efectivamente, \( mcd(a,b) \) es un máximo común divisor de \( a,b \) en \( \Bbb Z_n \).
Por otro lado, si \( g \) es otro máximo común divisor de \( a,b \) en \( \Bbb Z_n \), por definición de máximo común divisor se debe tener \( g \mid_n mcd(a,b) \) y \( mcd(a,b) \mid_n g \), es decir, \( g \) y \( mcd(a,b) \) son asociados. Pero por la proposición 2 deben ser asociados por una unidad. Por lo tanto, \( g=mcd(a,b)u \) con \( u\in U(\Bbb Z_n) \). Esto acaba la demostración del teorema.

Como observación final, esto es lo mismo que la fórmula que puso Luis, \( mcd_{\Bbb Z_n}(a,b) = mcd(a,b,n) \cdot U(\Bbb Z_n) \), porque se puede comprobar que \( mcd(a,b) \) y \( mcd(a,b,n) \) son asociados en \( \Bbb Z_n \).