Archivo de la etiqueta: ecuaciones

Álgebra Lineal I: Problemas de ortogonalidad, ecuaciones e hiperplanos

Por Ayax Calderón

11 respuestas

Introducción

En esta entrada ejercitaremos los conceptos introducidos recientemente. Abordamos los temas de espacio ortogonal e hiperplanos. Para ello, resolveremos problemas de ortogonalidad relacionados con encontrar una base para el espacio ortogonal y de escribir subespacios en términos de ecuaciones e intersecciones de hiperplanos.

Problemas resueltos de espacio ortogonal

Problema 1. Sea $S=\{x^3+x, x^2+x ,-x^3+x^2+1\} \subseteq \mathbb{R}_3[x]$.
Describe $S^{\bot}$ dando una base de este espacio.

Solución. Una forma lineal $l$ sobre $\mathbb{R}_3[x]$ es de la forma

$l(a_0 + a_1x+a_2x^2+a_3x^3)=aa_0+ba_1+ca_2+da_3$

para algunos $a, b,c,d\in \mathbb{R}$, pues basta decidir quiénes son $a=l(1)$, $b=l(x)$, $c=l(x^2)$ y $d=l(x^3)$.

La condición $l\in S^{\bot}$ es equivalente a

$l(x^3+x)=l(x^2+x)=l(-x^3+x^2+1)=0.$

Esto es
\begin{align*}
l(x^3+x)&=b+d=0\\
l(x^2+x)&=b+c=0\\
l(-x^3+x^2+1)&=a+c-d=0.
\end{align*}

La matriz asociada al sistema es

$A=\begin{pmatrix}
0 & 1 & 0 & 1\\
0 & 1 & 1 & 0\\
1 & 0 & 1 & -1\end{pmatrix}$

y su forma escalonada reducida es

$A_{red}=\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & -1\end{pmatrix}.$

Así, $d$ es variable libre y \begin{align*} a&=0\\ b&=-d\\ c&=d.\end{align*}

De aquí, el conjunto de soluciones del sistema es
$$\{(0,-u,u,u) : u\in \mathbb{R}\}.$$

Las correspondientes formas lineales son $$l_u(a_0+a_1x+a_2x^2+a_3x^3)=u(-a_1+a_2+a_3).$$

Este es un subespacio de dimensión $1$, así que para determinar una base para $S^{\bot}$, basta con elegir una de estas formas lineales con $u\neq 0$, por ejemplo, para $u=1$ tenemos
$$l_1(a_o+a_1x+a_2x^2+a_3x^3)=-a_1+a_2+a_3.$$

$\triangle$

Problema 2. Sea $V$ un espacio vectorial sobre un campo $F$, sea $V^\ast$ su espacio dual y tomemos subconjuntos $S, S_1, S_2\subseteq V^\ast$ tales que $S_1\subseteq S_2$. Prueba lo siguiente.

  1. $S_2^{\bot}\subseteq S_1^{\bot}$.
  2. $S\subseteq (S^{\bot})^{\bot}$.

Solución.

  1. Sea $l\in S_2^{\bot}$. Por definición $l(s)=0$ para toda $s\in S_2$.
    Luego, si $s\in S_1$, entonces $s\in S_2$ y así $l(s)=0$. Por consiguiente $l\in S_1^{\bot}$. Concluimos $S_2^{\bot}\subseteq S_1^{\bot}$.
  2. Sea $s\in S$. Para cualquier $l\in S^{\bot}$ se cumple que $l(s)=0$ y así $s\in (S^{\bot})^{\bot}$

$\square$

Observación. El problema anterior también es cierto si suponemos que $S, S_1, S_2\subseteq V$ tales que $S_1\subseteq S_2$ y la prueba es idéntica a la anterior.

Observación. Por muy tentador que sea pensar que la igualdad se da en el inciso 2 del problema anterior, esto es totalmente falso: $(S^{\bot})^{\bot}$ es un subespacio de $V$ (o de $V^\ast$), mientras que no hay razón para que $S$ lo sea, pues este es solamente un subconjunto arbitrario de $V$ (o $V^\ast$). Como vimos en una entrada anterior, la igualdad se da si $S$ es un subespacio de $V$ (o de $V^\ast$) cuando $V$ es un subespacio de dimensión finita.

Problemas resueltos de ecuaciones lineales y de hiperplanos

Veamos ahora problemas de ortogonalidad relacionados con encontrar expresiones para un subespacio en términos de ecuaciones lineales y de hiperplanos.

Problema 1. Sea $W$ el subespacio de $\mathbb{R}^4$ generado por los vectores

$v_1=(1,1,0,1)$
$v_2=(1,2,2,1).$

Encuentra ecuaciones lineales en $\mathbb{R}^4$ cuyo conjunto solución sea $W$.

Solución. Necesitamos encontrar una base para $W^{\bot}$.
Recordemos que $W^{\bot}$ consiste de todas las formas lineales

$l(x,y,z,t)=ax+by+cz+dt$

tales que $l(v_1)=l(v_2)=0$, es decir
\begin{align*}
a+b+d&=0\\
a+2b+2c+d&=0.
\end{align*}

La matriz asociada al sistema anterior es

$A=\begin{pmatrix}
1 & 1 & 0 & 1\\
1 & 2 & 2 & 1\end{pmatrix}$

y por medio de reducción gaussiana llegamos a que su forma reducida escalonada es

$A_{red}=\begin{pmatrix}
1 & 0 & -2 & 1\\
0 & 1 & 2 & 0\end{pmatrix}.$

De aquí, $c$ y $d$ son variables libres y $a$ y $b$ son variables pivote determinadas por
\begin{align*}a&=2c-d\\b&=-2c.\end{align*}

