Archivo del Autor: Leo

Leo

Acerca de Leo

Hola. Soy Leonardo Martínez. Soy Profesor de Tiempo Completo en la Facultad de Ciencias de la UNAM. Hice un doctorado en Matemáticas en la UNAM, un postdoc en Israel y uno en Francia. Además, me gusta colaborar con proyectos de difusión de las matemáticas como la Olimpiada Mexicana de Matemáticas.

Álgebra Superior II: Ecuaciones diofantinas

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. 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.

\square

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. 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.

\square

Ejemplo. 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.

\square

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. 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.

\square

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. 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.

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Resuelve el Ejemplo 2
  • En todos los ejemplos, verifica que las soluciones obtenidas en efecto son soluciones del sistema original.
  • ¿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?
  • 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é?
  • Investiga acerca de la ecuación pitagórica x^2+y^2=z^2.

Álgebra Lineal I: Rango de transformaciones lineales y matrices

Introducción

En entradas anteriores hablamos de transformaciones lineales, cómo actúan en conjuntos especiales de vectores y de cómo se pueden representar con matrices. Hablamos también de cómo cambiar de una base a otra y cómo usar esto para entender transformaciones en varias bases. Estamos listos para introducir un concepto fundamental de álgebra lineal, el de rango de una transformación lineal y de una matriz.

Antes de entrar en las definiciones formales, vale la pena hablar un poco de rango de manera intuitiva. Supongamos que V es un espacio vectorial de dimensión n y que W es un espacio vectorial sobre el mismo campo que V. Una transformación lineal T:V\to W puede «guardar mucha independencia lineal» o «muy poquita». Si T es inyectiva, ya vimos antes que T manda linealmente independientes a linealmente independientes. Si T es la transformación 0, entonces se «pierde toda la independencia».

El rango mide algo intermedio entre estos dos extremos. Mientras mayor sea el rango, más independencia lineal se preserva y viceversa. Si mantienes esta intuición en mente, varias de las proposiciones te resultarán más naturales.

Otro buen ejemplo para tener en mente es tomar una transformación lineal T:\mathbb{R}^3\to \mathbb{R}^3. Si es la transformación identidad, la base canónica se preserva. Si es la proyección al plano xy, entonces «perdemos» al vector (0,0,1), pues se va al (0,0,0). Si es la proyección al eje x, «perdemos» al (0,1,0) y al (0,0,1) pues ambos se van a (0,0,0). Y si es la transformación 0, perdemos a todos. El rango precisamente va a medir esto, y para estos ejemplos tendremos rango 3, 2, 1 y 0 respectivamente.

Rango para transformaciones lineales

Como en otras ocasiones, cuando hablemos de transformaciones lineales entre espacios vectoriales, serán sobre un mismo campo F.

Definición. Sean V y W espacios de dimensión finita. El rango de una transformación lineal T:V\to W es la dimensión de la imagen de T, es decir,

    \[\rank(T)=\dim\Ima T.\]

Si B es una base de V, entonces genera a V. La transformación T es suprayectiva de V a \Ima T, de modo que T(B) es generador de \Ima T. De esta forma, para encontrar el rango de una transformación lineal T:V\to W basta:

  • Tomar una base B de V
  • Aplicar T a cada elemento de B
  • Determinar un conjunto linealmente independiente máximo en T(B)

Para hacer este último paso, podemos poner a los vectores coordenada de T(B) con respecto a una base de W como los vectores fila de una matriz A y usar reducción gaussiana. Las operaciones elementales no cambian el espacio generado por las filas, así que el rango de T es el número de vectores fila no cero en la forma escalonada reducida A_{\text{red}} de A.

Ejemplo. Encuentra el rango de la transformación lineal T:\mathbb{R}^3\to M_{2}(\mathbb{R}) que manda (x,y,z) a

    \[\begin{pmatrix}x+y-z & 2x \\ 2y-2z & x+z-y\end{pmatrix}.\]

