Seminario de Resolución de Problemas: Máximo común divisor

Por Leonardo Ignacio Martínez Sandoval

5 respuestas

Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.

Divisibilidad y máximo común divisor

Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.

Decimos que $a$ divide a $b$ si $b$ es un mútiplo de $a$, es decir, si existe un $r$ tal que $b=ra$. Lo escribimos en símbolos como $a\mid b$. También decimos que $a$ es divisor de $b$.

Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si $a\mid b$ y $b\mid a$, entonces $|a|=|b|$, es decir $a=b$ o $a=-b$.

Si tenemos varios números $a_1,\ldots,a_n$, el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por $\MCD{a_1,\ldots,a_n}$ y $\mcm{a_1,\ldots,a_n}$.

Proposición 2. Si $n$ divide a $a$ y a $b$, entonces divide a cualquier combinación lineal entera $ra+sb$ de ellos. En particular, si $n$ divide a dos términos de la igualdad $a+b=c$, entonces divide al tercero.

Notemos que $a+(b-a)=b$. Por la Proposición 2, un divisor de $a$ y $b$ será divisor de $b-a$, y uno de $b-a$ y de $a$ será divisor de $b$. De aquí sale que $\MCD{a,b}=\MCD{a,b-a}$

Problema. Determina todas las funciones $f:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{Z}^+$ tales que cumplen las siguientes tres propiedades simultáneamente:

  1. $f(a,a)=a$ para todo entero positivo $a$.
  2. $f(a,b)=f(b,a)$ para todo par de enteros positivos $a$ y $b$.
  3. $f(a,b)=f(a,a+b)$ para todo par de enteros positivos $a$ y $b$.

Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de $f(a,b)$ para todos $a$ y $b$ enteros positivos. Intenta probar tu conjetura por inducción fuerte.

Solución. Vamos a mostrar que $f(a,b)=\MCD{a,b}$ para todo par de enteros positivos $a$ y $b$. Vamos a probarlo por inducción sobre la suma $a+b$. Como $a$ y $b$ son enteros positivos, la menor suma que pueden tener es $2$ y en este caso $a+b=2$ implica $a=b=1$. Por la hipótesis 1, tenemos $f(1,1)=1$, que coincide con $\MCD{1,1}$.

Supongamos que el resultado es cierto cuando $a+b=k$ para todo entero $k=1,\ldots,n$ y tomemos $a$ y $b$ enteros de suma $n+1$. Si $a=b$, entonces $$f(a,b)=f(a,a)=a=\MCD{a,a}=\MCD{a,b},$$ como queremos. Si $a\neq b$, por la simetría que nos da la hipótesis 2 podemos suponer $b>a$. Por la hipótesis 3, $$f(a,b)=f(a,a+(b-a))=f(a,b-a).$$ En la expresión de la derecha, tenemos que sus entradas suman $a+(b-a)=b<a+b=n+1$, de modo que podemos aplicar la hipótesis inductiva para obtener que $f(a,b-a)=\MCD{a,b-a}$. Por la discusión antes de este problema, $\MCD{a,b-a}=\MCD{a,b}$. Así, concluimos que $f(a,b)=\MCD{a,b}$, como queríamos.

$\square$

El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.

Proposición 3. Si tenemos otro número $d$ que sea divisor de $a_1,\ldots,a_n$, entonces $$d\mid \MCD{a_1,\ldots,a_n}.$$ Si tenemos otro número $M$ que sea múltiplo de $a_1,\ldots,a_n$, entonces $$\mcm{a_1,\ldots,a_n}\mid M.$$

Problema. Sean $a$ y $b$ enteros positivos. Muestra que $$\MCD{a,b}\mcm{a,b}=ab.$$

Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.

Solución. Para simplificar la notación, tomamos $D=\MCD{a,b}$ y $m=\mcm{a,b}$.

Como $D$ divide a $a$ y $b$, existen enteros $r$ y $s$ tales que $a=rD$ y $b=sD$. Notemos que $rsD=as=br$, así que $rsD$ es un múltiplo de $a$ y $b$, y por la Proposición 3, tenemos que $m\mid rsD$. Multiplicando por $D$ esta divisibilidad, tenemos que $Dm\mid rsD^2=ab$.

Como $ab$ es múltiplo de $a$ y de $b$, por la Proposición $3$ es múltiplo de $m$, digamos $ab=km$. Notemos que de aquí, tenemos $a=k(m/b)$ con $m/b$ entero y $b=k(m/a)$ con $m/a$ entero, de modo que $k$ divide a $a$ y a $b$. Como $D$ es máximo común divisor, por la Proposición 3 tenemos que $k\mid D$. Multiplicando por $m$ esta divisibilidad, tenemos que $km\mid DM$, es decir, $ab\mid Dm$.

Con esto logramos conseguir que $ab\mid Dm$ y $Dm\mid ab$. Por la Proposición $1$, tenemos que $|ab|=|Dm|$, pero como $a$, $b$, $D$, $m$ son positivos, entonces $ab=Dm$.

$\square$

Algoritmo de la división y algoritmo de Euclides

Tomemos $a$ y $b$ enteros. Si intentamos expresar a $a$ como múltiplo de $b$, puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo «pequeño». Esto es lo que dice el algoritmo de la división.

