[Adrii]

Buenos días,

Escribo este post porque estaba aprendiendo sobre el Teorema Chino del Resto y me he encontrado con una duda que no he podido resolver. En los apuntes que estoy leyendo, está escrito lo siguiente:

“Observación 2.21. Si los módulos no son coprimos, el sistema puede no tener solución. Por ejemplo, el sistema

\(  

x \equiv{3}\;(mod\;6) \newline
x \equiv{2}\;(mod\;4)

 \)

no tiene solución. La primera ecuación implica que \( x\equiv{1}\;(mod\;2) \), y la segunda implica que \( x \equiv{0}\;(mod\;2) \), por lo tanto no puede haber ninguna \( x \) que cumpla ambas a la vez.”


El teorema y el texto que he citado los entiendo bien, lo que no acabo de comprender es cómo deduce a partir de las ecuaciones del sistema, las dos ecuaciones de abajo (lo que he subrayado en el texto citado).

Gracias de antemano.

[Masacroso]

Si \( x\equiv 3\pmod 6 \) significa que \( x=6k+3 \) para algún \( k\in \mathbb{Z} \), por tanto

\( \displaystyle{
x\equiv 6k+3\equiv (6k+2)+1\equiv 0+1\equiv 1\pmod 2
} \)

Y la otra congruencia la resuelves igual obteniendo \( x\equiv 0\pmod 2 \). Observa que, en general, si \( n\mid m \) entonces

\( \displaystyle{
x\equiv r\pmod m\implies x\equiv r\pmod n
} \)

[Adrii]

Genial, muchas gracias. Creo que ya lo estoy entendiendo. Entonces, para un caso general, la demostración sería la siguiente?


Si \( n \mid m \), entonces \(  x\equiv r\pmod m\implies x\equiv r\pmod n  \)

Demostración.
Si \( n \mid m \) entonces \( nk=m \) para algún \( k \in \mathbb{Z} \).
Sea \(  x\equiv r\pmod m \). Entonces, esto significa que \( x = mk' + r \) para algún \( k' \in \mathbb{Z} \). Entonces:

\(  x \equiv mk' + r \equiv nkk' + r \equiv 0 + r \equiv r \;(\textrm{mod }n)  \)

\( \square \)

Por otro lado, me gustaría saber también si esto, que está muy relacionado con lo anterior, es cierto y cómo se puede demostrar:

Si \(  a \equiv b \; (\textrm{mod }m)  \) y \(  a \equiv b \; (\textrm{mod }n)  \), entonces \(  a \equiv b \; (\textrm{mod }[m,n])  \), donde \( [m,n] \) es el mínimo común múltiplo de m y n.

Gracias.

[Masacroso]

Genial, muchas gracias. Creo que ya lo estoy entendiendo. Entonces, para un caso general, la demostración sería la siguiente?


Si \( n \mid m \), entonces \(  x\equiv r\pmod m\implies x\equiv r\pmod n  \)

Demostración.
Si \( n \mid m \) entonces \( nk=m \) para algún \( k \in \mathbb{Z} \).
Sea \(  x\equiv r\pmod m \). Entonces, esto significa que \( x = mk' + r \) para algún \( k' \in \mathbb{Z} \). Entonces:

\(  x \equiv mk' + r \equiv nkk' + r \equiv 0 + r \equiv r \;(\textrm{mod }n)  \)

\( \square \)

Perfecto.

Por otro lado, me gustaría saber también si esto, que está muy relacionado con lo anterior, es cierto y cómo se puede demostrar:

Si \(  a \equiv b \; (\textrm{mod }m)  \) y \(  a \equiv b \; (\textrm{mod }n)  \), entonces \(  a \equiv b \; (\textrm{mod }[m,n])  \), donde \( [m,n] \) es el mínimo común múltiplo de m y n.

Gracias.

Para ver si eso es cierto, o no lo es, una simplificación que puedes hacer es asumir que \( a\equiv 0 \pmod y \), para \( y\in\{n,m,[n,m]\} \), ya que \( a\equiv b\pmod y\iff a-b\equiv 0\pmod y \), por tanto es suficiente con hacer la demostración para \( a-b \) en vez de \( a \).

