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

Por Claudia Silva

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»

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

Por Leonardo Ignacio Martínez Sandoval

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: Problemas de cambio de base

Por Blanca Radillo

Introducción

En las entradas anteriores platicamos acerca de matrices de cambio de base. Vimos cómo nos ayudan a pasar un vector expresado en una base a otra. También vimos cómo nos ayudan a entender una transformación lineal en bases distintas. En esta entrada, veremos algunos ejemplos para repasar estos conceptos.

Problemas resueltos

Problema 1. Considera las familias de vectores $B=\{v_1,v_2,v_3\}$, $B’=\{w_1,w_2,w_3\}$, donde $$v_1=(0,1,1), \ v_2=(1,0,1), \ v_3=(1,1,0)$$ y $$w_1=(1,1,-1), \ w_2=(1,0,-1), \ w_3=(-1,-1,0).$$

  1. Prueba que $B$ y $B’$ son bases de $\mathbb{R}^3$.
  2. Encuentra la matriz de cambio de base $P$ de $B$ a $B’$ usando la definición de $P$.
  3. Encuentra la matriz de cambio de base $P$ usando la base canónica de $\mathbb{R}^3$ y la última proposición de esta entrada.

Solución. (1) Dado que $\dim \mathbb{R}^3=3$ y estas familias son de tres vectores, basta con demostrar que son vectores linealmente independientes. Una manera de hacerlo es formando la matriz obtenida al colocar a los vectores como renglones y reducirla hasta la matriz identidad $I_3$.

Para $B$, la matriz asociada es $$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.$$

Haciendo los cálculos de la reducción, obtenemos que

\begin{align*}
&\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\\
\to&\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\\
\to &\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 0 & 1 & 1 \end{pmatrix}\\
\to &\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix} \\
\to &\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.
\end{align*}

Esto implica que los vectores en $B$ son linealmente independientes y, por lo tanto, forman una base $\mathbb{R}^3$.

Para $B’$, la matriz asociada es $$\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

Reduciendo la matriz, tenemos que

\begin{align*}&\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix} \\
\to &\begin{pmatrix} 1 & 1 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{pmatrix} \\
\to &\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.\end{align*}

Por lo tanto, $B’$ también es una base de $\mathbb{R}^3$.

(2) Recordemos que la matriz de cambio de base $P$ está definida como la matriz $[p_{ij}]$ cuya columna $j$ tiene como entradas a las coordenadas de $w_j$ escrito en términos de la base $B$. Entonces, expresemos

\begin{align*}
(1,1,-1)&=w_1=av_1+bv_2+cv_3=(b+c,a+c,a+b),\\
(1,0,-1)&=w_2=dv_1+ev_2+fv_3=(e+f,d+f,d+e),\\
(-1,-1,0)&=w_3=gv_1+hv_2+kv_3=(h+k,g+k,g+h),
\end{align*}

obteniendo que

\begin{align*}
b+c&=1\\
a+c&=1\\
a+b&=-1\\
e+f&=1\\
d+f&=0\\
d+e&=-1\\
h+k&=-1\\
g+k&=-1\\
g+h&=0.
\end{align*}

Si resolvemos el sistema anterior, concluimos que $a=b=-\frac{1}{2}$, $c=\frac{3}{2}$, $d=-1$, $e=0$, $f=1$, $g=h=0$, $k=-1$. Por lo tanto

$$P=\begin{pmatrix} a & d & g \\ b & e & h \\ c & f & k \end{pmatrix}= \begin{pmatrix} -\frac{1}{2} & -1 & 0 \\ -\frac{1}{2} & 0 & 0 \\ \frac{3}{2} & 1 & -1 \end{pmatrix}.$$

(3) Sea $B»=\{e_1,e_2,e_3\}$ la base canónica de $\mathbb{R}^3$. Queremos encontrar la matriz de cambio de base denotada como $\text{Mat}_B (B’)$. Usando la última proposición de la clase del lunes, tenemos que

$$\text{Mat}_B (B’)=\text{Mat}_{B} (B») \cdot \text{Mat}_{B»} (B’)=(\text{Mat}_{B»} (B))^{-1} \cdot \text{Mat}_{B»} (B’).$$

Por definición,

$$\text{Mat}_{B»} (B)=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}, \ \text{Mat}_{B»} (B’)=\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

Para calcular $(\text{Mat}_{B»} (B))^{-1}$, lo haremos como ya lo hemos visto en clases: pegando a la derecha una matriz identidad y aplicando reducción gaussiana:

\begin{align*} &\left( \begin{array}{ccc|ccc} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \\ \rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & -1 & 0 & -1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 1 & -1 & 1 \\ 0 & 0 & 2 & 1 & 1 & -1 \end{array} \right) \\ \rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & -1/2 & 1/2 & 1/2 \\ 0 & 1 & 0 & 1/2 & -1/2 & 1/2 \\ 0 & 0 & 1 & 1/2 & 1/2 & -1/2 \end{array} \right).
\end{align*}

Por lo tanto, $$(\text{Mat}_{B»}(B))^{-1}=\begin{pmatrix} -1/2 & 1/2 & 1/2 \\ 1/2 & -1/2 & 1/2 \\ 1/2 & 1/2 & -1/2 \end{pmatrix}.$$

Finalmente, usando la proposición, tenemos que

$$P=\text{Mat}_B (B’)=\begin{pmatrix} -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix}\cdot\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}$$

$$=\begin{pmatrix} -\frac{1}{2} & -1 & 0 \\ -\frac{1}{2} & 0 & 0 \\ \frac{3}{2} & 1 & -1 \end{pmatrix}. $$

Esto coincide con el cálculo que hicimos previamente.

$\square$

Problema 2. Considera la matriz $$A=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}$$

y sea $T:\mathbb{R}^3 \rightarrow \mathbb{R}^3$ la transformación lineal asociada, es decir $T(X)=AX$ para todo $X\in\mathbb{R}^3$. Considera los vectores

$$v_1=\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}, \ v_2=\begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}, \ v_3=\begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}.$$

  1. Prueba que $v_1,v_2,v_3$ forman una base de $\mathbb{R}^3$ y calcula la matriz de $T$ con respecto a esta base.
  2. Encuentra la matriz de cambio de base de la base canónica a la base $\{v_1,v_2,v_3\}$.
  3. Calcula $A^n$ para todo entero positivo $n$.

Antes de ver la solución a este problema este problema, observa que sería muy difícil decir quién es $A^{100}$ «a mano» si procedes directamente. Se tendrían que hacer muchas multiplicaciones matriciales, que son difíciles. Ten en mente esto cuando leas la solución de la parte 3.

Solución. (1) Dado que la dimensión de $\mathbb{R}^3$ es 3 y $\{v_1,v_2,v_3\}$ son tres vectores, basta con demostrar que éstos son linealmente independientes para probar que forman una base. Sean $a,b,c\in\mathbb{R}$ tales que $av_1+bv_2+cv_3=0$, entonces

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

Entonces, son linealmente independientes y, por lo tanto, forman una base de $\mathbb{R}^3$.

Nota: Otra manera de demostrarlo es considerar la matriz formada por los vectores $v_1,v_2,v_3$ como sus columnas, reducirla y llegar a que la matriz reducida es la matriz identidad.

Ahora, para calcular la matriz de $T$ con respecto a la nueva base, expresaremos $T(v_1),T(v_2), T(v_3)$ en términos de $v_1,v_2,v_3$. Entonces tenemos que

$$T(v_1)=Av_1=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=v_1,$$

$$T(v_2)=Av_2=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}=\begin{pmatrix} 2 \\ 0 \\ -2 \end{pmatrix}=2v_2,$$

$$T(v_3)=Av_3=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}=\begin{pmatrix} 3 \\ -3 \\ 0 \end{pmatrix}=3v_3.$$

Por lo tanto, la matriz que buscamos es $$B=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}.$$

(2) Lo haremos de la misma manera que en el inciso (2) del problema anterior, que consiste en escribir a los $v_1,v_2,v_3$ en la base canónica, pero ésto es obvio ya que están escritos de esa manera, por lo tanto $$P=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

(3) Sabemos que la matriz de $T$ con respecto a $v_1,v_2,v_3$ (que nombramos en el inciso (1) como $B$) es igual a $P^{-1}AP$, gracias al último corolario de la sección «Matrices de cambio de base y transformaciones lineales» de la entrada anterior. Entonces $$P^{-1}AP=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}.$$

Es fácil ver (pero lo pueden demostrar por inducción en $n$) que $$(P^{-1}AP)^n=(P^{-1}AP)(P^{-1}AP)\dots (P^{-1}AP)=P^{-1}A^n P.$$

Esto implica que $P^{-1}A^n P=B^n$, es decir $$P^{-1}A^n P=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}.$$