Por lo tanto,
\begin{align*}
l(x,y,z,t)&=(2c-d)x-2cy+cz+dt\\
&=c(2x-2y+z)+d(-x+t).
\end{align*}

Así, deducimos que una base para $W^{\bot}$ está dada por

$l_1(x,y,z,t)=2x-2y+z$ y $l_2(x,y,z,t)=-x+t$

y por consiguiente $W=\{v\in \mathbb{R}^4 : l_1(v)=l_2(v)=0\}$, de donde $$l_1(v)=0, l_2(v)=0$$ son ecuaciones cuyo conjunto solución es $W$.

$\triangle$

Problema 2. Considera el espacio vectorial $V=\mathbb{R}_3[x]$. Escribe el subespacio vectorial generado por $p(x)=1-2x^2$ y $q(x)=x+x^2-x^3$ como la intersección de dos hiperplanos linealmente independientes en $V$.

Solución. Sea $\mathcal{B}=\{1,x,x^2,x^3\}=\{e_1,e_2,e_3,e_4\}$ la base canónica de $V$.

Entonces

\begin{align*}
p(x)&=e_1-2e_3\\
q(x)&=e_2+e_3-e_4.
\end{align*}

Escribir $W=\text{span}(p(x),q(x))$ como intersección de dos hiperplanos es equivalente a encontrar dos ecuaciones que definan a $W$, digamos $l_1(v)=l_2(v)=0$ pues entonces $$W=H_1 \cap H_2,$$ donde $H_1=\ker(l_1)$ y $H_2=\ker(l_2)$.

Así que sólo necesitamos encontrar una base $l_1,l_2$ de $W^{\bot}$.

Recordemos que una forma lineal en $\mathbb{R}_3[x]$ es de la forma $$l_1(x_1e_1+x_2e_2+x_3e_3+x_4e_4)=ax_1+bx_2+cx_3+dx_4$$

para algunos $a,b,c,d \in \mathbb{R}$.

Esta forma lineal $l$ pertenece a $W^{\bot}$ si y sólo si $$l(p(x))=l(q(x))=0,$$ o bien

\begin{align*}
a-2c&=0\\
b+c-d&=0.
\end{align*}

Podemos fijar $c$ y $d$ libremente y despejar $a$ y $b$ como sigue:

\begin{align*}a&=2c\\b&=-c+d.\end{align*}

Por consiguiente

\begin{align*}
l(x_1e_1&+x_2e_2+x_3e_3+x_4e_4)\\
&=2cx_1+(-c+d)x_2+cx_3+dx_4\\
&=c2x_1-x_2+x_3)+d(x_2+x_4).
\end{align*}

Así deducimos que una base $l_1,l_2$ de $W^{\bot}$ está dada por

\begin{align*}
l_1(x_1e_1+x_2e_2+x_3e_3+x_4e_4)&=2x_1-x_2+x_3\\
l_2(x_1e_1+x_2e_2+x_3e_3+x_4e_4)&=x_2+x_4.
\end{align*}

y así $W=H_1\cap H_2$, donde

\begin{align*}
H_1&=\ker(l_1)=\{a+bx+cx^2+dx^3\in V : 2a-b+c=0\}\\
H_2&=\ker(l_2)=\{a+bx+cx^2+dx^3\in V : b+d=0\}.
\end{align*}


$\triangle$

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104721 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM»

Seminario de Resolución de Problemas: El teorema del valor intermedio

Por Fabian Ferrari

Deja un comentario

Introducción

El teorema del valor intermedio nos dice que si $f: [a, b] \to \mathbb{R}$ es una función continua, entonces para todo $y$ entre $f(a)$ y $f(b)$, existe un número $c \in [a, b]$ tal que $f(c)=y$. La forma de pensar este teorema es que «las funciones continuas no se pueden saltar valores que quedan entre dos valores que ya tomaron», o bien «las funciones continuas no dan brincos en su imagen».

Veamos algunos problemas que se resuelven usando este teorema

Una aplicación directa del teorema del valor intermedio

Problema 1. Muestra que la ecuación $2x^3+7x^2-27x=-18$ tiene una solución en el intervalo $[-7,-5]$.

Sugerencia pre-solución. Formula un problema equivalente definiendo una función continua $f$ para la cual si $f(x)=0$, entonces $x$ es solución a la ecuación.

Solución. La ecuación la podemos ver como $2x^3+7x^2-27x+18=0$. Consideremos la función $$f(x)=2x^3+7x^2-27x+18.$$ Como $f(x)$ es una función polinomial, sabemos que es continua en $\mathbb{R}$, así que es continua en el intervalo $[-7,-5]$. Lo que queremos ver es que existe un $c$ entre $-7$ y $-5$, tal que $f(c)=0$. Para esto, tenemos que evaluar la función en $-7$ y en $-5$.

Tenemos que:

$f(-7)=-136$ y $f(-5)=78$.

Tenemos que $0$ está entre $-136$ y $78$. Así, por el teorema del valor intermedio, debe de existir un número $c$ entre $-7$ y $-5$ de tal forma que $f(c)=0$. Por lo tanto $2x^3+7x^2-27x=-18$ tiene una solución entre $-5$ y $-7$.

$\square$

Notemos que no se encontró el valor de la raíz de la ecuación, sin embargo mostramos la existencia de esta. Esta es una de las características del teorema del valor intermedio: exhibir la existencia de algo sin necesidad de encontrarlo explícitamente.

Definir una buena función

En ocasiones podemos definir dos funciones para un problema y hacerlas interactuar para obtener una sola función continua que nos permite resolver un problema.

