Demostración del teorema chino del resto

Question

Esta es una pregunta del curso gratuito de álgebra abstracta en línea de Harvard conferencias . Publico aquí mis soluciones para que me den su opinión. Para una explicación más completa, véase este puesto.

Este problema es de la tarea 6. Los apuntes de esta clase se encuentran en aquí .

Utilice la Proposición (2.6) para demostrar la Teorema chino del resto : Sea $m,n,a,b$ sean números enteros, y supongamos que el máximo común divisor de $m$ y $n$ es 1. Entonces hay un número entero $x$ tal que $x\equiv a \pmod m$ y $x\equiv b \pmod n$ .

Proposición (2.6): Sea $a,b$ sean números enteros, ambos no nulos, y sea $d$ sea el número entero positivo que genera el subgrupo $a\mathbb{Z}+b\mathbb{Z}$ . Entonces
a) $d$ puede escribirse de la forma $d=ar+bs$ para algunos números enteros $r$ y $s$ .
b) $d$ divide $a$ y $b$ .
c) Si un número entero $e$ divide $a$ y $b$ también divide $d$ .

Desde $x\equiv a \:(\mathrm{modulo}\:m)$ y $x\equiv b \:(\mathrm{modulo}\:n)$ , $x=a+km$ y $x=b+jn$ para algunos $k,j\in\mathbb{Z}$ . Así que si $x$ existe $a+km=b+jn$ y $km-jn=b-a$ . Dado que gcd $(m,n)=1$ 1 genera el subgrupo $m\mathbb{Z}+n\mathbb{Z}$ . Por la proposición (2.6), hay enteros $r$ y $s$ tal que $rm+sn=1$ . Multiplicar por $b-a$ obtenemos $r(b-a)m+s(b-a)n=b-a.$ Entonces $k=r(b-a)$ y $j=-s(b-a)$ . Por lo tanto, $x=a+r(b-a)m$ es una solución a ambas congruencias.

De nuevo, agradezco cualquier crítica a mi razonamiento y/o mi estilo, así como soluciones alternativas al problema.

Gracias.

Answer 1

CONSEJO $\ $ Por la proposición 2.6 deducimos $\rm\ gcd(m,n) = 1\ \Rightarrow\ m^{-1}\ $ existe $\rm\ (mod\ n)\:.\ $ Por lo tanto

TEOREMA $\:$ (CRT fácil) $\rm\ \ $ Si $\rm\ m,\:n\:$ son enteros coprimos entonces

$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray} \ \iff\ \ x\ \equiv\ a + m\ \bigg[\frac{b-a}{m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$

Prueba $\rm\ (\Leftarrow)\ \ \ mod\ m:\ x\ \equiv\ a + m\ [\:\cdots\:]\ \equiv\ a\:,\ $ y $\rm\ mod\ n\!\!:\ x\ \equiv\ a + (b-a)\ m/m\ \equiv\ b\:.$

$\rm (\Rightarrow)\ \ $ La solución es única $\rm\ (mod\ m\:n)\ $ ya que si $\rm\ x',\:x\ $ son soluciones, entonces $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ por lo tanto $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \ $ desde $\rm\ \:m,\:n\:$ coprimo $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\quad $ QED

Answer 2

Te acercas peligrosamente a la falacia de asumir la conclusión cuando empiezas una frase con "si ". $x$ existe..." En realidad, no necesitas ni utilizas las dos primeras frases de tu escrito. Una vez que tenga $r$ y $s$ puede comprobar directamente que $a+(b-a)rm$ da una solución.

Answer 3

Nota: $|m - n| \ge j \in \mathbb{Z}$ en cualquier momento solución por estados de congruentes para cualquier número entero $x$ .