Teorema 1 (Algoritmo de la división). Para enteros $a$ y $b\neq 0$, existen únicos enteros $q$ y $r$ tales que $0\leq r < |b|$ y $a=bq+r$.

Consideremos la igualdad $a=bq+r$ en el algoritmo de la división y apliquemos la Proposición 2. Si $d$ divide a $a$ y $b$, entonces divide a $r$. Si $d$ divide a $r$ y a $b$, entonces divide a $a$. Así, $\MCD{a,b}=\MCD{b,r}$, en donde $b$ y $r$ ahora son números más chicos que $a$ y $b$. De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades
\begin{align*}
a&=bq_1+r_1\\
b&=r_1 q_2 + r_2\\
r_1&= r_2q_3 + r_3\\
&\vdots\\
r_{n-2}&= r_{n-1}q_n + r_n\\
r_{n-1}&= r_nq_{n+1} + 0\\
\end{align*}

de las que obtenemos $$\MCD{a,b}=\MCD{b,r_1}=\ldots=\MCD{r_n,0}=r_n.$$
En las igualdades llegamos a un residuo $0$ pues $b>r_1>r_2>r_3>\ldots\geq 0$ es una sucesión estrictamente decreciente de enteros no negativos.

En particular, obtenemos $$\MCD{a,b}=r_n.$$ A esto se le conoce como el algoritmo de Euclides, que enunciamos en otras palabras a continuación.

Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de $a$ y $b$ aplicando el algoritmo de la división a $a$ y $b$, a $b$ y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es $\MCD{a,b}$.

Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.

Problema. Sean $a\geq b$ enteros. Sean $q_i$ y los $r_i$ los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de $n+1$ vectores en $\mathbb{R}^3$ como sigue:

\begin{align*}
v_1&=(a,1,0)\\
v_2&=(b,0,2)\\
v_{i+2}&=v_{i}-q_iv_{i+1}\quad \text{para $i=1,\ldots,n-1$}
\end{align*}

Sean $r_{-1}=a$ y $r_{0}=b$. Muestra que para $i=1,2,3,\ldots,n+1$ se tiene que $v_i=(x_i,y_i,z_i)$, en donde:

  • $x_i=r_{i-2}$
  • $x_i=ay_i+bz_i$

Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos $i=1,2$ son inmediatos.

Solución. Procedemos por inducción fuerte en el subíndice $i$. Para $i=1,2$, el resultado es cierto pues $x_1=a=r_{-1}$, $x_2=b=r_0$, $a=1\cdot a + 0 \cdot b$ y $b=0 \cdot a + 1\cdot b$. Supongamos el resultado cierto para los índices $1,2,\ldots, k$ para algún $2\leq k\leq n$. Tomemos el índice $k+1$.

Estudiemos primero la entrada $x_{k+1}$. Por definición de la recursión e hipótesis inductiva
\begin{align*}
x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\
&=r_{k-3}-q_{k-1}r_{k-2}\\
&=r_{k-1},
\end{align*}

que es lo que queríamos mostrar para la entrada $x_{k+1}$. Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que
\begin{align*}
x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\
&=ay_{k-1}+bz_{k-1} – q_{k-1} (ay_{k}+bz_{k})\\
&=a(y_{k-1}-q_{k-1}y_k) + b(z_{k-1}-q_{k-1}z_k)\\
&=ay_{k+1}+bz_{k+1}.
\end{align*}

Con esto terminamos la inducción.

$\square$

El problema anterior nos dice que, en particular, $r_n=ay_n+bx_n$. Esta conclusión es muy importante y la enunciamos como teorema.

Teorema 3. El máximo común divisor de enteros $a$ y $b$ se puede escribir como combinación lineal entera de $a$ y $b$, es decir, existen enteros $m$ y $n$ tales que $\MCD{a,b}=am+bn$.

Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.

Problema. Expresa al máximo común divisor de $754$ y $221$ como combinación lineal entera de estos números.

Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones $2,3,4$). En el primer rengón vamos apuntando las $q_i$.

3223
7542219139130
101-25-17
01-37-1758

Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores $v_1$ y $v_2$ del problema, que son $(754,1,0)$ y $(221,0,1)$. Para la tercer columna, nos preguntamos ¿cuántas veces cabe $221$ en $754$? La respuesta es $3$, así que ponemos un $3$ arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.

Para la cuarta columna, nos preguntamos ¿cuántas veces cabe $91$ en $221$? La respuesta es $2$, así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un $0$. La columna anterior nos dice que $13$ es el máximo común divisor, y que la combinación lineal es $$13=754\cdot 5 + 221 \cdot 58.$$

$\square$

Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.

Problema. Muestra que para todo entero $n$ se tiene que la fracción $\frac{41-6n}{9n-61}$ es irreducible.

Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que $41-6n$ y $9n-61$ nunca tienen divisores en común.

Solución. Notemos que $41-6n$ y $9n-61$ tienen una combinación lineal que da $1$. En efecto, $$3\cdot (41-6n) + 2\cdot (9n-61) = 123-18n+18n-122=1.$$

Cualquier entero $d$ que divida a $41-6n$ y a $9n-61$ tiene entonces que dividir a $1$, lo cual muestra que $\MCD{41-6n,9n-61}=1$, y por lo tanto la fracción siempre es irreducible.