Problema 2. Un montañista empezó a escalar una montaña el sábado a las 8:00 hrs y llegó a la cima a las 18:00 hrs del mismo día. Decidió pasar la noche en la cima de la montaña. El día domingo empezó a descender a las 8:00 hrs y llegó al punto de partida a las 18:00 hrs. Prueba que hubo una hora en la que en ambos días estuvo a la misma altura de la montaña.

Sugerencia pre-solución. Plantea el problema usando dos funciones continuas que denoten la altura conforme pasa el tiempo en ambos días. Tienes mucha flexibilidad, así que usa notación efectiva para simplificar los cálculos.

Solución. Veamos que para este problema, podemos establecer dos funciones continuas para describir el cambio de altura con respecto al tiempo en horas, una para el ascenso y otra para el descenso del montañista en ambos días.

Sean $h_1(t)$, y $h_2(t)$ las funciones que representan el ascenso y el descenso del montañista respectivamente. En otras palabras, $h_1(t)$ y $h_2(t)$ denotan la altura en la que está el montañista tras $t$ horas después de haber comenzado su ascenso y descenso, respectivamente. Como amabas funciones son continuas en el intervalo de tiempo $[0, 10]$ (esto es porque tardó $10$ horas para ascender y $10$ horas para descender), tenemos que la función $g(t)=h_2(t)-h_1(t)$ tiene que ser continua en $[0, 10]$ también.

Ahora bien, sea $M$ la altura en la cima de la montaña. Tenemos lo siguiente:

$h_1(0)=0$, $h_1(10)=M$ y $h_2(0)=M$, $h_2(10)=0$.

Así, $g(0)=M$ y $g(10)=-M$. A su vez, $0$ está entre $-M$ y $M$, por lo que aplicando el teorema del valor intermedio, debe de existir un $t_0$ en el intervalo $[0, 10]$ tal que $g(t_0)=0$.

Y como

$g(t)=h_2(t)-h_1(t)$,

entonces

$g(t_0)=h_2(t_0)-h_1(t_0)$

$0=h_2(t_0)-h_1(t_0)$

$h_1(t_0)=h_2(t_0).$

Con esto podemos concluir que en el tiempo $t_0$ el día domingo estuvo a la misma altura que el día sábado al tiempo $t_0$.

$\square$

Definir un buen intervalo

En algunas ocasiones no es directo qué valores tenemos que usar como los extremos del intervalo al que aplicaremos el teorema del valor intermedio. Un ingrediente adicional que se necesita en el siguiente problema es elegir de manera correcta el extremo derecho.

Problema 3. Prueba que si $n$ es un entero positivo y $x_0 > 0$, entonces existe un único número positivo $x$ tal que $x^n=x_0$.

Sugerencia pre-solución. Necesitarás modificar el problema un poco. Se quiere encontrar una solución a $x^n=x_0$. Limítate a encontrarla en el intervalo $[0,c]$ para una buena elección de $c$.

Solución. Sea $c$ un número mayor que $1$ de tal forma que $0<x_0<c$. Si consideramos la función $f(x)=x^n$, tenemos que dicha función es continua en el intervalo $[0, c]$, y tenemos que

$f(0)=0$ y $f(c)=c^n.$

Como $$0<x_0<c<c^n,$$ tenemos que $x_0$ está en el intervalo $(0,c)$, y por el teorema del valor intermedio, tenemos que existe $x$ en el intervalo $(0,c)$ tal que $f(x)=x_0$, que usando la definición de $f$ quiere decir que $$x^n=x_0.$$

No puede existir otro además de $x_0$ ya que la función $f(x)=x^n$ es creciente en el intervalo $[0,c]$.

$\square$

Más ejemplos

Puedes encontrar más problemas que se pueden resolver usando el teorema del valor intermedio en el libro Problem Solving Strategies de Loren Larson, en la Sección 6.2.

Álgebra Superior II: Ecuaciones diofantinas

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores platicamos de congruencias y teoremas que nos sirven para trabajar con aritmética modular. Así mismo, aprendimos a resolver ecuaciones lineales y sistemas de ecuaciones lineales en congruencias en una variable.

Regresemos a $\mathbb{Z}$. Se usa el término ecuación diofantina para referirse a una ecuación en la cual las variables deben tomar soluciones enteras. Existe una gran variedad de formas que puede tomar una ecuación diofantina. «Resolver una ecuación diofantina» se refiere a encontrar, con demostración, una descripción del conjunto de todas sus soluciones en «términos sencillos».

Ejemplo 1. Encuentra todas las soluciones enteras $x$ a la ecuación $13x=91$.

Ejemplo 2. Encuentra todas las soluciones enteras $x,y$ a la ecuación $7x+5y=3$.

Los ejemplos $1$ y $2$ son ecuaciones diofantinas lineales en una y dos variables respectivamente. El objetivo de esta entrada es explicar cómo resolver estas ecuaciones. Continuamos la discusión de más ejemplos para abrir el panorama del tipo de problemas que aparecen en el área, y de las técnicas que se pueden usar.

Ejemplo 3. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^2+y^2=z^2$.

Al Ejemplo 3 se le conoce como la ecuación pitagórica. Esa es posible resolverla con todo lo que hemos visto hasta ahora, pero no es tan sencillo. Requiere de un análisis cuidadoso de casos.

Ejemplo 4. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $x^y=y^x$.