Solución. Tomemos e_1,e_2,e_3 la base canónica de \mathbb{R}^3. Tenemos que T(e_1)=\begin{pmatrix}1 & 2\\ 0 & 1\end{pmatrix}, T(e_2)=\begin{pmatrix} 1 & 0 \\ 2 & -1\end{pmatrix} y T(e_3)=\begin{pmatrix}-1 & 0\\ -2 & 1\end{pmatrix}.

Tomando la base canónica E_{11},E_{12},E_{21},E_{22} de M_2(\mathbb{R}), podemos entonces poner a las coordenadas de T(e_1),T(e_2),T(e_2) como vectores columna de una matriz

    \[\begin{pmatrix}1 & 2 & 0 & 1\\ 1 & 0 & 2 & -1\\ -1& 0 & -2 & 1\end{pmatrix}.\]

Sumando la segunda fila a la tercera, y después restando la primera a la segunda,obtenemos la matriz

    \[\begin{pmatrix}1 & 2 & 0 & 1\\ 0 & -2 & 2 & -2\\ 0& 0 & 0 & 0\end{pmatrix}.\]

De aquí, sin necesidad de terminar la reducción gaussiana, podemos ver que habrá exactamente dos filas no cero. De este modo, el rango de la transformación es 2.

\square

Propiedades del rango

Demostremos ahora algunas propiedades teóricas importantes acerca del rango de una transfromación lineal.

Proposición. Sean U, V y W espacios de dimensión finita. Sean S:U\to V, T:V\to W, T':V\to W transformaciones lineales. Entonces:

  1. \rank(T)\leq \dim V
  2. \rank(T)\leq \dim W
  3. \rank(T\circ S)\leq \rank(T)
  4. \rank(T\circ S)\leq \rank(S)
  5. \rank(T+T')\leq \rank(T) + \rank(T')

Demostración. (1) Pensemos a T como una transformación T:V\to \Ima(T). Haciendo esto, T resulta ser suprayectiva, y por un resultado anterior tenemos que \dim V\geq \dim \Ima T = \rank (T).

(2) Sabemos que \Ima (T) es un subespacio de W, así que \rank(T)=\dim \Ima T \leq \dim W.

(3) La imagen de T contiene a la imagen de T\circ S, pues cada vector de la forma T(S(v)) es de la forma T(w) (para w=S(v)). Así,

    \[\rank(T) =\dim \Ima T \geq \dim \ima T\circ S = \rank (T\circ S).\]

(4) La función T\circ S coincide con la restricción T_{\Ima S} de T a \Ima S. Por el inciso (1), \rank(T_{\Ima S})\leq \dim \Ima S = \rank(S), así que \rank (T\circ S) \leq \rank(S).