$\square$

Problema. Se tiene un número irracional $\alpha$ para el cual $\alpha^{91}$ y $\alpha^{119}$ son números racionales. Muestra que $\alpha^{14}$ es un número racional.

Sugerencia pre-solución. Encuentra el máximo común divisor de $91$ y $119$. Recuerda que las potencias de racionales son racionales, y productos de racionales también.

Solución. Como $91=7\cdot 13$ y $119=7\cdot 13$, tenemos que $\MCD{91,119}=7$. De esta forma, existen enteros $m$ y $n$ tales que $7=91m+119n$, de donde $14=91 \cdot (2m)+119 \cdot(2n)$.

Sabemos que $\alpha^{91}$ es racional, así que $(\alpha^{91})^{2m}$ también. Análogamente, $(\alpha^{119})^{2n}$ es racional. De esta forma, el número $$\alpha^{14}=(\alpha^{91})^{2m}\cdot (\alpha^{119})^{2n}$$ también lo es.

$\square$

Más ejemplos

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

El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo $n$.

Álgebra Superior II: Ejercicios de los teoremas de Fermat y de Wilson

Por Claudia Silva

3 respuestas

Introducción

Primero, un ejercicio más de congruencias:

Un ejercicio de congruencias

Un ejercicio utilizando el teorema de Fermat:

Ejercicio utilizando el teorema de Fermat

Ejercicio sencillo utilizando el Teorema de Wilson:

17!=1 (mod 19)

Otro ejercicio utilizando el Teorema de Wilson:

Si p primo, (p-1)! = -1 (mod p)

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Álgebra Lineal I: Problemas de transformaciones lineales, vectores independientes y forma matricial

Por Ayax Calderón

2 respuestas

Introducción

En esta entrada resolveremos algunos problemas acerca de transformaciones lineales, de su efecto en conjuntos generadores, independientes y bases, y de la forma matricial de transformaciones lineales.

Problemas resueltos

El siguiente problema es para repasar qué le hace una transformación lineal a una combinación lineal, y cómo podemos usar este hecho para saber cuánto vale una transformación lineal evaluada en un vector, sabiendo qué le hace a los elementos de una base.

Problema 1. Sean $$v_1=(1,0,0), v_2=(1,1,0), v_3=(1,1,1),$$

y sea $T:\mathbb{R}^3\to \mathbb{R}^2$ una transformación lineal tal que \begin{align*}T(v_1)&=(3,2)\\ T(v_2)&=(-1,2)\\ T(v_3)&=(0,1).\end{align*}

Calcula el valor de $T(5,3,1)$.

Solución. Primero observemos que ${(1,0,0), (1,1,0), (1,1,1)}$ es una base de $\mathbb{R}^3$, entonces existen $a,b,c\in \mathbb{R}$ tales que $$(5,3,1)=a(1,0,0)+b(1,1,0)+c(1,1,1).$$
Si logramos expresar a $(5,3,1)$ de esta forma, después podremos usar que $T$ es lineal para encontrar el valor que queremos. Encontrar los valores de $a,b,c$ que satisfacen la ecuación anterior lo podemos ver como el sistema de ecuaciones $$\begin{pmatrix}
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1\end{pmatrix} \begin{pmatrix}
a\\
b\\
c\end{pmatrix} = \begin{pmatrix}
5\\
3\\
1\end{pmatrix}.$$

Para resolver este sistema, consideramos la matriz extendida del sistema y la reducimos
\begin{align*} & \begin{pmatrix}
1 & 1 & 1 & 5\\
0 & 1 & 1 & 3\\
0 & 0 & 1 & 1\end{pmatrix} \\ \to &\begin{pmatrix}
1 & 0 & 0 & 2\\
0 & 1 & 1 & 3\\
0 & 0 & 1 & 1\end{pmatrix} \\ \to & \begin{pmatrix}
1 & 0 & 0 & 2\\
0 & 1 & 0 & 2\\
0 & 0 & 1 & 1\end{pmatrix}\end{align*}

Así, $a=2, b=2, c=1$.

Finalmente, usando que $T$ es transformación lineal,

\begin{align*}
T(5,3,1)&=T(2(1,0,0)+2(1,1,0)+(1,1,1))\\
&=2T(1,0,0)+2T(1,1,0)+T(1,1,1)\\
&=2(3,2)+2(-1,2)+(0,1)\\
&=(6,4)+(-2,4)+(0,1)\\
&=(4,9).
\end{align*}

$\triangle$

Veamos ahora un problema para practicar encontrar la matriz correspondiente a una base.

Problema 2. Sea $\mathbb{R}_n[x]$ el espacio de los polinomios de grado a lo más $n$ con coeficientes reales.

Considera la transformación lineal $T:\mathbb{R}_3[x]\to \mathbb{R}_2[x]$ dada por $T(p(x))=p'(x)$, es decir, aquella que manda a cada polinomio a su derivada.

Sean $\beta=(1,x,x^2,x^3)$ y $\gamma=(1,x,x^2)$ las bases canónicas ordenadas de $\mathbb{R}_3[x]$ y $\mathbb{R}_2[x]$, respectivamente. Encuentra la representación matricial de la transformación $T$.