El Ejemplo $4$ es curioso. Si consideramos a la función real $f(x)=x^{\frac{1}{x}}$, el problema pide encontrar a aquellas parejas de enteros $x$ y $y$ tales que $f(x)=f(y)$. Una forma de resolver la ecuación es utilizando herramientas de cálculo diferencial en $f(x)$ para mostrar que para $x>5$ la función ya es estrictamente creciente. Esto reduce el análisis de casos de enteros que tenemos que intentar, y muestra que $(2,4)$, $(4,2)$ y $(n,n)$ son las únicas parejas de enteros válidas. La moraleja de este ejemplo es que a veces se tienen que usar herramientas de otras áreas de las matemáticas para resolver una ecuación, aunque esta sólo requiera de soluciones enteras.

Ejemplo 5. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^3+y^3=z^3$.

El Ejemplo $5$, o bien cualquier ecuación del estilo $x^n+y^n=z^n$ se le llama una ecuación de tipo Fermat, pues Pierre Fermat conjeturó que no existen soluciones para cuando $n\geq 3$ y $x,y,z$ son todos distintos de cero. Esta conjetura fue demostrada en $1995$ por Andrew Wiles. Una demostración de esta conjetura queda muy lejos de la teoría que hemos desarrollado hasta ahora, pero vale la pena decir que esta ecuación motivó fuertemente el desarrollo de varias herramientas de teoría de números, sobre unas llamadas curvas elípticas.

Ejemplo 6. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $|2^x-3^y|=1$.

El Ejemplo $6$ se puede resolver también con herramientas que ya hemos visto en el curso, pero requiere de un análisis detallado. Este problema pide, en otras palabras, determinar cuándo «una potencia de $3$ está junto a una potencia de $2$». Un ejemplo de esto son $2^3=8$ y $3^2=9$. Otra pregunta clásica del área es la conjetura de Catalán, la cual afirma que estas son las únicas dos potencias no triviales que son consecutivas. Fue demostrada en $2002$ por Mihăilescu. Las técnicas también están muy lejos del alcance de este curso. Se usan técnicas en campos ciclotómicos y módulos de Galois.

En realidad, uno podría tomar cualquier ecuación en reales y hacerse la pregunta de si existirán soluciones en enteros y, de ser así, determinar cuántas o cuáles son. Ha existido (y existe) mucha investigación en el área. El interés de una ecuación diofantina en particular está relacionado con su aplicación a otros problemas y con la teoría que ayuda a desarrollar.

Ecuaciones diofantinas lineales

La ecuación diofantina del Ejemplo 1 se puede preguntar en general. Dados enteros $a$ y $b$, ¿cuáles son las soluciones enteras $x$ a la ecuación $ax=b$?

  • Si $a=0$, la ecuación tiene solución si y sólo si $b=0$, y en este caso, cualquier valor entero de $x$ es solución.
  • Si $a\neq 0$, esta ecuación tiene solución en enteros si y sólo si $a$ divide a $b$, y en este caso $x=b/a$ es la única solución entera.

Estudiemos ahora la generalización del Ejemplo 2.

Problema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Determina todas las soluciones enteras a la ecuación $$ax+by=c.$$

Primero, determinemos condiciones necesarias y suficientes en $a$, $b$ y $c$ para que la ecuación tenga soluciones enteras $x$ y $y$. Lo que nos está pidiendo la ecuación es que escribamos a $c$ como combinación lineal entera de $a$ y $b$. Recordemos que $$a\mathbb{Z}+b\mathbb{Z} = \text{MCD}(a,b) \mathbb{Z},$$ de modo que la ecuación tiene solución si y sólo si $\text{MCD}(a,b)$ divide a $c$. ¿Cuáles son todas las soluciones? Esto lo determinaremos mediante las siguientes proposiciones.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero divisible entre $M:=\text{MCD}(a,b)$. Sean $a’=a/M$, $b’=b/M$, $c’=c/M$. Las soluciones enteras a la ecuación $ax+by=c$ son las mismas que para la ecuación $a’x+b’y=c’$.

Demostración. Se sigue de manera directa usando que $M\neq 0$, ya que de la original podemos pasar a la nueva dividiendo entre $M$, y de la nueva a la anterior multiplicando por $M$.

$\square$

Ejemplo 1. $x=2$ y $y=7$ son soluciones a la ecuación $6x-4y=-16$, y también son soluciones a la ecuación $3x-2y=-8$.

$\triangle$

Al dividir ambos lados de la ecuación entre el máximo común divisor de $a$ y $b$ obtenemos una ecuación en la que los coeficientes de las variables ahora son primos relativos. Este fenómeno ya lo habíamos visto cuando hablamos de ecuaciones en congruencias. Estudiemos este tipo de ecuaciones en enteros. Comenzaremos con unas un poco más sencillas: aquellas en las que $c=0$. A estas les llamamos ecuaciones homogéneas.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Las soluciones de la ecuación diofantina $ax+by=0$ son exactamente de la forma $x=-kb$, $y=ka$ para $k$ en los enteros.

Demostración. De la ecuación obtenemos $-ax=by$, por lo que $a$ divide a $by$. Como $a$ y $b$ son primos relativos, tenemos que $a$ divide a $y$. Así, existe un $k$ entero tal que $y=ka$. Entonces, $-ax=bka$. Como $a\neq 0$, podemos cancelar y despejar $x=-kb$.

En efecto, todas estas parejas son soluciones pues $a(-kb)+b(ka)=0$.

$\square$

Ejemplo 2. Determina todas las soluciones a la ecuación diofantina $9x+5y=0$.

Solución. Tenemos que $9$ y $5$ son primos relativos y que la ecuación es homogénea. Por el resultado anterior, las soluciones son de la forma $x=-5k$ y $y=9k$.

$\triangle$

Ejemplo 3. Determina todas las soluciones a la ecuación diofrantina $9x-6y=0$.

