12 Sistemas de ecuaciones lineales modulo n

Vamos a estudiar sistemas de varias ecuaciones modulares con una sola incognita xx 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.

Theorem 12.1 (chino de los restos).

Sean n1,n2,…,nkn_{1},n_{2},\ldots,n_{k} ∈ℤ\in\mathbb{Z} con cada ni≥2n_{i}\geq 2 y relativamente primos entre si dos a dos, es decir, si i≠ji\neq j entonces m.c.d.(ni,nj)=1\mathrm{m.c.d.}(n_{i},n_{j})=1.

Sean a1,a2,…,ak∈ℤa_{1},a_{2},\ldots,a_{k}\in\mathbb{Z} y consideramos el sistema de ecuaciones

{x≡a1⁢(mod ⁢n1)x≡a2⁢(mod ⁢n2)⋮x≡ak⁢(mod ⁢nk)\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 xx es la incognita que toma valores en ℤ\mathbb{Z}.

Entonces el sistema tiene solucion.

Es mas, si definimos, para cada jj,

  • •
    ​

    Q≔∏i=1nniQ\coloneqq\prod\limits_{i=1}^{n}n_{i}

  • •
    ​

    Qj≔Q/njQ_{j}\coloneqq Q/n_{j}

  • •
    ​

    yjy_{j} como una solucion de la ecuacion Qi⁢y≡i⁢(mod ⁢nj)Q_{i}y\equiv i(\text{mod }n_{j})

entonces el siguiente valor es solucion del sistema:

x0=y1⁢Q1⁢a1+y2⁢Q2⁢a2+⋯+yk⁢Qk⁢akx_{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:

x=x0+t⁢Q,t∈ℤx=x_{0}+tQ,\quad t\in\mathbb{Z}

(por lo que la solucion es unica modulo QQ).

Proof 12.2.

Vamos a empezar viendo que las ecuaciones

Qj⋅y≡1⁢ mod ⁢njQ_{j}\cdot y\equiv 1\text{ mod }n_{j}

tienen solucion.

Como Qj=∏i=1kninjQ_{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 m.c.d.(Qj,nj)=1⇒Qj⋅y≡1⁢ mod ⁢nj⁢ tiene solucion\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 x0=∑i=1kyi⁢Qi⁢aix_{0}=\sum_{i=1}^{k}y_{i}Q_{i}a_{i} es solucion del sistema.

Voy a calcular x0x_{0} mod njn_{j}.

Si i≠j⇒n⁢j|Q2i\neq j\Rightarrow nj|Q_{2}. Todos los sumandos yi⁢Qi⁢aiy_{i}Q_{i}a_{i} son 0 mod nn cuando i≠ji\neq j.

Luego x0≡yj⁢Qj⁢aj≡1⁢aj≡aj⁢ mod ⁢njx_{0}\equiv y_{j}Q_{j}a_{j}\equiv 1a_{j}\equiv a_{j}\text{ mod }n_{j}

Luego x0x_{0} es solucion de la ecuacion x≡aj⁢ mod ⁢nj⁢∀j⇒x0x\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

x=x0+t⋅Q,t∈ℤx=x_{0}+t\cdot Q,\quad t\in\mathbb{Z}

donde x0x_{0} es cualquier solucion particular.

Supongamos que x=x0+t⋅Qx=x_{0}+t\cdot Q es uno de esos valores. ¿Cuanto vale modulo njn_{j}?

x=x0+t⋅Q≡x0≡aj⁢ mod ⁢njx=x_{0}+t\cdot Q\equiv x_{0}\equiv a_{j}\text{ mod }n_{j}

x0≡ajx_{0}\equiv a_{j} porque x0x_{0} es solucion.

Luego xx es solucion del sistema.

Veamos que no hay mas soluciones que esos valores.

Sean x0x_{0} una solucion particular y x′x^{\prime} otra solucion cualquiera ⇒x0≡a1⁢ mod ⁢n1\Rightarrow x_{0}\equiv a_{1}\text{ mod }n_{1} y x′≡a1⁢ mod ⁢n1⇒x≡x′⁢ mod ⁢n1⇒∃k1∈ℤ∣x0−x′=k1⋅n1x^{\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 x0≡a2⁢ mod ⁢n2x_{0}\equiv a_{2}\text{ mod }n_{2}, x′≡a2⁢ mod ⁢n2x^{\prime}\equiv a_{2}\text{ mod }n_{2}.

Luego x0≡x′⁢ mod ⁢n2⇒∃k2∈ℤ∣x0−x′=k2⋅n2⇒k1⁢n1=k2⋅n2x_{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 m.c.d.(n1,n2)=1\mathrm{m.c.d.}(n_{1},n_{2})=1 y n1|k2⁢n2⇒n1|k2⇒k2=n1⋅k⇒x0−x′=n1⋅k⁢n2n_{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: x0≡x′≡a3⁢ mod ⁢n3⇒x0−x=k3⋅n3x_{0}\equiv x^{\prime}\equiv a_{3}\text{ mod }n_{3}\Rightarrow x_{0}-x=k_{3}% \cdot n_{3}.

Luego k2⋅n2=k3⋅n3k_{2}\cdot n_{2}=k_{3}\cdot n_{3}

Repitiendo el argumento para cada ecuacion, llego a que x0−x′=t⋅n1⋅n2⁢⋯⁢nk⇒x′=x0+(−t)⁢n1⋅n2⁢⋯⁢nk⇒x′=x0+s⋅Qx_{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.

Remark 12.3.

Que pasa si no podemos aplicar el teorema chino de los restos?

Podemos ir resolviendo el sistema por sustitucion: hallar la solucion general en ℤ\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.