Solución. Primero le aplicamos $T$ a cada uno de los elementos de $\beta$, que simplemente consiste en derivarlos. Obtenemos que:

$T(1)=0=0\cdot 1 + 0\cdot x + 0\cdot x^2$
$T(x)=1=1\cdot 1 + 0\cdot x + 0\cdot x^2$
$T(x^2)=2x=0\cdot 1 + 2\cdot x + 0\cdot x^2$
$T(x^3)=3x^2=0\cdot 1 + 0\cdot x + 3\cdot x^2$

Para construir la matriz de cambio de base, lo que tenemos que hacer es formar una matriz con cuatro columnas (una por cada elemento de la base $\beta$). La primera columna debe tener las coordenadas de $T(1)$ en la base $\gamma$. La segunda columna, las coordenadas de $T(x)$ en la base $\gamma$. Y así sucesivamente. Continuando de este modo, llegamos a que

$$\begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 3\end{pmatrix}$$
es la forma matricial de $T$ con respecto a las bases canónicas.

$\triangle$

Finalmente, el siguiente problema combina muchas de las ideas relacionadas con la forma matricial de una transformación. Se recomienda fuertemente que lo leas con detenimiento. Es un ejemplo en el que encontramos tres formas matriciales: las de dos transformaciones y las de su composición. Después, se verifica que la de la composición en efecto es el producto de las correspondientes a las dos transformaciones.

Problema 3. Considera las transformaciones

\begin{align*}
T:\mathbb{R}^3&\to \mathbb{R}_2[x]\quad\text{y}\\
S:\mathbb{R}_2[x] &\to M_2(\mathbb{R})
\end{align*}

dadas por

\begin{align*}
T(a,b,c)&=a+2bx+3cx^2\quad \text{y}\\
S(a+bx+cx^2)&=\begin{pmatrix}
a & a+b\\
a-c & b\end{pmatrix}.
\end{align*}

Consideramos la base ordenada $B_1=(1,x,x^2)$ de $\mathbb{R}_2[x]$, la base canónica ordenada $B_2$ de $\mathbb{R}^3$ y la base ordenada $B_3=(E_{11}, E_{12}, E_{21}, E_{22})$ de $M_2(\mathbb{R})$.

  1. Verifica que $T$ y $S$ son transformaciones lineales.
  2. Escribe las matrices asociadas a $T$ y $S$ con respecto a las bases dadas.
  3. Encuentra la matriz asociada a la composición $S\circ T$ con respecto a las bases anteriores usando el resultado que dice que es el producto de las dos matrices que ya encontraste.
  4. Calcula explícitamente $S\circ T$, después encuentra directamente su matriz asociada con respecto a las bases anteriores y verifica que el resultado obtenido aquí es el mismo que en el inciso anterior.

Solucion. 1. Sea $u\in \mathbb{R}$ y sean $(a,b,c), (a’,b’,c’)\in \mathbb{R}^3$.
Entonces

\begin{align*}
T(u&(a,b,c)+(a’,b’,c’))\\
&=T(au+a’,bu+b’,cu+c’)\\
&=(au+a’)+2(bu+b’)x+3(cu+c’)x^2\\
&=u(a+2bx+3cx^2)+(a’+2b’x+3c’x^2)\\
&=uT(a,b,c)+T(a’,b’,c’).
\end{align*}

Así, $T$ es lineal.

Ahora, sea $u\in \mathbb{R}$ y sean $a+bx+cx^2, a’+b’x+c’x^2\in \mathbb{R}_2[x]$.
Entonces

\begin{align*}
S(u&(a+bx+cx^2)+(a’+b’x+c’x^2))\\
&=S(ua+a’+(ub+b’)x+(uc+c’)x^2)\\
&=\begin{pmatrix}
ua+a’ & (ua+a’)+(ub+b’)\\
ua+a’-(uc+c’) & ub+b’\end{pmatrix}\\
&=u\begin{pmatrix}
a & a+b\\
a-c & b\end{pmatrix} + \begin{pmatrix}
a’ & a’+b’\\
a’-c’ & b’\end{pmatrix}\\
&=uS(a+bx+cx^2)+S(a’+b’x+c’x^2).
\end{align*}

Así, $S$ es lineal.

2. Empezamos calculando la matriz $\Mat_{B_1,B_2}(T)$ de $T$ con respecto a $B_1$ y $B_2$. La base $B_2$ es la base canónica ordenada de $\mathbb{R}^3$, es decir, $B_2=(e_1,e_2,e_3)$. Aplicando $T$ en cada uno de estos vectores,

\begin{align*}
T(e_1)&=T(1,0,0)=1=1\cdot 1 + 0\cdot x + 0\cdot x^2,\\
T(e_2)&=T(0,1,0)=2x= 0\cdot 1 + 2\cdot x + 0 \cdot x^2,\\
T(e_3)&=T(0,0,1)=3x^2= 0\cdot 1 + 0\cdot x + 3 \cdot x^2.
\end{align*}

Así, $$\Mat_{B_1,B_2}(T)=\begin{pmatrix}
1 & 0 & 0\\
0 & 2 & 0\\
0& 0 & 3\end{pmatrix}.$$

De manera análoga, calculamos