Solución. Aquí hay que tener cuidado. Si bien la ecuación es homogénea, los coeficientes de las variables no son primos relativos. Si sólo consideramos las soluciones de la forma $x=6k$ y $y=9k$, en efecto todas estas son soluciones, pero nos faltará la solución $x=2$, $y=3$ que no es de esta forma.

Antes de poder usar la proposición, necesitamos dividir entre el máximo común divisor de $9$ y $6$, que es $3$, para obtener primero la ecuación diofantina equivalente $3x-2y=0$. Ahora sí, todas las soluciones enteras de esta ecuación (y por lo tanto de la original) son de la forma $x=2k$ y $y=3k$.

$\triangle$

Pasemos ahora al caso en el que los coeficientes de las variables son primos relativos, pero la ecuación ya no es homogénea.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Sea $c$ un entero divisible entre $\text{MCD}(a,b)$. Se puede obtener una solución $x_0, y_0$ a la ecuación diofantina $ax+by=c$ usando el algoritmo de Euclides. El resto de las soluciones son exactamente de la forma $x=x_0-kb$, $y=y_0+ka$ en donde $k$ es cualquier entero positivo.

Demostración. Notemos que en efecto las soluciones propuestas satisfacen la ecuación diofantina pues
\begin{align*}
ax+by&=a(x_0-kb)+b(y_0+ka)\\
&=ax_0+by_0 + (-kab+kab)\\
&=ax_0+by_0\\
&=c.
\end{align*}

Aquí usamos que $x_0,y_0$ es una solución de $ax+by=c$. Veamos que estas soluciones son las únicas.

Si $x_1,y_1$ es una solución, entonces tenemos $$ax_1+by_1=c=ax_0+by_0,$$ y entonces $$a(x_1-x_0)+b(y_1-y_0)=c-c=0,$$ de modo que $(x_1-x_0)$, $(y_1-y_0)$ es una solución de la ecuación homogénea $ax+by=0$, y por la proposición anterior, debe suceder que $x_1-x_0=-ka$ y $y_1-y_0=kb$ con $k$ un entero. Así, $x_1=x_0-ka$ y $y_1=y_0+kb$, como queríamos.

$\square$

Ejemplo 4. Determina todas las soluciones a la ecuación diofantina $12x+13y=1$.

Solución. Por inspección, una solución es $x=-1$, $y=1$. Los coeficientes de las variables son primos relativos. Por la proposición anterior, todas las soluciones son de la forma $-13k-1$, $12k+1$ donde $k$ es un entero arbitrario.

$\triangle$

Resumimos todo lo obtenido en el siguiente resultado.

Teorema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Consideremos la ecuación diofantina $ax+by=c$. Si $M:=\text{MCD}(a,b)$ no divide a $c$, entonces la ecuación no tiene solución. Si sí, podemos usar el algoritmo de Euclides para encontrar una solución $x_0,y_0$. El resto de las soluciones son de la forma $x_0-ka’$, $y_0+kb’$, en donde $a’=a/M$, $b’=b/M$ y $k$ es cualquier entero.

Veamos un ejemplo en el que juntamos todo lo que ya sabemos.

Ejemplo 5. Determina todas las soluciones a la ecuación diofantina $21x-35y=14$.

Solución. Los coeficientes de las variables no son primos relativos, pues su máximo común divisor es $7$. Tenemos que $7$ divide a $14$, así que la ecuación sí tiene soluciones y son las mismas que las de la ecuación $3x-5y=2$. Por inspección, una solución es $x=-1, y=-1$. Así, todas las soluciones a esta ecuación (y por lo tanto a la original), son de la forma $x=5k-1, y=3k-1$.

$\triangle$

Más adelante…

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Resuelve el Ejemplo 2.
  2. En todos los ejemplos, verifica que las soluciones obtenidas en efecto son soluciones del sistema original.
  3. ¿Para cuántos enteros $c$ entre $1$ y $100$ se tiene que la ecuación lineal $21x+18y=c$ tiene solución $x,y$ en enteros?
  4. Sólo hemos visto ecuaciones diofantinas lineales en dos variables. Sin embargo, con lo visto hasta ahora puedes argumentar por qué la ecuación diofantina $91x+14y-70z=100$ no tiene soluciones en enteros. ¿Por qué?
  5. Investiga acerca de la ecuación pitagórica $x^2+y^2=z^2$.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Problemas de ecuaciones en congruencias y teorema chino del residuo

Por Claudia Silva

Deja un comentario

Introducción

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Teorema chino del residuo

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. También, aprendimos a resolver una ecuación lineal módulo $n$. El resultado principal fue el siguiente:

Teorema 1. Sean $a,b$ enteros y $n$ un entero positivo. La ecuación $ax\equiv b\pmod n$ tiene solución si y sólo si $M:=\text{MCD}(a,n)$ divide a $b$. Cuando sí hay solución, ésta se puede expresar de manera única en módulo $n’:=n/M$.

Ya que sabemos resolver una ecuación lineal, el siguiente paso es aprender a resolver sistemas que involucren dos o más ecuaciones lineales. En esta entrada veremos primero cómo resolver un sistema de dos ecuaciones lineales.

Luego, veremos cómo resolver un sistema con más ecuaciones y demostraremos un resultado clásico: el teorema chino del residuo. Pero para eso necesitaremos el resultado para dos ecuaciones lineales. Vamos poco a poco.

Sistemas de dos ecuaciones lineales

Supongamos que queremos entender por completo el sistema de ecuaciones
\begin{align*}
ax&\equiv b \pmod m\\
cx&\equiv d \pmod n,
\end{align*}