Pero entonces, siguiendo mismas ideas de antes, la demostración de este teorema es bastante directa. Sigue los mismos pasos del teorema anterior que seguro podrás resolverlo. Igualmente te dejo la solución en un spoiler.

Spoiler

Si \( a\equiv 0\pmod n \) entonces \( a=nk_1 \) para algún \( k_1\in \mathbb{Z} \), y si también \( a\equiv 0\pmod m \) entonces \( a=mk_2 \) para algún \( k_2\in \mathbb{Z} \). Si ahora sustituyes \( n \) y \( m \) por su descomposición en factores primos observas que \( a=[n,m]k_3 \) para un \( k_3\in \mathbb{Z} \), y por tanto \( a\equiv 0\pmod{[n,m]} \).∎

[cerrar]

[Adrii]

Gracias. He intentado demostrarlo y he hecho lo siguiente (que creo que no es correcto):


Proposición. Si \(  a \equiv 0 \; (\textrm{mod }m)  \) y \(  a \equiv 0 \; (\textrm{mod }n)  \), entonces \(  a \equiv 0 \; (\textrm{mod }[m,n])  \), donde \( [m,n] \) es el mínimo común múltiplo de m y n.

Demostración. Supongamos que \(  a \equiv 0 \; (\textrm{mod }m)  \) y \(  a \equiv 0 \; (\textrm{mod }n)  \). Entonces \(  nn' = a  \) y \(  mm' = a \Longleftrightarrow nmk = a^{2}, \textrm{ donde } k=m'n'  \).