\begin{align*}
S(1)&=\begin{pmatrix}
1 & 1\\
1 & 0\end{pmatrix} \\
&= 1 \cdot E_{11} + 1 \cdot E_{12} + 1 \cdot E_{21} + 0\cdot E_{22},\\
S(x)&=\begin{pmatrix}
0 & 1\\
0 & 1\end{pmatrix} \\
&= 0 \cdot E_{11} + 1 \cdot E_{12} + 0 \cdot E_{21} + 1\cdot E_{22},\\
S(x^2)&=\begin{pmatrix}
0 & 0\\
-1 & 0\end{pmatrix} \\
&= 0 \cdot E_{11} + 0 \cdot E_{12} + (-1) \cdot E_{21} + 0\cdot E_{22}.\end{align*}

Por lo tanto $$\Mat_{B_3,B_1}(S)=\begin{pmatrix}
1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & -1\\
0 & 1 & 0\end{pmatrix}.$$

3. Usando el resultado de que la forma matricial de una composición de transformaciones es el producto de sus formas matriciales, $$\Mat_{B_3,B_2}(S\circ T)=\Mat_{B_3,B_1}(S)\cdot \Mat_{B_1,B_2}(T).$$

Así, tenemos que:
\begin{align*}
\Mat_{B_3,B_2}(S\circ T)&=\begin{pmatrix}
1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & -1\\
0 & 1 & 0\end{pmatrix} \begin{pmatrix}
1 & 0 & 0\\
0 & 2 & 0\\
0 & 0 & 3\end{pmatrix} \\
&= \begin{pmatrix}
1 & 0 & 0\\ 1 & 2 & 0\\ 1 & 0 & -3\\
0 & 2 & 0\end{pmatrix}.\end{align*}

4. Calculamos la composición directamente como sigue:

\begin{align*}
(S\circ T)(a,b,c)&=S(T(a,b,c))\\
&= S(a+2bx+3cx^2)\\
&=\begin{pmatrix}
a & a+2b\\
a-3c & 2b\end{pmatrix}.
\end{align*}

Para encontrar la matriz que representa a esta transformación lineal, evaluamos en cada elemento de $B_2$.

\begin{align*}
(S\circ T)(e_1)&=\begin{pmatrix}
1 & 1\\
1 & 0\end{pmatrix}\\
& = 1\cdot E_{11} + 1 \cdot E_{12} + 1 \cdot E_{21} + 0 \cdot E_{22},\\
(S\circ T)(e_2)&=\begin{pmatrix}
0 & 2\\
0 & 2\end{pmatrix} \\
&= 0\cdot E_{11} + 2 \cdot E_{12} + 0 \cdot E_{21} + 2 \cdot E_{22},\\
(S\circ T)(e_2)&=\begin{pmatrix}
0 & 0\\
-3 & 0\end{pmatrix} \\
&= 0 \cdot E_{11} + 0 \cdot E_{12} +(-3) \cdot E_{21} + 0 \cdot E_{22}.
\end{align*}

Así, la matriz asociada a $S\circ T$ con las bases indicadas es $$\Mat_{B_3,B_2}(S\circ T)= \begin{pmatrix}
1 & 0 & 0\\ 1 & 2 & 0\\ 1 & 0 & -3\\
0 & 2 & 0\end{pmatrix}.$$

Esto es, por supuesto, justo lo que se obtuvo en el inciso 3.

$\triangle$

Entradas relacionadas

Agradecimientos

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

Álgebra Superior II: Ecuaciones en congruencias

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo 1. ¿Cuáles son las soluciones enteras a la ecuación $x\equiv 3 \pmod 6$?

Solución. Un número $x$ satisface la ecuación si y sólo si $6$ divide a $x-3$, lo cual sucede si y sólo si $x$ es de la forma $x=6r+3$, donde $r$ es un número entero. Así, el conjunto de soluciones es de la forma $$6\mathbb{Z}+3:= \{6r+3: r\in \mathbb{Z}\}.$$ Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del $3$ módulo $6$, es decir, $[3]_6$.

$\triangle$

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de $\mathbb{Z}_n$. Si se quiere encontrar a todos los enteros (en $\mathbb{Z}$) que sean solución, basta recordar este ejemplo para expresar a las soluciones en $\mathbb{Z}_n$ como conjuntos de soluciones en $\mathbb{Z}$.

Ejemplo 2. ¿Cuáles son las soluciones enteras a la ecuación $2x+1\equiv 0 \pmod 7$?

Solución. Trabajemos módulo $7$. Restando $1$ de ambos lados obtenemos $$2x\equiv -1\equiv 6 \pmod 7.$$ Multiplicando por $4$ de ambos lados tenemos que $$8x\equiv 24\equiv 3\pmod 7.$$ Como $8x\equiv x \pmod 7$, tenemos que $x\equiv 3 \pmod 7$ es la solución.

$\triangle$

En el ejemplo anterior encontramos las soluciones módulo $7$. Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en $\mathbb{Z}$ son los números de la forma $7r+3$ con $r$ entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma $$ax\equiv b\pmod n.$$ Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo $n$ tiene. Hay un caso fácil de estudiar, que es cuando $a$ y $n$ son primos relativos.

Proposición 1. Sean $a,b$ enteros y $n$ un entero positivo tales que $\text{MCD}(a,n)=1$. Entonces la ecuación $$ax\equiv b \pmod n$$ tiene una única solución $x$ módulo $n$.