es decir, determinar cuándo existe una $x$ que satisfaga ambas ecuaciones y, si existe, determinar cómo se ven todas las soluciones. Por lo primero que nos tenemos que preocupar es por que cada una de las ecuaciones tenga solución: si alguna no tiene, entonces no hay solución para el sistema.

Así, lo primero que tiene que pasar es que $\text{MCD}(a,m)$ divida a $b$ y que $\text{MCD}(c,n)$ divida a $d$. Cuando sí tienen solución, entonces podemos intercambiar a las ecuaciones por sus ecuaciones reducidas y obtener el sistema de ecuaciones lineales equivalente
\begin{align*}
a’x&\equiv b’ \pmod {m’}\\
c’x&\equiv d’ \pmod {n’}.
\end{align*}

La primera ecuación tiene una única solución módulo $m’$ y la segunda una única solución módulo $n’$, así que este sistema es equivalente al sistema
\begin{align*}
x&\equiv e \pmod {m’}\\
x&\equiv f \pmod {n’},
\end{align*}

en donde $e$ y $f$ son las soluciones a cada una de las ecuaciones lineales reducidas por separado. Ahora sí podemos combinar ambas ecuaciones. Lo único que nos falta es entender cuándo los sistemas de esta forma tienen solución.

Ejemplo 1. El sistema lineal de ecuaciones
\begin{align*}
x&\equiv 2 \pmod 6\\
x&\equiv 4 \pmod {15}
\end{align*}
no tiene solución.

Solución. La primera ecuación implica que $6\mid x-2$. Como $3\mid 6$, por transitividad tenemos $3\mid x-2$, así que la primera ecuación implica que $x$ deja residuo $2$ al dividirse entre $3$.

La segunda ecuación implica que $15\mid x-4$. Como $3\mid 15$, por transitividad $3\mid x-4$, o bien $x\equiv 4 \equiv 1 \pmod 3$. Es decir, la segunda ecuación implica que $x$ deja residuo $1$ al dividirse entre $3$. De esta forma, es imposible satisfacer simultáneamente ambas ecuaciones.

$\triangle$

En el ejemplo anterior, $3$ es el máximo común divisor de $6$ y $15$ y por eso convino estudiar la divisibilidad entre $3$. La siguiente proposición justo dice cuándo el sistema tiene solución en términos de cierta divisibilidad por el máximo común divisor de los módulos.

Proposición 4. Sean $a$ y $b$ enteros y $m$ y $n$ enteros positivos. El sistema lineal de ecuaciones en congruencias
\begin{align*}
x&\equiv a \pmod m\\
x&\equiv b \pmod n
\end{align*}

tiene solución si y sólo si $M:=\text{MCD}(m,n)$ divide a $a-b$. En este caso, la solución se puede expresar de manera única módulo $N:=\text{mcm}(m,n)$, el mínimo común múltiplo de $m$ y $n$.

Demostración. Supongamos que $x$ es solución. Por la primera ecuación, $m\mid x-a$ y como $M\mid m$, entonces $M\mid x-a$. De manera análoga, $M\mid x-b$. Así, $M\mid (x-b)-(x-a)=a-b$, lo cual prueba una implicación de la proposición.

Por otro lado, si $M$ divide a $a-b$, entonces existe una combinación lineal de $m$ y $n$ que da $a-b$, digamos $ym+zn=a-b$, que podemos reescribir como $b+zn=a-ym$. Tomemos $x=b+zn=a-ym$. Notemos que
\begin{align*}
x&=a-ym\equiv a\pmod m\\
x&= b+zn \equiv b \pmod n,
\end{align*}

de modo que $x$ es solución para el sistema. Notemos que $x+rN$ para cualquier $r$ entero y $N$ el mínimo común múltiplo de $m$ y $n$ también es solución pues $N\equiv 0 \pmod m$ y $N\equiv 0 \pmod n$.

Veamos que la solución es única módulo $N$. Si tenemos $x$ y $y$ que son soluciones al sistema, entonces tenemos
\begin{align*}
x&\equiv a \equiv y\pmod m\\
x&\equiv b \equiv y\pmod n,
\end{align*}

lo cual implica $m\mid x-y$ y $n\mid x-y$. Como $N$ es el mínimo común múltiplo, $N\mid x-y$, de modo que $x\equiv y \pmod N$.

$\square$

Terminamos esta sección con un teorema que recopila todo lo que hemos mostrado para dos ecuaciones lineales.

Teorema 2. Consideremos el sistema de ecuaciones
\begin{align*}
ax&\equiv b \pmod m\\
cx&\equiv d \pmod n.
\end{align*}

Si $\text{MCD}(a,m)$ no divide a $b$ o $\text{MCD}(c,n)$ no divide a $d$, entonces el sistema no tiene solución. Si tenemos ambas divisibilidades, entonces el sistema original es equivalente al sistema
\begin{align*}
x&\equiv e \pmod {m’}\\
x&\equiv f \pmod {n’},
\end{align*}

donde $e$ y $f$ son las soluciones únicas a las reducciones de la primer y segunda congruencia respectivamente. Si $\text{MCD}(m’,n’)$ no divide a $e-f$, entonces el sistema original no tiene solución. Si sí, entonces el sistema original tiene una única solución módulo $\text{mcm}(m’,n’)$.

Ejemplo 2. Determina las soluciones al siguiente sistema lineal de ecuaciones:
\begin{align*}
4x&\equiv 12 \pmod {24}\\
10x&\equiv 5 \pmod {75}.
\end{align*}

Solución. Para la primera ecuación, notamos que $\text{MCD}(4,24)=4$ sí divide a $12$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x\equiv 3\pmod 6$.