Multiplicando por $P$ a la izquierda y por $P^{-1}$ a la derecha, obtenemos que $$A^n=P\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}P^{-1} .$$

Para ello, nos falta calcular la inversa de $P$, y eso lo haremos como siempre lo hemos hecho: reduciendo la matriz. Entonces

\begin{align*} &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & -1 & 0 & 1 & 0 \\ -1 & -1 & 0 & 0 & 0 & 1 \end{array} \right) \\\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & -1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & -1 & -1 & -2 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right) \\\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & -1 & -1 & -2 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right). \end{align*}

Como consecuencia, tenemos que $$P^{-1}=\begin{pmatrix} 1 & 1 & 1 \\ -1 & -1 & -2 \\ 1 & 0 & 1 \end{pmatrix}.$$

Por lo tanto,

\begin{align*}
A^n &=P \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix} P^{-1}\\
&=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}\begin{pmatrix} 1 & 1 & 1 \\ -1 & -1 & -2 \\ 1 & 0 & 1 \end{pmatrix}
\end{align*}

$$A^n= \begin{pmatrix} 1-2^n+3^n & 1-2^n & 1-2^{n+1}+3^n \\ 1-3^n & 1 & 1-3^n \\ 2^n-1 & 2^n-1 & 2^{n+1}-1 \end{pmatrix}.$$

$\square$

El ejercicio anterior deja una moraleja importante de álgebra lineal: si tenemos una matriz $A$ y logramos encontrar una matriz diagonal $B$ similar a ella, entonces será fácil encontrar $A^n$. Para finalizar esta sesión, tenemos el siguiente problema.

Problema 3. Prueba que las matrices $$A=\begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \ \text{y} \ B=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$ son similares.

Solución. Para resolverlo usaremos el corolario de la entrada anterior. Al escribirlo en este contexto, dice lo siguiente:

Corolario. Sea $T:\mathbb{R}^4\rightarrow \mathbb{R}^4$ una transformación lineal. Sean $B’$ y $B»$ bases de $\mathbb{R}^4$ y $P$ la matriz de cambio de base de $B’$ a $B»$. Entonces $\text{Mat}_{B»}(T)=P^{-1} \text{Mat}_{B’}(T) P.$

Si podemos encontrar una transformación $T$ y bases $B’$ y $B»$ tales que $\text{Mat}_{B’}(T)=A$ y $\text{Mat}_{B»} (T)=B$, podemos calcular la matriz de cambio de base $P$, y satisface que $B=P^{-1}AP$, implicando que $A$ y $B$ sean matrices similares. Entonces, el problema se reduce a encontrar la transformación, las bases y calcular $P$.

Dado que $\text{Mat}_{B’}(T)=A$, si $B’$ es la base canónica, es claro que la transformación $T$ satisface que $T(X)=AX$ para todo $X\in\mathbb{R}^4$.

Ahora, encontremos $B»$. Sea $B»=\{ v_1,v_2,v_3,v_4 \}$ con

$$v_1=\begin{pmatrix} x_1 \\ y_1 \\ z_1 \\ w_1 \end{pmatrix}, v_2=\begin{pmatrix} x_2 \\ y_2 \\ z_2 \\ w_2 \end{pmatrix}, v_3=\begin{pmatrix} x_3 \\ y_3 \\ z_3 \\ w_3 \end{pmatrix}, v_4=\begin{pmatrix} x_4 \\ y_4 \\ z_4 \\ w_4 \end{pmatrix}.$$

Dado que $\text{Mat}_{B»}(T)=B$, entonces satisface

$$T(v_1)=Av_1=v_1, \ T(v_2)=Av_2=2v_1+v_2,$$

$$T(v_3)=Av_3=3v_1+2v_2+v_3, \ T(v_4)=Av_4=4v_1+3v_2+2v_3+v_4.$$

Resolviendo lo anterior, obtenemos que

$$Av_1=\begin{pmatrix} x_1+y_1 \\ y_1+z_1 \\ z_1+w_1 \\ w_1 \end{pmatrix}=\begin{pmatrix} x_1 \\ y_1 \\ z_1 \\ w_1 \end{pmatrix} \ \Rightarrow \ v_1=\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix},$$

$$Av_2=\begin{pmatrix} x_2+y_2 \\ y_2+z_2 \\ z_2+w_2 \\ w_2 \end{pmatrix}=\begin{pmatrix} x_2+2 \\ y_2 \\ z_2 \\ w_2 \end{pmatrix} \ \Rightarrow \ v_2=\begin{pmatrix} 1 \\ 2 \\ 0 \\ 0 \end{pmatrix},$$