Demostración. Como $a$ y $n$ son primos relativos, $a$ tiene un inverso multiplicativo módulo $n$, digamos $a^{-1}$. Afirmamos que $x=a^{-1}b$ es solución. En efecto, $a(a^{-1}b)\equiv 1\cdot b\equiv b \pmod n$.

Ahora, afirmamos que la solución es única. Supongamos que $x$ y $y$ son solución. Tendríamos entonces que $$ax\equiv b \equiv ay \pmod n.$$ Multiplicando ambos extremos de esta ecuación por $a^{-1}$, tenemos que $$x\equiv a^{-1}ax\equiv a^{-1}a y \equiv y \pmod n.$$

$\square$

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que $x$ es solución de $ax\equiv b\pmod n$ si y sólo si $n$ divide a $ax-b$, lo cual sucede si y sólo si existe un entero $y$ tal que $ax-b=ny$. Reordenando, tenemos que $ax-ny=b$. En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a $b$ como combinación lineal entera de $a$ y $n$, lo cual sucede si y sólo si $$b\in a\mathbb{Z} + n \mathbb{Z}=\text{MCD}(a,n)\mathbb{Z},$$ es decir, si y sólo si $b$ es múltiplo del máximo común divisor de $a$ y $n$. Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. 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 $\text{MCD}(a,n)$ divide a $b$.

Ahora, queremos entender cuántas soluciones diferentes hay módulo $n$.

Ejemplo. Encuentra todas las soluciones a la ecuación $4x\equiv 1 \pmod 8$ y a la ecuación $4x\equiv 0 \pmod 8$.

Solución. Tenemos que $\text{MCD}(4,8)=4$ y que $4$ no divide a $1$, así que la primer ecuación no tiene solución. Tenemos que $4$ sí divide a $0$, así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por $4$ cada uno de los elementos $0,2,4,6$ obtenemos respectivamente $0,8,16,24$, que son todos múltiplos de $8$, así que estos elementos de $\mathbb{Z}_8$ son solución. Al multiplicar $4$ por $1,3,5,7$ obtenemos $4,12,20,28$, que módulo $8$ son $4,4,4,4$, así que ninguno de estos números son solución. Así, las soluciones son $x\equiv 0,2,4,6\pmod 8$.

$\triangle$

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros $n$ tales que $n\equiv 0\pmod 2$. En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean $a,b$ enteros y $n$ un entero positivo tales que $M=\text{MCD}(a,n)$ divide a $b$. Sean $a’=a/M$, $b’=b/M$ y $n’=n/M$ (con $a’$, $b’$, $n’$ enteros). El entero $x$ es solución a la ecuación en congruencias $ax\equiv b \pmod n$ si y sólo si es solución a la ecuación en congruencias $a’x\equiv b’\pmod {n’}$.

Demostración. Tenemos que $x$ es solución a $ax\equiv b \pmod n$ si y sólo si existe una combinación lineal entera $ax-ny=b$. Al dividir entre $M\neq 0$, esto sucede si y sólo si $a’x-n’y=b’$, lo cual sucede si y sólo si $x$ es solución a la ecuación en congruencias $a’x\equiv b’\pmod {n’}$.

$\square$

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

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

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente $a’x\equiv b’\pmod {n’}$, en donde $a’=a/M$ y $b’=b/M$. En esta ecuación, $a’$ y $n’$ son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo $n’$.

$\square$

Como empezamos con una ecuación módulo $n$, quizás queremos saber cuántas soluciones tiene módulo $n$, y no módulo $n’$. De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene $M$ soluciones módulo $n$.

Ejercicio. Resuelve la ecuación lineal en congruencias $$12x\equiv 18 \pmod {30}.$$

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de $12$ y $30$.

Solución. El máximo común divisor de $12$ y $30$ es $6$, que sí divide a $18$. Entonces sí hay soluciones, y habrá $6$ soluciones módulo $30$. Para encontrar la ecuación reducida equivalente, dividimos entre $6$ para obtener $$2x\equiv 3 \pmod 5.$$

El inverso de $2$ módulo $5$ es $3$. Multiplicando en ambos lados por $3$ obtenemos la solución $$x\equiv 9 \equiv 4 \pmod 5.$$

Para recuperar las soluciones módulo $30$, a cada una de estas soluciones le sumamos $30/6=5$ repetidamente para obtener las soluciones $x\equiv 4, 9, 14, 19, 24, 29 \pmod {30}$.

$\triangle$

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

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. Sea $a$ un entero y $n$ un entero positivo. Sea $M=\text{MCD}(a,n)$ y sean $a’=a/M$ y $n’=n/M$. Muestra que $\text{MCD}(a’,n’)=1$.
  2. Demuestra el corolario al Teorema 1.
  3. Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
  4. Diseña una ecuación lineal módulo $60$ que tenga exactamente $15$ soluciones módulo $60$.
  5. Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

\begin{align*}
x&\equiv -1 \pmod{77}\\
x&\equiv -1 \pmod{55}\\
\end{align*}

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: Bases numéricas y dígitos

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En las entradas anteriores de teoría de números hemos hablado acerca de divisibilidad, de aritmética modular y de factorización única en primos. En esta entrada vamos a hablar de propiedades que podemos deducir de ciertos números a partir de su dígitos.