Para la segunda ecuación, notamos que $\text{MCD}(10,75)=5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2x\equiv 1\pmod {15}$. La solución de esta ecuación es $x\equiv 8 \pmod {15}$. De este modo, el sistema original es equivalente al sistema:

\begin{align*}
x&\equiv 3 \pmod {6}\\
x&\equiv 8 \pmod {15}.
\end{align*}

Tenemos que $\text{MCD}(6,15)=3$. Pero $3$ no divide a $3-8=-5$. Entonces este sistema no tiene solución, y por lo tanto el original tampoco.

$\triangle$

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo 3. Determina las soluciones al siguiente sistema lineal de ecuaciones:
\begin{align*}
4x&\equiv 20 \pmod {24}\\
10x&\equiv 5 \pmod {75}.
\end{align*}

Solución. Para la primera ecuación, notamos que $\text{MCD}(4,24)=4$ sí divide a $20$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x\equiv 5\pmod 6$.

Para la segunda ecuación, notamos que $\text{MCD}(10,75)=5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2x\equiv 1\pmod {15}$. La solución de esta ecuación es $x\equiv 8 \pmod {15}$. De este modo, el sistema original es equivalente al sistema:
\begin{align*}
x&\equiv 5 \pmod {6}\\
x&\equiv 8 \pmod {15}.
\end{align*}

Tenemos que $\text{MCD}(6,15)=3$ y que $3$ sí divide a $5-8=-3$, de modo que sí hay solución. Para encontrarla, expresamos a $-3$ como combinación lineal de $6$ y $15$: $$5-8= -3 = (-3)\cdot 6 + 1\cdot 15.$$

De aquí, $x=8+15=23$ es una solución, y por lo tanto el conjunto de soluciones queda descrito módulo $\text{mcm}(6,15)=30$ de manera única como $$x\equiv 23 \pmod {30}$$.

$\triangle$

El teorema chino del residuo

Varias de las ideas que usamos para un sistema de dos ecuaciones lineales las podemos reciclar para cuando queremos encontrar una $x$ que satisfaga simultáneamente el sistema de ecuaciones lineales en congruencias
\begin{align*}
a_1x&\equiv b_1\pmod {m_1}\\
a_2x&\equiv b_2\pmod {m_2}\\
&\vdots\\
a_nx&\equiv b_n\pmod {m_n}
\end{align*}

Si este sistema tiene solución, entonces claramente:

  • Cada una de las ecuaciones debe tener solución y,
  • cada par de ellas debe tener solución.

Lo impresionante del siguiente teorema es que estas dos condiciones son las únicas que tenemos que verificar para que el sistema tenga solución. Y afortunadamente ya estudiamos cuándo dos ecuaciones lineales en congruencias tienen una solución simultánea.

Si cada una de las ecuaciones del sistema tiene solución, entonces es única, así que podemos remplazar cada ecuación por su solución y obtener un sistema de ecuaciones en donde todos los coeficientes de $x$ son $1$ (como le hicimos en el caso de dos ecuaciones). El siguiente resultado estudia estos sistemas.

Teorema 3. Sea $n\geq 2$ un entero, $b_i$ enteros para $i\in \{1,\ldots,n\}$ y $m_i$ enteros positivos para $i\in \{1,\ldots,n\}$. El sistema de ecuaciones en congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene solución si y sólo si para cada par de índices $i$ y $j$ en $\{1,2,\ldots,n\}$ se tiene que la ecuación $i$ y la ecuación $j$ tienen solución, es decir, si y sólo si $\text{MCD}(m_i,m_j)\mid b_i-b_j$. En este caso, la solución es única módulo $\text{mcd}(m_1,\ldots,m_n)$.

Demostración. Si el sistema completo tiene solución, entonces claramente cualquier par de ecuaciones tiene solución. Para demostrar la afirmación inversa, procederemos por inducción. Para $n=2$ la afirmación es directa, pues justo la hipótesis es que ese par de ecuaciones tiene solución.

Supongamos entonces el resultado cierto para cuando tenemos $n$ ecuaciones y consideremos un sistema con $n+1$ ecuaciones
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}\\
x&\equiv b_{n+1}\pmod {m_{n+1}}.
\end{align*}

Supongamos que cualquier par de ellas tienen solución. Tenemos que mostrar que todo el sistema tiene solución y que es única módulo $\text{mcm}(m_1,\ldots,m_{n+1})$. Como cualquier par tienen solución, entonces cualquier par de las primeras $n$ tienen solución. Por hipótesis inductiva, entonces podemos reemplazar a las primeras ecuaciones por una ecuación módulo $N=\text{mcm}(m_1,\ldots,m_{n})$, que es única por la unicidad en la hipótesis inductiva. En otras palabras, existe un entero $c$ tal que el sistema de ecuaciones original es equivalente al sistema de ecuaciones
\begin{align*}
x&\equiv c \pmod N\\
x&\equiv b_{n+1} \pmod {m_{n+1}}
\end{align*}

Mostraremos ahora que este sistema tiene solución. Para esto, basta mostrar que $\text{MCD}(N,m_{n+1})$ divide a $c-b_{n+1}$.

Como $c$ es solución del sistema para las primeras $n$ ecuaciones, tenemos que $c\equiv b_i\pmod {m_i}$ para toda $i=1,\ldots, n$, es decir, $m_i\mid c-b_i$. Por transitividad, $\text{MCD}(m_{n+1},m_i)\mid c-b_i$.

Como cualquier par de ecuaciones de las originales tenía solución, tenemos que $\text{MCD}(m_{n+1},m_i)\mid b_i-b_{n+1}$. De esta forma, $$\text{MCD}(m_{n+1},m_i)\mid -(c-b_i)-(b_i-b_{n+1})=b_{n+1}-c.$$