$$Av_3=\begin{pmatrix} x_3+y_3 \\ y_3+z_3 \\ z_3+w_3 \\ w_3 \end{pmatrix}=\begin{pmatrix} x_3+5 \\ y_3+4 \\ z_3 \\ w_3 \end{pmatrix} \ \Rightarrow \ v_3=\begin{pmatrix} 1 \\ 5 \\ 4 \\ 0 \end{pmatrix},$$

y por último

$$Av_4=\begin{pmatrix} x_4+y_4 \\ y_4+z_4 \\ z_4+w_4 \\ w_4 \end{pmatrix}=\begin{pmatrix} x_4+9 \\ y_4+16 \\ z_4+8 \\ w_4 \end{pmatrix} \ \Rightarrow \ v_4=\begin{pmatrix} 1 \\ 9 \\ 16 \\ 8 \end{pmatrix}$$

Aquí estamos usando que los sistemas de ecuaciones que se obtienen tienen como variables libres a $x_1,x_2,x_3,x_4$, las cuales las estamos tomando todas ellas iguales a $1$.

Estos vectores son linealmente independientes pues la matriz con ellos como columnas es triangular superior con entradas en la diagonal distintas de cero, de modo que su matriz reducida es la identidad. Como $\mathbb{R}^4$ es de dimensión $4$ y $B»$ es un conjunto de cuatro vectores linealmente independientes, entonces $B»$ es una base. Más aún, $B»$ es una base tal que $\text{Mat}_{B»} (T)=B$, por construcción.

Finalmente, podemos calcular la matriz de cambio de base $P$ de $B’$ a $B»$, pero es fácil ya que $B’$ es la base canónica, entonces $$P=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}.$$

Por propiedades de la matriz de cambio de base, sabemos que $P$ es invertible. Entonces, para terminar la prueba, podemos encontrar $P^{-1}$ y verificar que $B=P^{-1}AP$, o simplemente verificamos que $PB=AP$, y por lo tanto $A$ y $B$ son matrices similares. Lo haremos de la segunda manera. En efecto,

$$PB=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 3 & 6 & 10 \\ 0 & 2 & 9 & 25 \\ 0 & 0 & 4 & 24 \\ 0 & 0 & 0 & 8 \end{pmatrix}$$

$$AP=\begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}=\begin{pmatrix} 1 & 3 & 6 & 10 \\ 0 & 2 & 9 & 25 \\ 0 & 0 & 4 & 24 \\ 0 & 0 & 0 & 8 \end{pmatrix}.$$

Por lo tanto, $A$ y $B$ son matrices similares.

Nota: si calculas la inversa de $P$, obtienes como resultado que $$P^{-1}=\begin{pmatrix} 1 & -\frac{1}{2} & \frac{3}{8} & -\frac{5}{16} \\ 0 & \frac{1}{2} & -\frac{5}{8} & \frac{11}{16} \\ 0 & 0 & \frac{1}{4} & -\frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{8} \end{pmatrix}.$$

$\square$

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»

Álgebra Lineal I: Cambio de base de transformaciones lineales

Por Leonardo Ignacio Martínez Sandoval

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.

Más adelante…

En estas últimas dos entradas aprendimos a hacer «cambios de base», tanto para coordenadas, como para formas matriciales. También, introdujimos el concepto de similitud de matrices. Cuando $A$ es una matriz similar a una matriz diagonal, decimos que $A$ es diagonalizable. Que una matriz sea diagonalizable trae muchas ventajas. Como ya mencionamos, una de ellas es poder elevar la matriz a potencias de manera sencilla. Otra ventaja es que en las matrices diagonalizables es sencillo calcular rangos, determinantes y otras invariantes de álgebra lineal.

Una parte importante de lo que resta del curso consistirá en entender por qué las matrices simétricas con entradas reales son diagonalizables. El teorema principal del curso (el teorema espectral), consistirá en mostrar que toda matriz simétrica con entradas reales es diagonalizable mediante matrices ortogonales. Para poder demostrarlo, necesitaremos primero estudiar teoría geométrica de espacios vectoriales y teoría de determinantes.

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.

  • 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 que $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}$.

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»

Álgebra Superior II: Teorema chino del residuo

Por Leonardo Ignacio Martínez Sandoval

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»