Mostrar Mensajes
1
Teoría de números / m.c.d. y l.c.m. en Z/(n)
« en: 30 Diciembre, 2023, 05:51 pm »
Buenas.
Si algún alma algebrista tiene ganas de revisar estas cuentas, lo agradeceré.
Estoy procurando entender qué sentido tienen
el máximo común divisor (mcd)
y el mínimo común múltiplo (lcm)
en el anillo \(\mathbb Z_n=\mathbb Z/(n)\) de los enteros módulo \(n\).
La definición de m.c.d. en un anillo sería así:
Un elemento \(d\in \mathbb Z_n\) es uuuunnnnn
máximo común divisor de dos elementos \(a,b\in \mathbb Z_n\)
si \(d\) es divisor (respecto el producto del anillo \(\mathbb Z_n\)) de \(a,b\),
y si además, para todo otro elemento \(\delta\) que sea divisor de \(a,b\),
se cumple que \(\delta\) es divisor de \(d\).
Esa definición da lugar a que pueda haber todo un conjunto de varios elementos que sean máximos comunes divisores de \(a,b\).
O incluso podría pasar que no haya ninguno.
______________________
Para alegrar mis ojos, voy a introducir notación.
La notación \(r\preceq_n s\) significará que \(r\) es divisor de \(s\) en \(\mathbb Z_n\).
Esto significa que existe solución en las ecuación en congruencia: \(rx\equiv s\mod(n)\).
En símbolos:
\[ r\preceq_n s \quad \Leftrightarrow\quad \exists x\in \mathbb Z_n:\, rx \equiv s \, \mod (n).\]
Denotaremos \(GCD_n(a,b)\) al conjunto de máximos comunes divisores de \(a,b\) en \(\mathbb Z_n\).
Esto significa lo siguiente:
\[d \in GCD_n(a,b) \quad \Leftrightarrow \quad
d\preceq_n a, \; d\preceq_n b, \Big[ \forall \delta\in \mathbb Z_n:\,
\delta\preceq_n a,\;\delta \preceq_n b \quad\Rightarrow \quad \delta\preceq_n {\color{red}d}\Big].
\]
Sabemos que \(u\in \mathbb Z_n\) es una unidad (invertible con el producto) sii \(\hbox{mcd}(u,n) = 1\).
Denotemos \(U_n\) al conjunto de unidades de \(\mathbb Z_n\).
Todo elemento \(b\) es divisible en \(\mathbb Z_n\) por una unidad \(u\),
ya que basta tomar \(x = u^{-1}b\) (que existe por estar \(u\in U_n\)),
y en tal caso:
\[ u x \equiv u (u^{-1} b) \equiv b \mod(n).\]
Por lo tanto:
\[ \forall b\in \mathbb Z_n:\; \forall u\in U_n:\, u\preceq_n b.\]
Por otra parte, sabemos que las no-unidades son divisores de 0 en \(Z_n\), es decir:
\[ w\not\in \mathbb Z_n \quad \Leftrightarrow\quad \exists k\in\mathbb Z_n:\, wk\equiv 0\mod(n).\]
Por otra parte, sea\(\delta\) un divisor de \(u\) que no sea una unidad.
En ese caso, \(\delta\) es un divisor de 0.
Nos preguntamos cómo tendrían que ser las soluciones \(x\) de la siguiente ecuación:
\[ \delta x \equiv u \mod(n).\]
Multiplicando a ambos lados por \(u^{-1}\) se obtiene:
\[ \delta u^{-1} x \equiv 1 \mod(n). \]
Esto significa que \(v = \delta u^{-1}\), es invertible, o sea, un elemento de \(U_n\).
Por lo tanto, al multiplicar \(v\) por otra unidad, obtendremos una unidad.
Pero entonces \(\delta = (\delta u^{-1}) u = v u\) es una unidad,
en contra de lo supuesto.
Así que los únicos divisores de \(u\) son los elementos de \(U_n\).
__________________________
Ahora, razono así.
Sean \(a,b\in \mathbb Z_n\).
Supongamos que uno dellos, digamos \(b\), es un elemento de \(U_n\).
Entonces todo divisor común de \(a,b\), tiene que estar en \(U_n\).
Y si \(d\) es un común divisor divisible por todo otro divisor común de \(a,b\),
entonces \(d\) tiene que ser divisible por una unidad, lo cual era siempre cierto.
Por lo tanto:
\[GCD_n(a,b) = U_n.\]
______________________________
Supongamos ahora que \(a,b\), no son unidades.
Entonces \(a,b\), son ambos divisores de 0.
Si \(a=b=0\), entonces todo elemento de \(\mathbb Z_n\) es divisor de \(a,b\).
Sea \(d\) un máximo común divisor de \(a,b\).
Esto quiere decir que para todo \(\delta\) tal que \(\delta\preceq_n a,\,\delta\preceq_n b\),
se tiene también que \(\delta\preceq_n d\).
Si \(d \not\equiv 0 \mod(n)\), entonces no puede ser un máximo común divisor,
porque \(0\) es, en particular, divisor de \(a,b\), pero no sería divisor de \(d\).
Así que el único candidato a posible máximo común divisor de \(a = b=0\) es \(d=0\).
Sea \(\delta\) un divisor común de \(a=b=0\).
Claramente, \(\delta\) es un divisor de \(d=0\).
En conclusión: un elemento \(d\) es un máximo común divisor \(d\) de \(a=b=0\) si y sólo si \(d=0\).
\[GCD_n(0,0) = \{0\}.\]
__________________________________
Ahora supongamos que \(a,b\) son ambos divisores de 0,
pero que no son ambos 0 al mismo tiempo.
S.p.d.g. digamos que \(b\not\equiv 0\).
Sabemos que \(h\preceq_n a\) si y sólo si, respecto \(\mathbb Z\):
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;a,\]
en donde el mcd y la relación de divisibilidad están "miradas" en \(\mathbb Z\).
Si \(h\) es un divisor común (en \(\mathbb Z_n\)) de \(a,b\),
esto quiere decir que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;a,\qquad \hbox{mcd}(n,h)\;|\;b.\]
Esto es equivalente a pedir que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;(\mathbb Z)\hbox{mcd}(a,b). \]
Denotemos con \(g=(\mathbb Z)\hbox{mcd}(a,b)\).
Tenemos que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\; g. \]
Supongamos que \(d\) es un máximo común divisor en \(\mathbb Z_n\) de \(a,b\).
Tenemos, primero que nada, que:
\[ (\mathbb Z)\hbox{mcd}(n,d)\;|\; g. \]
En particular, esto implica que: \((\mathbb Z)\hbox{mcd}(n,d) \leq g.\)
Y además, si \(\delta\) es otro divisor común (en \(\mathbb Z_n\)) de \(a,b\), entonces no sólo tiene que ocurrir:
\[ (\mathbb Z)\hbox{mcd}(n,\delta)\;|\; g. \]
sino que también \(\delta\preceq_n d\), lo cual equivale a:
\[ (\mathbb Z)\hbox{mcd}(n,\delta)\;|\; d. \]
A PARTIR DE ACÁ ESTÁ MAL, ASÍ QUE LO ESCONDO EN SPOILER
Si algún alma algebrista tiene ganas de revisar estas cuentas, lo agradeceré.
Estoy procurando entender qué sentido tienen
el máximo común divisor (mcd)
y el mínimo común múltiplo (lcm)
en el anillo \(\mathbb Z_n=\mathbb Z/(n)\) de los enteros módulo \(n\).
La definición de m.c.d. en un anillo sería así:
Un elemento \(d\in \mathbb Z_n\) es uuuunnnnn
máximo común divisor de dos elementos \(a,b\in \mathbb Z_n\)
si \(d\) es divisor (respecto el producto del anillo \(\mathbb Z_n\)) de \(a,b\),
y si además, para todo otro elemento \(\delta\) que sea divisor de \(a,b\),
se cumple que \(\delta\) es divisor de \(d\).
Esa definición da lugar a que pueda haber todo un conjunto de varios elementos que sean máximos comunes divisores de \(a,b\).
O incluso podría pasar que no haya ninguno.
______________________
Para alegrar mis ojos, voy a introducir notación.
La notación \(r\preceq_n s\) significará que \(r\) es divisor de \(s\) en \(\mathbb Z_n\).
Esto significa que existe solución en las ecuación en congruencia: \(rx\equiv s\mod(n)\).
En símbolos:
\[ r\preceq_n s \quad \Leftrightarrow\quad \exists x\in \mathbb Z_n:\, rx \equiv s \, \mod (n).\]
Denotaremos \(GCD_n(a,b)\) al conjunto de máximos comunes divisores de \(a,b\) en \(\mathbb Z_n\).
Esto significa lo siguiente:
\[d \in GCD_n(a,b) \quad \Leftrightarrow \quad
d\preceq_n a, \; d\preceq_n b, \Big[ \forall \delta\in \mathbb Z_n:\,
\delta\preceq_n a,\;\delta \preceq_n b \quad\Rightarrow \quad \delta\preceq_n {\color{red}d}\Big].
\]
Sabemos que \(u\in \mathbb Z_n\) es una unidad (invertible con el producto) sii \(\hbox{mcd}(u,n) = 1\).
Denotemos \(U_n\) al conjunto de unidades de \(\mathbb Z_n\).
Todo elemento \(b\) es divisible en \(\mathbb Z_n\) por una unidad \(u\),
ya que basta tomar \(x = u^{-1}b\) (que existe por estar \(u\in U_n\)),
y en tal caso:
\[ u x \equiv u (u^{-1} b) \equiv b \mod(n).\]
Por lo tanto:
\[ \forall b\in \mathbb Z_n:\; \forall u\in U_n:\, u\preceq_n b.\]
Por otra parte, sabemos que las no-unidades son divisores de 0 en \(Z_n\), es decir:
\[ w\not\in \mathbb Z_n \quad \Leftrightarrow\quad \exists k\in\mathbb Z_n:\, wk\equiv 0\mod(n).\]
Por otra parte, sea\(\delta\) un divisor de \(u\) que no sea una unidad.
En ese caso, \(\delta\) es un divisor de 0.
Nos preguntamos cómo tendrían que ser las soluciones \(x\) de la siguiente ecuación:
\[ \delta x \equiv u \mod(n).\]
Multiplicando a ambos lados por \(u^{-1}\) se obtiene:
\[ \delta u^{-1} x \equiv 1 \mod(n). \]
Esto significa que \(v = \delta u^{-1}\), es invertible, o sea, un elemento de \(U_n\).
Por lo tanto, al multiplicar \(v\) por otra unidad, obtendremos una unidad.
Pero entonces \(\delta = (\delta u^{-1}) u = v u\) es una unidad,
en contra de lo supuesto.
Así que los únicos divisores de \(u\) son los elementos de \(U_n\).
__________________________
Ahora, razono así.
Sean \(a,b\in \mathbb Z_n\).
Supongamos que uno dellos, digamos \(b\), es un elemento de \(U_n\).
Entonces todo divisor común de \(a,b\), tiene que estar en \(U_n\).
Y si \(d\) es un común divisor divisible por todo otro divisor común de \(a,b\),
entonces \(d\) tiene que ser divisible por una unidad, lo cual era siempre cierto.
Por lo tanto:
\[GCD_n(a,b) = U_n.\]
______________________________
Supongamos ahora que \(a,b\), no son unidades.
Entonces \(a,b\), son ambos divisores de 0.
Si \(a=b=0\), entonces todo elemento de \(\mathbb Z_n\) es divisor de \(a,b\).
Sea \(d\) un máximo común divisor de \(a,b\).
Esto quiere decir que para todo \(\delta\) tal que \(\delta\preceq_n a,\,\delta\preceq_n b\),
se tiene también que \(\delta\preceq_n d\).
Si \(d \not\equiv 0 \mod(n)\), entonces no puede ser un máximo común divisor,
porque \(0\) es, en particular, divisor de \(a,b\), pero no sería divisor de \(d\).
Así que el único candidato a posible máximo común divisor de \(a = b=0\) es \(d=0\).
Sea \(\delta\) un divisor común de \(a=b=0\).
Claramente, \(\delta\) es un divisor de \(d=0\).
En conclusión: un elemento \(d\) es un máximo común divisor \(d\) de \(a=b=0\) si y sólo si \(d=0\).
\[GCD_n(0,0) = \{0\}.\]
__________________________________
Ahora supongamos que \(a,b\) son ambos divisores de 0,
pero que no son ambos 0 al mismo tiempo.
S.p.d.g. digamos que \(b\not\equiv 0\).
Sabemos que \(h\preceq_n a\) si y sólo si, respecto \(\mathbb Z\):
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;a,\]
en donde el mcd y la relación de divisibilidad están "miradas" en \(\mathbb Z\).
Si \(h\) es un divisor común (en \(\mathbb Z_n\)) de \(a,b\),
esto quiere decir que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;a,\qquad \hbox{mcd}(n,h)\;|\;b.\]
Esto es equivalente a pedir que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\;(\mathbb Z)\hbox{mcd}(a,b). \]
Denotemos con \(g=(\mathbb Z)\hbox{mcd}(a,b)\).
Tenemos que:
\[ (\mathbb Z)\hbox{mcd}(n,h)\;|\; g. \]
Supongamos que \(d\) es un máximo común divisor en \(\mathbb Z_n\) de \(a,b\).
Tenemos, primero que nada, que:
\[ (\mathbb Z)\hbox{mcd}(n,d)\;|\; g. \]
En particular, esto implica que: \((\mathbb Z)\hbox{mcd}(n,d) \leq g.\)
Y además, si \(\delta\) es otro divisor común (en \(\mathbb Z_n\)) de \(a,b\), entonces no sólo tiene que ocurrir:
\[ (\mathbb Z)\hbox{mcd}(n,\delta)\;|\; g. \]
sino que también \(\delta\preceq_n d\), lo cual equivale a:
\[ (\mathbb Z)\hbox{mcd}(n,\delta)\;|\; d. \]
A PARTIR DE ACÁ ESTÁ MAL, ASÍ QUE LO ESCONDO EN SPOILER
Spoiler
En particular, \(\delta\leq g\) y \(\delta\leq d\).
El hecho de que \(\delta\leq d\) nos muestra que, de existir un máximo común divisor \(d\),
éste tiene que ser único.
Así que, el valor de \(d\) ha de ser el elemento más grande de \(\mathbb Z_n\) (con el orden de \(\mathbb Z\)) tal que:
\[(\mathbb Z)\hbox{mcd}(n,d)\;|\; g = (\mathbb Z)\hbox{mcd}(a,b).\]
Por lo tanto, si
\[ d = \max\{d\in\mathbb Z_n\;:\; (\mathbb Z)\hbox{mcd}(n,d)\;|\; (\mathbb Z)\hbox{mcd}(a,b)\}, \]
entonces
\[GCD_n(a,b) = \{d\}.\]
El hecho de que \(\delta\leq d\) nos muestra que, de existir un máximo común divisor \(d\),
éste tiene que ser único.
Así que, el valor de \(d\) ha de ser el elemento más grande de \(\mathbb Z_n\) (con el orden de \(\mathbb Z\)) tal que:
\[(\mathbb Z)\hbox{mcd}(n,d)\;|\; g = (\mathbb Z)\hbox{mcd}(a,b).\]
Por lo tanto, si
\[ d = \max\{d\in\mathbb Z_n\;:\; (\mathbb Z)\hbox{mcd}(n,d)\;|\; (\mathbb Z)\hbox{mcd}(a,b)\}, \]
entonces
\[GCD_n(a,b) = \{d\}.\]
[cerrar]