(5) Tenemos que \Ima (T+T') \subseteq \Ima T + \Ima T'. Además, por un corolario de la fórmula de Grassman, sabemos que

    \begin{align*}\dim (\Ima T + \Ima T')&\leq \dim \Ima T + \dim \Ima T'\\&= \rank(T) + \rank(T').\end{align*}

Así,

    \begin{align*}\rank(T+T')&\leq \rank(\Ima T + \Ima T')\\&\leq \rank(T)+\rank(T').\end{align*}

\square

Proposición. Sean R:U\to V, T:V\to W y S:W\to Z transformaciones lineales con R suprayectiva y S inyectiva. Entonces

    \[\rank(S\circ T\circ R)=\rank (T).\]

Dicho de otra forma «composición por la izquierda con transformaciones inyectivas no cambia el rango» y «composición por la derecha con transformaciones suprayectivas no cambia el rango». Un corolario es «composición con transformaciones invertibles no cambia el rango».

Demostración. De la proposición anterior, tenemos que \rank(S\circ T)\leq \rank (T). La restricción S_{\Ima T} de S a la imagen de T es una transformación lineal de \Ima T a \Ima (S\circ T) que es inyectiva, de modo que \dim \Ima T \leq \dim \Ima (S\circ T), que es justo \rank(T)\leq \rank(S\circ T), de modo que tenemos la igualdad \rank(S\circ T)=\rank (T).

Como R es suprayectiva, \Ima R= V, de modo que \Ima(S\circ T \circ R)=\Ima(S\circ T). Así,

    \[\rank (S\circ T \circ R) = \rank (S\circ T)=\rank(T).\]

\square

Teorema de rango-nulidad

Una transformación lineal T:V\to W determina automáticamente dos subespacios de manera natural: el kernel \ker T y la imagen \Ima T. Resulta que las dimensiones de \ker T, de \Ima T y de V están fuertemente relacionadas entre sí.

Teorema. Sean V y W espacios de dimensión finita. Sea T:V\to W una transformación lineal. Entonces

    \[\dim\ker T + \rank(T) = \dim V.\]

Demostración. Supongamos que \dim V=n y \dim \ker T = k. Queremos mostrar que \rank(T)=n-k. Para ello, tomemos una base B de \ker T y tomemos B'=\{v_1,\ldots,v_{n-k}\} tal que B\cup B' sea base de V. Basta mostrar que T(B')=\{T(v_1),\ldots,T(v_{n-k})\}\subset \Ima T es base de \Ima T. Sea U el generado por B', de modo que V=U \oplus \ker T.

Veamos que T(B') es generador de \Ima T. Tomemos T(v) en \Ima T. Podemos escribir v=z+u con z\in \ker T y u\in U. Así, T(v)=T(z)+T(u)=T(u)\in T(B').

Ahora veamos que T(B') es linealmente independiente. Si

    \[\alpha_1T(v_1)+\ldots+\alpha_{n-k}T(v_{n-k})=0,\]

entonces T(\alpha_1v_1+\ldots+\alpha_{n-k}v_{n-k})=0, de modo que \alpha_1v_1+\ldots+\alpha_{n-k}v_{n-k} está en U y en \ker T, pero la intersección de estos espacios es \{0\}. Como esta combinación lineal es 0 y B' es linealmente independiente, \alpha_1=\ldots=\alpha_n=0.

De esta forma, T(B') es linealmente independiente y genera a \Ima T, de modo que \rank(T) =|B'|=n-k.

\square

Ejemplo. Consideremos de nuevo la transformación lineal T:\mathbb{R}^3\to M_{2}(\mathbb{R}) que manda (x,y,z) a

    \[\begin{pmatrix}x+y-z & 2x \\ 2y-2z & x+z-y\end{pmatrix}.\]

Muestra que T no es inyectiva.

Solución. Ya determinamos previamente que esta transformación tiene rango 2. Por el teorema de rango-nulidad, su kernel tiene dimensión 1. Así, hay un vector v\neq (0,0,0) en el kernel, para el cual T(v)=0=T(0), de modo que T no es inyectiva.

\square

Problema. Demuestra que para cualquier entero n existe una terna (a,b,c)\neq (0,0,0) con a+b+c=0 y tal que

    \[\int_0^1 at^{2n}+bt^n+c \,dt = 0.\]

Solución. Podríamos hacer la integral y plantear dos ecuaciones lineales. Sin embargo, daremos argumentos dimensionales para evitar la integral. Consideremos las transformaciones lineales T:\mathbb{R}^3\to \mathbb{R} y S:\mathbb{R}^3\to \mathbb{R} dadas por

    \begin{align*}T(x,y,z)&=\int_0^1 xt^{2n}+yt^n+z \,dt\\S(x,y,z)&=x+y+z.\end{align*}


Notemos que T(0,0,1)=\int_0^1 1\, dt = 1=S(0,0,1), de modo que ni T ni S son la transformación 0. Como su rango puede ser a lo más \dim\mathbb{R}=1, entonces su rango es 1. Por el teorema de rango-nulidad, \dim \ker S= \dim \ker T = 2. Como ambos son subespacios de \mathbb{R}^3, es imposible que \ker S \cap \ker T=\{0\}, de modo que existe (a,b,c) no cero tal que T(a,b,c)=S(a,b,c)=0. Esto es justo lo que buscábamos.

\square

Rango para matrices

Definición. El rango de una matriz A en M_{m,n}(F) es el rango de la transformación lineal asociada de F^n a F^m dada por X\mapsto AX. Lo denotamos por \rank(A).

A partir de esta definición y de las propiedades de rango para transformaciones lineales obtenemos directamente las siguientes propiedades para rango de matrices.

Proposición. Sean m, n y p enteros. Sea B una matriz en M_{n,p}(F) y A, A' matrices en M_{m,n}. Sea P una matriz en M_{n,p} cuya transformación lineal asociada es suprayectiva y Q una matriz en M_{r,m} cuya transformación lineal asociada es inyectiva. Entonces:

  1. \rank(A)\leq \min(m,n)
  2. \rank(AB)\leq \min(\rank(A),\rank(B))
  3. \rank(A+A')\leq \rank(A) + \rank(A')
  4. \rank(QAP) = \rank(A)

Como discutimos anteriormente, el rango de una transformación se puede obtener aplicando la transformación a una base y viendo cuál es el máximo subconjunto de imágenes de elementos de la base que sea linealmente independiente. Si tomamos una matriz A en M_{m,n}(F), podemos aplicar esta idea con los vectores e_1,\ldots,e_n de la base canónica de F^{n}. Como hemos visto con anterioridad, para cada i=1,\ldots, n tenemos que el vector Ae_i es exactamente la i-ésima columna de A. Esto nos permite determinar el rango de una matriz en términos de sus vectores columna.

Proposición. El rango de una matriz en M_{m,n}(F) es igual a la dimensión del subespacio de F^m generado por sus vectores columna.

Problema. Determina el rango de la matriz

    \[\begin{pmatrix} 3 & 1 & 0 & 5 & 0\\ 0 & 8 & 2 & -9 & 0\\ 0 & -1 & 0 & 4 & -2\end{pmatrix}.\]

Solución. Como es una matriz con 3 filas, el rango es a lo más 3. Notemos que entre las columnas están los vectores (3,0,0), (0,2,0) y (0,0,-2), que son linealmente independientes. De esta forma, el rango de la matriz es 3.

\square

A veces queremos ver que el rango de un producto de matrices es grande. Una herramienta que puede servir en estos casos es la desigualdad de Sylvester.

Problema (Desigualdad de Sylvester). Muestra que para todas las matrices A, B en M_n(F) se tiene que

    \[\rank(AB)\geq \rank(A)+\rank(B)-n.\]

Solución. Tomemos T_1:F^n\to F^n y T_2:F^n\to F^n tales que T_1(X)=AX y T_2(X)=BX. Lo que tenemos que probar es que

    \[\rank(T_1\circ T_2) \geq \rank(T_1) + \rank(T_2) - n.\]

Consideremos S_1 como la restricción de T_1 a \Ima T_2. Tenemos que \ker S_1 \subset \ker T_1, así que \dim \ker S_1 \leq \dim \ker T_1. Por el teorema de rango-nulidad en S_1, tenemos que

    \begin{align*}rank(T_2) &= \dim \Ima T_2 \\&= \dim \ker S_1 + \rank(S_1) \\&= \dim \ker S_1 + \rank(T_1\circ T_2)\\&\leq \dim \ker T_1 + \rank(T_1\circ T_2),\end{align*}

así que

    \[\rank(T_2)\leq \dim \ker T_1 + \rank(T_1\circ T_2).\]

Por el teorema de rango-nulidad en T_1 tenemos que

    \[\dim \ker T_1 + \rank(T_1)=n.\]

Sumando la desigualdad anterior con esta igualdad obtenemos el resultado.

\square

El teorema PJQ (opcional)

El siguiente resultado no se encuentra en el temario usual de Álgebra Lineal I. Si bien no formará parte de la evaluación del curso, recomendamos fuertemente conocerlo y acostumbrarse a usarlo pues tiene amplias aplicaciones a través del álgebra lineal.

Teorema (Teorema PJQ). Sea A una matriz en M_{m,n}(F) y r un entero en \{0,\ldots,\min(m,n)\}. El rango de A es igual a r si y sólo si existen matrices invertibles P\in M_m(F) y Q\in M_n(F) tales que A=PJ_rQ, en donde J_r es la matriz en M_{m,n} cuyas primeras r entradas de su diagonal principal son 1 y todas las demás entradas son cero, es decir, en términos de matrices de bloque,

    \[J_r=\begin{pmatrix}I_r & 0 \\0 & 0\end{pmatrix}.\]

No damos la demostración aquí. Se puede encontrar en el libro de Titu Andreescu, Teorema 5.68. Veamos algunas aplicaciones de este teorema.

Problema. Muestra que una matriz tiene el mismo rango que su transpuesta.

Solución. Llamemos r al rango de A. Escribimos A=PJ_rQ usando el teorema PJQ, con P y Q matrices invertibles. Tenemos que ^tA=^tQ\, ^tJ_r \,^tP, con ^tQ y ^tP matrices invertibles. Además, ^t J_r es de nuevo de la forma de J_r. Así, por el teorema PJQ, tenemos que ^t A es de rango r.

Combinando el problema anterior con el resultado del rango de una matriz en términos de sus vectores columna obtenemos lo siguiente.

Proposición. El rango de una matriz en M_{m,n}(F) es igual a la dimensión del subespacio de F^n generado por sus vectores renglón.

Terminamos esta entrada con una aplicación más del teorema PJQ.

Problema. Muestra que una matriz A de rango r se puede escribir como suma de r matrices de rango 1. Muestra que es imposible hacerlo con menos matrices.

Solución. Expresamos A=PJ_rQ usando el teorema PJQ. Si definimos A_i=PE_{ii}Q para i=1,\ldots,r, donde E_{ii} es la matriz cuya entrada (i,i) es uno y las demás cero, claramente tenemos que J_r=E_{11}+E_{22}+\ldots+E_{rr}, por lo que

    \[A=PJ_rQ=A_1+A_2+\ldots+A_r.\]

Además, como E_{ii} es de rango 1, por el teorema PJQ cada matriz A_i es de rango 1.

Veamos que es imposible con menos. Si B_1,\ldots,B_s son matrices de rango 1, como el rango es subaditivo tenemos que \rank (B_1+\ldots+B_s)\leq s. Así, si sumamos menos de r matrices, no podemos obtener a A.

\square

Tarea Moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Termina de hacer la reducción gaussiana del primer ejemplo.
  • Sea T una transformación de un espacio vectorial V de dimensión finita a si mismo. Usa el teorema de rango-nulidad para mostrar que si T es inyectiva o suprayectiva, entonces es biyectiva.
  • Determina el rango de la matriz

        \[\begin{pmatrix} 0 & 0 & 0 & 8 & 3\\ 7 & 8 & -1 & -2 & 0\\ 3 & -1 & 4 & 4 & -9\end{pmatrix}.\]

  • Demuestra que aplicar operaciones elementales a una matriz no cambia su rango.
  • Demuestra que matrices similares tienen el mismo rango.
  • Demuestra por inducción que para matrices A_1,\ldots, A_n del mismo tamaño tenemos que

        \[\rank (A_1+\ldots+A_n)\leq \sum_{i=1}^n \rank(A_i).\]

  • Escribe la demostración de la última proposición de la sección del teorema PJQ
  • Revisa la demostración del teorema de descomposición PJQ en el libro de Titu Andreescu.

Seminario de Resolución de Problemas: Primos y factorización única

Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El 1 no es primo pues su único divisor es él mismo. Pero 2, 17 y 31 sí son primos. De aquí y el algoritmo de la división, si p es primo y a es un entero, entonces p\mid a o \MCD{p,a}=1.

Proposición 1. Si p es un número primo que divide al producto de enteros ab, entonces p\mid a ó p\mid b.

Demostración. Si p no divide a a, entonces \MDC(p,a)=1, así que existe una combinación lineal entera pn+am=1. Multiplicando esta combinación por b, tenemos que pbn+abm=b. Como p divide a pbn y a ab, entonces divide a b.

\square

Problema. Muestra que si p es un primo que divide a 123456^{654321}, entonces p divide a 123456.

Sugerencia pre-solución. Aquí 123456 y 654321 no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea a un entero, n un entero positivo y p un primo. Vamos a mostrar por inducción en n que si p\mid a^n, entonces p\mid a. Para n=1 la conclusión es inmediata. Supongamos el resultado cierto para n. Si p\mid a^{n+1}, por la Proposición 1 tenemos que p\mid a (en cuyo caso terminamos), o que p\mid a^n (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando a=123456 y n=6543321.

\square

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si p es primo, a un entero y n un entero positivo tales que p\mid a^n, entonces p^n\mid a^n.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean a un entero positivo. Entonces existe un único n, únicos primos p_1<\ldots<p_n y exponentes \alpha_1,\ldots,\alpha_n tales que

    \[a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.\]

La idea de la demostración es factorizar y factorizar. Si n está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que \sqrt[3]{7} es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos \sqrt[3]{7}=\frac{a}{b} con a y b enteros. De aquí, 7b^3=a^3. En la factorización en primos de a^3 y b^3 tenemos una cantidad múltiplo de 3 de factores 7. Así, en el lado derecho tenemos una cantidad mútiplo de 3 de factores 7 (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

\square

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos n para los cuales 2^8+2^{11}+2^n es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo m^2=2^8+2^{11}+2^n. De aquí,

    \begin{align*}2^n&=m^2-2^8(1+2^3)\\&=m^2-(3\cdot 2^4)^2\\& =(m+48)(m-48).\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números m+48 y m-48 tienen que ser potencias de 2, digamos m+48=2^a y m-48=2^b con a>b y a+b=n. Además tenemos que

    \[2^b(2^{a-b}-1)=96=2^5\cdot 3.\]

Como 2^{a-b}-1 es impar, de nuevo por la unicidad de la factorización en primos debemos tener que 2^{a-b}-1=3, y por lo tanto que 2^b=2^5. De aquí, b=5 y a-b=2, y así a=7. Por lo tanto, el único candidato es n=5+7=12.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que n en efecto es solución. Hacemos esto último notando que 2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2 que en efecto es un número cuadrado.

\square

Fórmulas que usan el teorema fundamental de la aritmética

Sean a y b números enteros positivos y P={p_1,\ldots,p_n} el conjunto de números primos que dividen a alguno de a o b. Por el teorema fundamental de la aritmética, existen exponentes \alpha_1,\ldots,\alpha_n y \beta_1,\ldots,\beta_n, tal vez algunos de ellos cero, tales que

    \begin{align*}a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si a=21, b=28, entonces P={2,3,7}, a=2^0 3^1 7^1 y b=2^2 3^0 7^1.

Proposición 3. Se tiene que a divide a b si y sólo si para todo primo p_i se tiene que \alpha_i\leq \beta_i.

Problema. ¿Cuántos múltiplos de 108 hay que sean divisores de 648?

Sugerencia pre-solución. Factoriza en primos a 108 y a 648 y usa la Proposición 3.

Solución. Tenemos que 108=2^23^3 y que 648=2^3\cdot 3^4. Por la Proposición 3, un número que funcione debe ser de la forma 2^a3^b con 2\leq a \leq 3 y con 3\leq b \leq 4. Así, a tiene 2 posibilidades y b también, de modo que hay 2\cdot 2=4 números que cumplen.

\square

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero a tiene (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1) divisores positivos.

Problema. Determina cuántos enteros hay entre 1 y 10000 que tienen 49 divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se 49.

Solución. Tomemos a un entero y p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} su factorización en primos. Por la Proposición 4, necesitamos que (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49.

A la izquierda tenemos puros números mayores o iguales que 2. El número 49 tiene como únicos divisores a 1, 7 y 49. De esta forma, sólo hay dos casos posibles:

  • El número a tiene sólo un divisor primo y a=p_1^{48}
  • El número a tiene dos divisores primos y a=p_1^6p_2^6

El primer caso es imposible, pues p_1 sería por lo menos 2 y 2^{48}>2^{20}=(1024)^2>(1000)^2>10000. Para el segundo caso, recordemos que p_2>p_1 en la factorización en primos. Si p_2\geq 5, entonces como p_1\geq 2, tendríamos a\geq (2\cdot 5)^6 = 1000000>10000, así que esto no es posible.

La única otra posibilidad es p_2=3 y por lo tanto p_1=2. En este caso obtenemos al número a=(2\cdot 3)^6=6^6=46656, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

\square

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular \MCD{a,b} y \mcm{a,b} como sigue:

    \begin{align*}\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que \MCD{a,b}\mcm{a,b}=ab.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a a y b en su factorización en primos como lo discutimos arriba. Al multiplicar \MCD{a,b} y \mcm{a,b}, el exponente de p_i es \min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i\beta_i. Este es el mismo exponente de p_i en ab. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si p es primo, entonces todo entero n que no sea múltiplo de p tiene inverso módulo n. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.

Álgebra Lineal I: Cambios de base, parte 2

Introducción

En la entrada anterior definimos las matrices de cambio de base. Vimos algunas de sus propiedades básicas y mostramos cómo nos pueden ayudar para resolver el primero de los siguientes dos problemas.

  • Supongamos que tenemos dos bases B_1 y B_2 de un espacio vectorial V y que tomamos un vector v en V. Si ya sabemos la combinación lineal de elementos de B_1 que da v, ¿cómo podemos saber la combinación lineal de elementos de B_2 que da v? En otras palabras, ¿cómo podemos pasar a v de su expresión en base B_1 a su expresión en base B_2?
  • Supongamos que tenemos una transformación lineal T:V\to W entre dos espacios vectoriales V y W, dos bases B_1 y B_2 de V y dos bases C_1 y C_2 de W. Si ya sabemos qué le hace T a los elementos de V en términos de las bases B_1 y C_1, ¿cómo podemos saber qué hace T en términos de las bases B_2 y C_2?

El objetivo de esta entrada es ver cómo con las matrices de cambio de base también podemos resolver el segundo problema. Después de hacer esto, hablaremos de una noción fundamental en álgebra lineal: la de matrices similares.

Matrices de cambio de base y transformaciones lineales

Las matrices de cambios de base nos ayudan a entender a las matrices de transformaciones lineales en bases diferentes.

Teorema. Sea T:V\to W una transformación lineal entre espacios de dimensión finita V y W. Sean B_1 y B_2 bases de V, y C_1 y C_2 bases de W. Entonces

    \[\Mat_{C_2,B_2}(T) = \Mat_{C_2}(C_1)\Mat_{C_1,B_1}(T)\Mat_{B_1}(B_2).\]

Observa cómo la elección de orden en la notación está rindiendo fruto. En el lado derecho «van apareciendo las bases» en el «orden natural» C_2, C_1, B_1, B_2.

Demostración. Sean P=\Mat_{C_1}(C_2) y Q=\Mat_{B_1}(B_2). Por un resultado de la entrada anterior, P es la matriz que representa a la transformación identidad en W con respecto a las bases C_1 y C_2, es decir, P=\Mat_{C_1,C_2}(\text{id}_W).

Por cómo son las matrices de composiciones de transformaciones lineales, y usando que \text{id}_W\circ T=T, tenemos que

    \[\Mat_{C_1,C_2}(\text{id}_W)\Mat_{C_2,B_2}(T)=\Mat_{C_1,B_2}(T).\]

De manera análoga, Q es la matriz que representa a la transformación identidad en V con respecto a las bases B_1 y B_2, de donde tenemos que

    \[\Mat_{C_1,B_1}(T)\Mat_{B_1,B_2}(\text{id}_V)=\Mat_{C_1,B_2}(T).\]

De esta forma,

    \[P\Mat_{C_2,B_2}(T) = \Mat_{C_1,B_2}(T) = \Mat_{C_1,B_1}(T) Q.\]

El resultado se obtiene multiplicando por la izquierda ambos lados de esta ecuación por P^{-1}=\Mat_{C_2}(C_1).

\square

En la siguiente entrada se verán varios ejemplos que involucran crear matrices para transformaciones lineales, matrices de cambios de base y multiplicarlas para entender una transformación lineal en distintas bases.

Por el momento, dejamos únicamente un corolario del teorema anterior, para el caso en el que tenemos una transformación lineal de un espacio vectorial a sí mismo expresado en términos de dos bases.

Corolario. Sea T:V\to V una transformación lineal de un espacio vectorial V de dimensión finita a sí mismo. Sean B y B' bases de V y P la matriz de cambio de base de B a B'. Entonces

    \[\Mat_{B'}(T)=P^{-1}\Mat_{B}(T)P.\]

Matrices similares

Definición. Decimos que dos matrices A y B en M_{n}(F) son similares o conjugadas si existe una matriz invertible P en M_n(F) tal que B=P^{-1}AP.

En otras palabras, A y B son matrices similares si representan a una misma transformación lineal en diferentes bases.

Proposición. La relación «ser similares» es una relación de equivalencia en M_n(F).

Demostración. Toda matriz es similar a sí misma usando P=I_n, la identidad. Si A y B son similares con matriz invertible P, entonces B y A son similares con matriz invertible P^{-1}. Si A y B son similares con matriz invertible P y B y C son similares con matriz invertible Q, notemos que A=P^{-1}BP=P^{-1}(Q^{-1}CQ)P=(QP)^{-1}C(QP), de modo que A y C son similares con matriz invertible QP.

\square

¿Por qué es importante saber si dos matrices son similares? Resulta que dos matrices similares comparten muchas propiedades, como su traza, su determinante, su rango, etc. Para algunas matrices es más sencillo calcular estas propiedades. Así que una buena estrategia en álgebra lineal es tomar una matriz A «complicada» y de ahí encontrar una matriz similar B «más simple», y usar B para encontrar propiedades de A.

Veamos un ejemplo de esto. Mediante un sencillo argumento inductivo se puede mostrar lo siguiente.

Proposición. Si A y B son matrices similares con A=P^{-1}BP, entonces A^n=P^{-1}B^nP.

Si B fuera una matriz diagonal, entonces es fácil encontrar B^n: basta con elevar cada una de las entradas de su diagonal a la n (lo cual es mucho más fácil que hacer productos de matrices). Así, esto da una forma muy fácil de encontrar A^n: basta con encontrar B^n, y luego hacer dos multiplicaciones de matrices más, por P^{-1} a la izquierda y por P a la derecha.

Cuando A es una matriz similar a una matriz diagonal, decimos que A es diagonalizable. Una parte importante de lo que resta del curso consistirá en entender por qué las matrices simétricas con entradas reales son diagonalizables.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Deduce el corolario del teorema principal de esta entrada.
  • Considera \mathbb{R}[x]_2 de polinomios con coeficientes reales y grado a lo más dos. Sea T: \mathbb{R}[x]_2 la transformación tal qur T(p)=p', el polinomio derivado. Encuentra la matriz que representa a la transformación en la base \{1+x+x^2,1+2x,1\} y la matriz que representa a la transformación en la base \{1,x,x^2\}. Encuentra también la matriz de cambio de base de la primera a la segunda. Verifica que se cumple la conclusión del corolario.
  • Sean A y B matrices similares. Muestra que A es invertible si y sólo si B lo es.
  • Sean A y B matrices similares. Muestra que A y B tienen la misma traza.
  • Completa el argumento inductivo para demostrar la última proposición.
  • Considera la matriz con entradas complejas A=\begin{pmatrix}1 & 0 & 0\\ 0 & i & 0\\ 0 & 0 & -1 \end{pmatrix}. Encuentra A^{105}.

Álgebra Superior II: Teorema chino del residuo

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. 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.

\square

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. 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.

\square

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo. 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}\]

.

\square

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

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
  • Cuando un sistema de dos ecuaciones en módulos m y n sí tiene solución, ¿cuántas soluciones módulo mn tiene?
  • 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})].\]

  • Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
  • Problema. 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.