Usualmente escribimos a los números en base $10$, usando los dígitos de $1$ a $9$. En realidad, esto es relativamente arbitrario. Podemos usar bases distintas de $10$ para expresar cualquier número de manera (casi) única. Conocer la expresión de un número en cierta base nos permite deducir propiedades algebraicas y de divisibilidad que nos ayuden a resolver problemas.

Expresión en una base arbitraria

Para cualquier base entera $b\geq 2$ que elijamos, cualquier número real se puede expresar de manera (casi) única en base $b$. La afirmación precisa es el siguiente resultado.

Teorema. Sea $r$ un número real y $b\geq 2$ un entero. Entonces, existen únicos enteros $A_0,A_1,\ldots, a_1,a_2,\ldots$ en $\{0,1,\ldots,b-1\}$ tales que $$r=\sum_{i=0}^\infty A_i b^i + \sum_{i=0}^{\infty} a_i 10^{-i}$$ y $a_i\neq b-1$ para una infinidad de $i$’s.

Para estos $a_i$ y $A_i$ escribimos $$r=(\ldots A_2A_1A_0.a_1a_2\ldots)_b,$$ en donde el subíndice indica la base que se está usando.

La condición de $a_i\neq b-1$ para una infinidad de $i’s$ está ahí para garantizar que la expresión sea única pues, por ejemplo, $1=\sum_{i=0}^\infty 9\cdot 10^{-i}=0.9999\ldots$, pero esa condición descarta la expresión de la derecha.

Si $b=2$, a esta expresión le llamamos la expresión binaria de $r$.

Ejemplo. La expresión binaria de $4/3$ es $(1.010101\ldots)_2$. ¿Por qué?

Multiplicar y dividir entre $10$ cuando tenemos números en base $10$ es sencillo: simplemente recorremos el punto decimal. Lo mismo sucede en cualquier base $b$.

Proposición. Cuando tenemos un número en base $b$ y multiplicamos por $b$, el «punto decimal» se recorre a la derecha. Cuando dividimos entre $b$ se recorre a la izquierda.

Problema. Determina si existe un real $x$ tal que $$\floor{x}+\floor{2x}+\floor{4x}+\floor{8x}= 2222.$$

Sugerencia pre-solución. Trabaja hacia atrás suponiendo que la ecuación sí tiene una solución para determinar cómo tiene que verse $x$. Usa la expresión binaria de $x$.

Solución. Tenemos que $r\geq \floor{r}$ para todo real $r$, de modo que si dicho número $x$ existe, se cumple $$17x\geq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} = 2222.$$ De aquí, $x\geq 2222/17 = 130.705\ldots\geq 130$. También, $r\leq \floor{r}+1$, de modo que si $x$ existe necesitamos $$17x\leq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} + 4 = 2226.$$

De aquí, $x\leq 2226/17 =130.94\leq 131$.

Esto nos dice que $x$ es un real entre $130$ y $131$. Escribámoslo como $130$ más una parte fraccional en base $2$, es decir, de la forma $x=130+(abcde\ldots)_2$. Multiplicar por $2$ simplemente recorre el punto decimal en base $2$ un lugar hacia la derecha, de modo que
\begin{align*}
2x&=260+(a.bcde\ldots)_2\\
4x&=520+(ab.cde\ldots)_2\\
8x&=1040+(abc.de\ldots)_2,
\end{align*} y por lo tanto
\begin{align*}
\floor{x}&=130\\
\floor{2x}&=260+(a)_2=260+a\\
\floor{4x}&=520+(ab)_2=520+2a+b\\
\floor{8x}&=1040+(abc)_2=1040+4a+2b+c.
\end{align*}

Concluimos entonces que la suma buscada es igual a $1950+7a+3b+c$. Si existe el número que queremos, la ecuación $$1950+7a+3b+c=2222$$ debe tener una solución con $a$, $b$ y $c$ iguales a $0$ o a $1$. Pero esto es imposible, pues incluso aunque los tres sean iguales a $1$, tenemos a lo más $1950+11=1961$. De esta forma, no existe la $x$ que buscamos.

$\square$

Bases y números racionales

Una sucesión infinita $\{a_1,a_2,\ldots,\}$ es preperiódica si existen enteros positivos $n$ y $d$ tales que $a_m=a_{m+d}$ para todo entero $m\geq n$. A $d$ se le llama un periodo de la sucesión, y decimos que $\{a_1,a_2,\ldots\}$ es periódica a partir de $a_n$.

Teorema. Sea $r$ un número real. Las siguientes tres afirmaciones son equivalentes:

  • $r$ es racional.
  • Para toda base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.
  • Para alguna base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.

Problema. Considera el número en binario $$r=(0.a_1a_2a_3\ldots)_2$$ en donde $a_i=0$ si $i$ es primo y $a_i=1$ si no. Determina si $r$ es un número racional o irracional.

Sugerencia pre-solución. Procede por contradicción, suponiendo que $r$ es racional.

Solución. Si $r$ fuera racional, la sucesión $\{a_1,a_2,\ldots\}$ sería preperiódica, de modo que existirían $n$ y $d$ tales que $a_{m+d}=a_m$ para todo $m\geq n$. Consideremos el bloque de $d$ dígitos $(a_na_{n+1}\ldots a_{n+d-1})_2$. Como el periodo de la sucesión es $d$, a partir de $a_n$ este bloque de dígitos se repite.