Con esto mostramos que cada $\text{MCD}(m_{n+1},m_i)$ divide a $b_{n+1}-c$, de modo que el mínimo común múltiplo de estos números también divide a $b_{n+1}-c$. Pero el mínimo común múltiplo de estos números precisamente $\text{MCD}(N,m_{n+1})$.

En otras palabras, el sistema
\begin{align*}
x&\equiv c \pmod N\\
x&\equiv b_{n+1} \pmod {m_{n+1}},
\end{align*}

que es esquivalente al original, tiene una solución, y esta es única módulo $$\text{mcm}(N,m_{n+1})=\text{mcm}(m_1,\ldots,m_n,m_{n+1}).$$

Esto es justo lo que queríamos para dar el paso inductivo.

$\square$

Como corolario, obtenemos el teorema chino del residuo, que habla acerca de soluciones a sistemas de ecuaciones en los cuales los módulos que tomamos son primos relativos entre sí.

Teorema 4 (teorema chino del residuo). Sea $n\geq 2$ un entero, $b_i$ enteros para $i\in\{1,2,\ldots,n\}$ y $m_i$ enteros positivos para $i\in\{1,\ldots,n\}$. Supongamos además que cada par $m_i, m_j$ de enteros ($i\neq j$) son primos relativos. Entonces el sistema lineal de congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene una y sólo una solución módulo $m_1m_2\ldots m_n$.

Demostración. Como cada pareja de módulos son primos relativos, tenemos que $\text{MCD}(m_i,m_j)=1$ y entonces claramente cada par de ecuaciones tiene solución. Por el Teorema 3, el sistema tiene solución y esta es única módulo el mínimo común múltiplo de $m_1,\ldots,m_n$, que como son primos relativos dos a dos, es $m_1m_2\ldots m_n$.

$\square$

La demostración del Teorema 3 también nos da un procedimiento para resolver de manera práctica los sistemas de ecuaciones lineales en congruencias:

  • Si los coeficientes de $x$ del sistema no son $1$, entonces primero resolvemos todas las ecuaciones con coeficiente distinto de $1$ para transformarla en una del estilo de las del Teorema 3. Si alguna no se puede, entonces el sistema no tiene solución.
  • Una vez que el sistema está en la forma del Teorema 3, verificamos si cada par de ecuaciones tienen solución calculando los máximos comunes divisores de dos en dos y viendo que dividen a las restas respectivas. Si alguno de estos pares falla, entonces el sistema no tiene solución.
  • Si todos los pares cumplen la hipótesis, entonces resolvemos las primeras dos ecuaciones para remplazarlas por otra módulo su mínimo común múltiplo. Luego, usamos esa que obtuvimos y la tercera para remplazarlas por otra. Seguimos así hasta que sólo nos queden dos ecuaciones. La solución a esas será la solución al sistema original.

Ejemplo. Resolvamos el siguiente sistema de congruencias:

\begin{align*}
x&\equiv 11 \pmod{5}\\
x&\equiv 5 \pmod{7}\\
x&\equiv 7 \pmod{11}
\end{align*}

Solución. Los números $5$, $7$ y $11$ son primos relativos por parejas, de modo que la solución existe y es única módulo $5\cdot 7 \cdot 11= 385$. Para encontrarla, primero resolvemos las primeras dos ecuaciones. Estas corresponden al sistema
\begin{align*}
x&\equiv 11\equiv 1 \pmod{5}\\
x&\equiv 5 \pmod{7}
\end{align*}

Para encontrar la solución, ponemos a $1-5=-4$ como combinación lineal de $5$ y $7$, que tras explorar un poco, se puede hacer así: $1-5=-4=2\cdot 5 + (-2)\cdot 7$. De este modo, la solución es $x\equiv 5-14 \equiv -9 \equiv 26 \pmod{35}$ (este es un buen momento para substituir en las dos ecuaciones originales y ver que todo vaya bien).

Así, el sistema original es equivalente al sistema
\begin{align*}
x&\equiv 26 \pmod{35}\\
x&\equiv 7 \pmod{11}
\end{align*}

Ahora lo que tenemos que hacer es expresar a $26-7=19$ como combinación lineal de $35$ y $11$. Es difícil encontrar una combinación «al tanteo», así que aquí es mejor usar el algoritmo de la división de Euclides:
\begin{align*}
35&=3\cdot 11 + 2\\
11&=2\cdot 5 + 1
\end{align*}

De aquí, $$1=11-2\cdot 5=11-(35-3\cdot 11)\cdot 5 = (-5)\cdot 35 +
16\cdot 11,$$ por lo que $$19=(-5\cdot 19)\cdot 35 + (19\cdot 16)\cdot 11=(-95)\cdot 35 + (304)\cdot 11.$$

Así, la solución al sistema está dada por $x=7+304\cdot 11=3351\equiv 271 \pmod {385}$.

$\square$

Más adelante…

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
  2. Cuando un sistema de dos ecuaciones en módulos $m$ y $n$ sí tiene solución, ¿cuántas soluciones módulo $mn$ tiene?
  3. Usando $(\ldots)$ para máximo común divisor y $[\ldots]$ para mínimo común múltiplo, demuestra que para cualesquiera enteros $m_1,m_2,\ldots,m_n$ se tiene que $$([m_1,\ldots,m_n],m_{n+1})=[(m_1,m_{n+1}),\ldots,(m_n,m_{n+1})].$$
  4. Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
  5. Demuestra que para cualquier entero $n\geq 1$ existen $n$ enteros consecutivos tal que la factorización en primos de cada uno de ellos usa al menos dos primos diferentes.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»