Por otro lado, partiendo del hecho de que \(  \displaystyle\frac{mn}{(m,n)} = [m,n]  \) (donde \( (m,n) \) es el máximo común divisor de m y n), deducimos que \(  [m,n] \mid mn  \) ya que \( [m,n]k' = mn \textrm{ para algún } k' \in \mathbb{Z} \) (de hecho este \( k' \) es el máximo común divisor).

Entonces, \(  a^{2} \equiv nmk \equiv [m,n]kk' \equiv 0 \; (\textrm{mod } [m,n])  \)

Sin embargo, aquí me queda que \(  a^{2} \equiv 0 \; (\textrm{mod } [m,n])  \) y no sé si esto es suficiente para poder decir que \(  a \equiv 0 \; (\textrm{mod } [m,n])  \).



Por otro lado, te agradezco que hayas dejado la demostración. Sin embargo, me cuesta un poco ver por qué si descompongo \( m \) y \( n \) en factores primos, se observa que \( a=[n,m]k_{3} \)

[Masacroso]

Por otro lado, te agradezco que hayas dejado la demostración. Sin embargo, me cuesta un poco ver por qué si descompongo \( m \) y \( n \) en factores primos, se observa que \( a=[n,m]k_{3} \)

Supón que \( \{p_k\}_{k\in\mathbb{N}} \) es una enumeración de los números primos en \( \mathbb{N} \), entonces \( n=\prod_{k\in \mathbb{N}}p_k^{n_k} \) y \( m=\prod_{k\in \mathbb{N}}p_k^{m_k} \) para determinados \( n_k,m_k\in \mathbb{N}\cup \{0\} \) donde, excepto un número finito de \( n_k \) y de \( m_k \), todos esos números son iguales a cero. Entonces \( [n,m]=\prod_{k\in \mathbb{N}}p_k^{\max\{n_k,m_k\}} \).

Ahora observa que, para cada \( k\in \mathbb{N} \), o bien \( p_k^{\max\{ n_k,m_k \}}\mid n \) o bien \( p_k^{\max\{ n_k,m_k \}}\mid m \), y por tanto \( p_k^{\max\{ n_k,m_k \}}\mid a \) en todo caso (ya que \( a \) es divisible por \( n \) y por \( m \)), de donde se sigue que \( [n,m]\mid a \) (ya que todos los factores primos de \( [n,m] \) dividen a \( a \)). Dime si ahora lo ves más claro.

Añadido: para hacer esta última afirmación en paréntesis una demostración rigurosa podemos usar el siguiente teorema:

Teorema: si \( \operatorname{MCD}(x,y)=1 \) y tanto \( x \) como \( y \) dividen a \( g \), entonces \( x\cdot y \) también divide a \( g \). Demostración: tenemos que \( g=x\cdot k \) para algún \( k\in \mathbb{N} \). Si \( y\nmid k \) entonces en particular alguno de los factores primos de \( y \), llamémosle \( p \), no divide a \( k \), y como \( y\mid x\cdot k \) entonces \( p\mid x \), pero eso contradice el que \( x \) e \( y \) sean primos entre sí, por tanto \( y\mid k \).∎

Del teorema anterior, y teniendo en cuenta que en la descomposición \( [n,m]=\prod_{k\in \mathbb{N}}p_k^{\max\{n_k,m_k\}} \) cada factor \( p_k^{\max\{ n_k,m_k \}} \) es primo relativo a cualquier otro factor \( p_j^{\max\{ n_j,m_j \}} \) con \( j\neq k \), utilizando inducción en \( N \) podemos demostrar que, para todo \( N \), \( \prod_{k=1}^N p_k^{\max\{ n_k,m_k \}} \) divide a \( a \), y como existe \( R\in \mathbb{N} \) tal que \( \prod_{k=1}^R p_k^{\max\{ n_k,m_k \}}=\prod_{k\in \mathbb{N}} p_k^{\max\{ n_k,m_k \}} \), ya habríamos demostrado con más formalidad que \( [n,m]\mid a \).

[feriva]

El teorema y el texto que he citado los entiendo bien, lo que no acabo de comprender es cómo deduce a partir de las ecuaciones del sistema, las dos ecuaciones de abajo (lo que he subrayado en el texto citado).

Gracias de antemano.

Si te fijas un poco se ve de inmediato sin hacer cuentas. x-3 y x-2 son enteros consecutivos, luego uno es par y otro es impar; sin embargo, los dos módulos son pares, por tanto, alguna de las divisiones \( \dfrac{x-3}{6} \) o \( \dfrac{x-2}{4} \) no pueden dar un entero.

En general, lo puedes ver como una suma de dos o más enteros \( \dfrac{x-r_{1}}{m_{1}}+\dfrac{x-r_{2}}{m_{2}}+... \) la cual, como tal, va a dar otro entero. Ese entero resultante será múltiplo del mcm de los módulos (como en cualquier suma de fracciones en la aritmética elemental) y ésa es la esencia del teorema chino. Cuando los módulos son coprimos, el mcm es directamente el producto de los módulos y el MCD es 1, por lo que \( MCD(m_{1}m_{2})\cdot mcm(m_{1}m_{2})=m_{1}m_{2}\Rightarrow mcm(m_{1}m_{2})=1\cdot m_{1}m_{2} \), lo que quiere decir que, cuando los módulos son coprimos, el producto de los módulos divide es común respecto de cualquier \( x-r_{i} \), donde ese producto de los módulos es el “módulo general” del sistema, podríamos decir. Por eso, cuando ocurre esto, tiene solución siempre. Y en otros casos dependerá.

O sea, mira

\( \dfrac{a}{p}+\dfrac{b}{q}+\dfrac{c}{r}=k \) (“a=x- resto”, etc.).

Entonces podemos operar asi

\( \dfrac{qr}{qr}\cdot\dfrac{a}{p}+\dfrac{pr}{pr}\cdot\dfrac{b}{q}+\dfrac{pq}{pq}\cdot\dfrac{c}{r}=k\rightarrow \)

\( qr\cdot\dfrac{a}{pqr}+pr\cdot\dfrac{b}{pqr}+pq\cdot\dfrac{c}{pqr}=k\rightarrow \)

\( qr\cdot a+pr\cdot b+pq\cdot c=(pqr)k \)

Donde “a” es múltiplo de “p” (por la propia definición de la congruencia) y así con los demás. Es decir, “pqr” tiene que ser divisor común de cada sumando de esa suma, para cada sumando, para que “k” sea entero.

Saludos.

[Adrii]

Ahora observa que, para cada \( k\in \mathbb{N} \), o bien \( p_k^{\max\{ n_k,m_k \}}\mid n \) o bien \( p_k^{\max\{ n_k,m_k \}}\mid m \), y por tanto \( p_k^{\max\{ n_k,m_k \}}\mid a \) en todo caso (ya que \( a \) es divisible por \( n \) y por \( m \)), de donde se sigue que \( [n,m]\mid a \) (ya que todos los factores primos de \( [n,m] \) dividen a \( a \)). Dime si ahora lo ves más claro.

Sí, perfecto, ahora lo he comprendido del todo. Muchas gracias!

Si te fijas un poco se ve de inmediato sin hacer cuentas. x-3 y x-2 son enteros consecutivos, luego uno es par y otro es impar; sin embargo, los dos módulos son pares, por tanto, alguna de las divisiones \( \dfrac{x-3}{6} \) o \( \dfrac{x-2}{4} \) no pueden dar un entero.

En general, lo puedes ver como una suma de dos o más enteros \( \dfrac{x-r_{1}}{m_{1}}+\dfrac{x-r_{2}}{m_{2}}+... \) la cual, como tal, va a dar otro entero. Ese entero resultante será múltiplo del mcm de los módulos (como en cualquier suma de fracciones en la aritmética elemental) y ésa es la esencia del teorema chino. Cuando los módulos son coprimos, el mcm es directamente el producto de los módulos y el MCD es 1, por lo que \( MCD(m_{1}m_{2})\cdot mcm(m_{1}m_{2})=m_{1}m_{2}\Rightarrow mcm(m_{1}m_{2})=1\cdot m_{1}m_{2} \), lo que quiere decir que, cuando los módulos son coprimos, el producto de los módulos divide es común respecto de cualquier \( x-r_{i} \), donde ese producto de los módulos es el “módulo general” del sistema, podríamos decir. Por eso, cuando ocurre esto, tiene solución siempre. Y en otros casos dependerá.

O sea, mira

\( \dfrac{a}{p}+\dfrac{b}{q}+\dfrac{c}{r}=k \) (“a=x- resto”, etc.).

Entonces podemos operar asi

\( \dfrac{qr}{qr}\cdot\dfrac{a}{p}+\dfrac{pr}{pr}\cdot\dfrac{b}{q}+\dfrac{pq}{pq}\cdot\dfrac{c}{r}=k\rightarrow \)

\( qr\cdot\dfrac{a}{pqr}+pr\cdot\dfrac{b}{pqr}+pq\cdot\dfrac{c}{pqr}=k\rightarrow \)

\( qr\cdot a+pr\cdot b+pq\cdot c=(pqr)k \)

Donde “a” es múltiplo de “p” (por la propia definición de la congruencia) y así con los demás. Es decir, “pqr” tiene que ser divisor común de cada sumando de esa suma, para cada sumando, para que “k” sea entero.

Saludos.

Gracias por esta otra forma de plantear el problema, ahora lo entiendo todo mejor.

[feriva]

Gracias por esta otra forma de plantear el problema, ahora lo entiendo todo mejor.

De nada, me alegro de que te haya servido.

Por señalar algo más. Yo no sé si esto se dice en la explicación formal del teorema chino (porque soy aficionado, no lo he estudiado académicamente) pero fíjate en que si tienes dos grupos (o más) de enteros módulo lo que sea, \( \mathbb{Z}_{n} \) y \( \mathbb{Z}_{m} \), esta representación del resto 1, \( \dfrac{n}{n}\equiv1 \), o ésta \( \dfrac{nm}{nm}\equiv1 \) o esta \( \dfrac{pqr}{pqr}\equiv1 \)... es válida para cualquiera de los grupos, porque siempre representa el resto tal cual, al neutro, no a una unidad cualquiera; mientras que aquí \( x\equiv1\,(mod\,n) \) vale cualquier representante, la notación no caracteriza al neutro por sí sola (al neutro de todos los enteros, quiero decir). 

Y mirarlo así me parece un detalle que puede ayudar a ver mejor el el porqué del asunto.

Saludos.