Los números

\begin{align*}
M&=n(2d+1)!+2,\\
M+1&=n(2d+1)!+3,\\
&\vdots\\
M+(2d-1)&=n(2d+1)!+(2d+1)
\end{align*}

son $2d$ números consecutivos mayores a $n$ y tales que ninguno de ellos es primo, pues el primero es divisible entre $2$, el segundo entre $3$, …, y el último entre $2d+1$. Esto muestra que el bloque de $d$ dígitos debe consistir de puros $1$’s, pues uno de los bloques del ciclo queda contenido en el bloque de $2d$ dígitos $(a_Ma_{M+1}\ldots a_{M+2d-1})_2$. Así, a partir de $a_n$ todos los dígitos son iguales a $1$.

Pero esto es imposible, pues quiere decir que todos los enteros mayores o iguales a $n$ no son primos. Esto contradice que hay una infinidad de números primos.

$\square$

Criterios de divisibilidad

Si sabemos cómo es la expresión de un número en una base, entonces a veces podemos decir cosas acerca de su divisibilidad o residuo al dividirse entre algunos enteros relacionados con la base. Cuando estamos trabajando módulo $10$ tenemos el siguiente resultado.

Proposición (criterios de divisibilidad base 10). Sea $n$ un entero positivo. En base $10$,

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $10^k$, y por lo tanto también módulo $2^k$ y módulo $5^k$.
  • $n$ es congruente con la suma de sus dígitos módulo $9$, y por lo tanto también módulo $3$.
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $10^{j}+1$.

Demostrar estos criterios es sencillo. Por ejemplo, un número $(A_nA_{n-1}\ldots A_0)_{10}$ en base $10$ es igual a $$10^{n}A_n+10^{n-1}A_{n-1}+\ldots+10 A_1+ A_0.$$ Trabajando módulo $9$, todos los $10$ son $1$, así que $$n=10^nA_n+\ldots+A_0\equiv A_n + A_{n-1}+\ldots+A_0.$$

Como ejemplo del último criterio, considera el siguiente problema:

Problema. ¿Cuál es el residuo que queda al dividir $n=1512513514515$ entre $13$?

Sugerencia pre-solución. Usa el tercer criterio de divisibilidad base $10$ para $j=3$. Factoriza $1001$.

Solución. Vamos a estudiar al número módulo $1001$. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda $$515, 514, 513, 512, 1$$ y hacemos la suma alternada $$515-514+513-512+1=3.$$ Por el tercer criterio de divisibilidad, tenemos que $n\equiv 3 \pmod{1001}$. Notemos que $1001=7\cdot 11 \cdot 13$, de modo que $n\equiv 3 \pmod{13}$. Así, el residuo al dividir $n$ entre $13$ es $3$.

$\square$

En general, tenemos lo siguiente.

Proposición (criterios de divisibilidad base $b$). Sea $n$ un entero positivo. En base $b$:

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $b^k$, y por lo tanto también módulo $d^k$ para cualquier divisor $d$ de $b$.
  • $n$ es congruente con la suma de sus dígitos módulo $b-1$ (y por lo tanto también módulo cualquier divisor de $b-1$)
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $b^{j}+1$.

Problema. Considera los números del $1$ al $500$ (inclusive). ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en base $3$? ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en binario?

Sugerencia pre-solución. Haz casos pequeños para encontrar un patrón que te diga cuántos números del $1$ al $n$ tienen una cantidad impar de $1$’s en su expresión en base $2$ y $3$. Para demostrar el resultado para base $3$, usa criterios de divisibilidad generalizados. Para base $2$ usa paridad y aprovecha la simetría.

Solución. Un número en base $3$ es congruente con la suma de sus dígitos módulo $2$. En base $3$ el único dígito impar es el $1$. Así, un número en base $3$ es congruente a su cantidad de dígitos $1$ módulo $2$. De esta forma, $n$ tiene una cantidad impar de $1$’s si y sólo si es impar. Por lo tanto, hay $250$ números entre $1$ y $500$ que tienen una cantidad impar de $1$’s en su expresión en base $3$.

En base $1$ el patrón no es tan claro. Los primeros números son $1$, $10$, $11$, $100$, $101$, $110$, $111$. A veces cuando se cambia de cantidad de dígitos se cambia la paridad de $1$’s (como de $11$ a $100$) y a veces no (como de $111$ a $1000$). Haremos entonces un argumento de emparejamiento.

Notemos que cualquier número par $2n$ termina en $0$ en binario y que $2n+1$ tiene la misma expansión salvo el último dígito, que ahora es $1$.Así, a los números del $2$ al $499$ los podemos agrupar en parejas en donde en cada pareja los números tienen distinta paridad de $1$’s. De esta forma, aquí hay $498/2=249$ números con una cantidad impar de $1$’s. El $1$ tiene una cantidad impar de $1$’s. El $500$ en binario es $(111110100)_2$, que tiene una cantidad par de $1$’s. Así, hay $250$ números entre $1$ y $500$ con una cantidad impar de $1$’s en binario.

$\square$

Más ejemplos

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