12 Sistemas de ecuaciones lineales modulo n

Vamos a estudiar sistemas de varias ecuaciones modulares con una sola incognita $\displaystyle x$ del tipo:

Una herramienta teorica importante por si misma y que, ademas, nos permite resolver algunos de estos sistemas es el teorema chino de los restos.

Teorema 12.1 (chino de los restos).

Sean $\displaystyle n_{1},n_{2},\ldots,n_{k}$ $\displaystyle\in\mathbb{Z}$ con cada $\displaystyle n_{i}\geq 2$ y relativamente primos entre si dos a dos, es decir, si $\displaystyle i\neq j$ entonces $\displaystyle\mathrm{m.c.d.}(n_{i},n_{j})=1$ . Sean $\displaystyle a_{1},a_{2},\ldots,a_{k}\in\mathbb{Z}$ y consideramos el sistema de ecuaciones

\displaystyle\begin{dcases}x\equiv a_{1}(\text{mod }n_{1})\\ x\equiv a_{2}(\text{mod }n_{2})\\ \vdots\\ x\equiv a_{k}(\text{mod }n_{k})\\ \end{dcases}

donde $\displaystyle x$ es la incognita que toma valores en $\displaystyle\mathbb{Z}$ . Entonces el sistema tiene solucion. Es mas, si definimos, para cada $\displaystyle j$ ,

$\displaystyle Q\coloneqq\prod\limits_{i=1}^{n}n_{i}$
$\displaystyle Q_{j}\coloneqq Q/n_{j}$
$\displaystyle y_{j}$ como una solucion de la ecuacion $\displaystyle Q_{i}y\equiv i(\text{mod }n_{j})$

entonces el siguiente valor es solucion del sistema:

\displaystyle x_{0}=y_{1}Q_{1}a_{1}+y_{2}Q_{2}a_{2}+\cdots+y_{k}Q_{k}a_{k}

Y el conjunto de todas las soluciones del sistema viene dado por:

\displaystyle x=x_{0}+tQ,\quad t\in\mathbb{Z}

(por lo que la solucion es unica modulo $\displaystyle Q$ ).

Demostración.

Vamos a empezar viendo que las ecuaciones

\displaystyle Q_{j}\cdot y\equiv 1\text{ mod }n_{j}

tienen solucion. Como $\displaystyle Q_{j}=\frac{\prod\limits_{i=1}^{k}n_{i}}{n_{j}}$ , por la hipotesis de que los modulos son relativamente primos dos a dos, tenemos que $\displaystyle\mathrm{m.c.d.}(Q_{j},n_{j})=1\Rightarrow Q_{j}\cdot y\equiv 1% \text{ mod }n_{j}\text{ tiene solucion}$ . Vamos a ver que $\displaystyle x_{0}=\sum_{i=1}^{k}y_{i}Q_{i}a_{i}$ es solucion del sistema. Voy a calcular $\displaystyle x_{0}$ mod $\displaystyle n_{j}$ . Si $\displaystyle i\neq j\Rightarrow nj|Q_{2}$ . Todos los sumandos $\displaystyle y_{i}Q_{i}a_{i}$ son 0 mod $\displaystyle n$ cuando $\displaystyle i\neq j$ . Luego $\displaystyle x_{0}\equiv y_{j}Q_{j}a_{j}\equiv 1a_{j}\equiv a_{j}\text{ mod }% n_{j}$ Luego $\displaystyle x_{0}$ es solucion de la ecuacion $\displaystyle x\equiv a_{j}\text{ mod }n_{j}\forall j\Rightarrow x_{0}$ es solucion del sistema original. Falta ver que el conjunto de todas las soluciones es

\displaystyle x=x_{0}+t\cdot Q,\quad t\in\mathbb{Z}

donde $\displaystyle x_{0}$ es cualquier solucion particular. Supongamos que $\displaystyle x=x_{0}+t\cdot Q$ es uno de esos valores. ¿Cuanto vale modulo $\displaystyle n_{j}$ ?

\displaystyle x=x_{0}+t\cdot Q\equiv x_{0}\equiv a_{j}\text{ mod }n_{j}

$\displaystyle x_{0}\equiv a_{j}$ porque $\displaystyle x_{0}$ es solucion. Luego $\displaystyle x$ es solucion del sistema. Veamos que no hay mas soluciones que esos valores. Sean $\displaystyle x_{0}$ una solucion particular y $\displaystyle x^{\prime}$ otra solucion cualquiera $\displaystyle\Rightarrow x_{0}\equiv a_{1}\text{ mod }n_{1}$ y $\displaystyle x^{\prime}\equiv a_{1}\text{ mod }n_{1}\Rightarrow x\equiv x^{% \prime}\text{ mod }n_{1}\Rightarrow\exists k_{1}\in\mathbb{Z}\mid x_{0}-x^{% \prime}=k_{1}\cdot n_{1}$ . Tambien $\displaystyle x_{0}\equiv a_{2}\text{ mod }n_{2}$ , $\displaystyle x^{\prime}\equiv a_{2}\text{ mod }n_{2}$ . Luego $\displaystyle x_{0}\equiv x^{\prime}\text{ mod }n_{2}\Rightarrow\exists k_{2}% \in\mathbb{Z}\mid x_{0}-x^{\prime}=k_{2}\cdot n_{2}\Rightarrow k_{1}n_{1}=k_{2% }\cdot n_{2}$ . Por el lema de Euclides, como $\displaystyle\mathrm{m.c.d.}(n_{1},n_{2})=1$ y $\displaystyle n_{1}|k_{2}n_{2}\Rightarrow n_{1}|k_{2}\Rightarrow k_{2}=n_{1}% \cdot k\Rightarrow x_{0}-x^{\prime}=n_{1}\cdot kn_{2}$ Sigo con la tercera ecuacion: $\displaystyle x_{0}\equiv x^{\prime}\equiv a_{3}\text{ mod }n_{3}\Rightarrow x% _{0}-x=k_{3}\cdot n_{3}$ . Luego $\displaystyle k_{2}\cdot n_{2}=k_{3}\cdot n_{3}$ Repitiendo el argumento para cada ecuacion, llego a que $\displaystyle x_{0}-x^{\prime}=t\cdot n_{1}\cdot n_{2}\cdots n_{k}\Rightarrow x% ^{\prime}=x_{0}+(-t)n_{1}\cdot n_{2}\cdots n_{k}\Rightarrow x^{\prime}=x_{0}+s\cdot Q$ . Por tanto, no hay mas soluciones que las del enunciado. ∎

Observación.

Que pasa si no podemos aplicar el teorema chino de los restos? Podemos ir resolviendo el sistema por sustitucion: hallar la solucion general en $\displaystyle\mathbb{Z}$ de la primera ecuacion y sustituir en la segunda para obtener una solucion comun de las dos. Sustituir esa solucion en la tercera para hallar una solucion comun de las tres. Y asi sucesivamente hasta encontrar la solucion general comun a todas las ecuaciones. En el caso general no esta garantizada la existencia de solucion al sistema, se notara si en alguno de los pasos se encuentra una ecuacion que no tiene solucion. Este metodo es general y tambien sirve para el caso en el que si se puede aplicar el teorema chino de los restos.