Archivo de la etiqueta: euclides

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.

El procedimiento del algoritmo de Euclides

Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$

Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.

Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de $3456$ y $6524$.

Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.

$\triangle$

Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$

$\triangle$

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$

Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.

Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.

Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.

Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.

$\square$

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla

\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}

con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla

\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}

con $0\leq r_j < r_{j-1}.$

Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.

Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidamente la proposición tenemos que:

$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$

La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.

$\square$

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.

$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.

$6524$$1$$0$
$3456$$0$$1$
$3068$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:

$6524$$1$$0$
$3456$$0$$1$
$3068$$\mathbf{1}$$\mathbf{-1}$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$\mathbf{-1}$$\mathbf{2}$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$\mathbf{8}$$\mathbf{-15}$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$8$$-15$
$36$$-9$$17$
$28$$89$$-168$
$8$$-98$$185$
$4$$383$$-723$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:

$$4=383 \cdot 6524 – 723 \cdot 3456.$$

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.

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. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. $15$ y $35$
    2. $18$ y $92$
    3. $201$ y $153$
    4. $328$ y $528$
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    \begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}.
    1. Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$.
    2. Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

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»

Geometría Analítica I: Las ideas de Euclides y Descartes

Por Elsa Fernanda Torres Feria

Deja un comentario

Introducción

En la primer parte del curso desarrollaremos los formalismos de conceptos geométricos de los cuales ya tenemos alguna noción como puntos, rectas, el espacio vectorial $\mathbb{R}^2$, ángulos, distancias, entre otras. Es probable que ya tengas muchas de estas nociones previas, y que hayas trabajado con ellas incluso desde el punto de vista analítico. Sin embargo, es importante ir siguiendo las ideas poco a poco pues, además de aprender a hacer las operaciones necesarias, también hay que desarrollar la intuición matemática y geométrica detrás de las cuentas. Así mismo, será importante darse cuenta del orden en el que vamos construyendo los objetos, pues en muchas ocasiones no sólo calcularemos sino que demostraremos y para ello es fundamental basarse únicamente en cosas que ya se hayan probado antes.

En esta entrada en particular, hablaremos de dos formas en las que se ha formalizado a la geometría: mediante una construcción sintética propuesta por los griegos, y mediante una construcción analítica desarrollada por Descartes. La presentación que hacemos de estos temas es más moderna que como fueron planteados originalmente.

Geometría griega

Antes de que la geometría fuera formalizada, en sus inicios era mucho más una herramienta. Estaba conformada por reglas comúnmente usadas para cosas de la vida cotidiana como medir terrenos, construir casas y ciudades, y navegar.

La formalización de este conocimiento se dio por primera vez en Elementos, un texto escrito en el siglo III a.C. por Euclides de Alejandría; durante este proceso, Euclides se percató de que todo razonamiento riguroso debe tener bases previamente establecidas que bien pueden haberse demostrado con anterioridad o que son válidas sin necesidad de demostración. Esta última opción hace referencia a principios básicos que están dados y son incontrovertibles, de tal manera que se puede construir sobre ellos el resto de la teoría.

Para formalizar una teoría, necesitamos objetos y principios básicos. En el caso de la geometría euclideana, los objetos son las nociones intuitivas que tenemos: puntos, rectas, planos, ángulos, etc. Los principios básicos, que se asumen como ciertos desde el inicio se les conoce como los cinco postulados de Euclides:

  1. Por cualesquiera dos puntos, se puede trazar el segmento de recta que los une.
  2. Dado un punto y una distancia, se puede trazar el círculo con centro en el punto y cuyo radio es la distancia.
  3. Un segmento de recta se puede extender en ambas direcciones indefinidamente.
  4. Todos los ángulos rectos son iguales.
  5. Dadas dos rectas y una tercera que las corta, si los ángulos internos de algún lado suman menos de dos ángulos rectos (180°), entonces las dos rectas se cortan y lo hacen de ese lado.

Este último postulado resulta tener dos versiones que son equivalentes y que enunciamos a continuación:

5.a. Dada una línea recta y un punto fuera de ella, existe una única recta que pasa por el punto y que es paralela a la línea.

5.b. Los ángulos interiores de un triángulo suman dos ángulos rectos.

El quinto postulado resultó ser muy controvertido y en el transcurso de la historia muchos geómetras intentaron mostrar que se desprendía de las definiciones y de los primeros cuatro. Pero esto resultó no ser cierto. Se descubrió que al tomar distintas negaciones del quinto postulado se podían obtener distintas geometrías, tan válidas y tan ricas como la geometría euclideana misma. Esto no lo trataremos en este curso, pero si te interesa conocer más, puedes investigar acerca de la geometría proyectiva o hiperbólica.

Del plano euclideano al plano cartesiano y viceversa

Continuando con la formalización de la geometría, el siguiente paso en este camino lo dio Descartes en su publicación Géométrie al introducir el álgebra en la solución de problemas de índole geométrica. Este camino inicia al buscar la forma de representar puntos en el plano por parejas de números. Para esto partimos del plano euclidiano que está bien definido por los cinco axiomas descritos por Euclides. Pensaremos que este plano consiste de puntos y que se extiende indefinidamente. Pensaremos también que en este plano los objetos que se mencionan en los postulados tienen sentido (punto, distancia, etc.). Llamaremos a este plano $\mathbb{E}^2$, donde el exponente en este caso hace referencia a la dimensión.

Notemos ahora que los puntos de una recta $l_1$ contenida en el plano ($l_1 \in \mathbb{E}^2$) representan a los números reales ($\mathbb{R}$) y que se vale lo contrario también (los reales pueden ser representados por una recta dentro de $\mathbb{E}^2$). Para ello, escogemos un punto $ O \in l_1$ al que denotaremos como origen y le asignaremos el valor real cero. Para que sea tangible la representación de los reales con esta recta, designamos que del lado derecho de $O$ se tienen los números positivos de acuerdo con su distancia al origen y del lado izquierdo los negativos. Así, a cada número real $x$ se le asocia un punto $P \in l_1$ (y a cada punto en $l_1$ le corresponde un número real).

El siguiente paso consiste en construir otra recta, digamos $l_2$, que también pase por $O$ y algún otro punto $Q$ (nótese que $l_1$ y $l_2$ fueron construidas utilizando los postulados 1 y 3 de Euclides). Orientemos a $l_2$ de la misma manera que a $l_1$ para que sus puntos representen a los números reales. Entonces, se tiene la correspondencia biunívoca entre puntos en $ \mathbb{E}^2$ y parejas de números reales gracias al postulado 5.a:

  • De punto en el plano a pareja de números: Existe una única recta $l_1’$ que pasa por $P$ y es paralela a $l_1$; análogamente existe una única recta $l_2’$ que pasa por $P$ y es paralela a $l_2$. Las intersecciones de las rectas $l_1 \cap l_2’$ y $l_2 \cap l_1’$ determinan los puntos $p_1 \in l_1$ y $q_1 \in l_2$ que definen dos números reales $x$ y $y$; esto es, una pareja ordenada $(x,y)$.
  • De pareja de números a punto en el plano: Para esta correspondencia se hace la construcción inversa, dada una pareja de números $(x,y)$, consideremos a $p_1 \in l_1$ como el punto sobre $l_1$ que se encuentra a distancia $x$ del origen y a $q_1 \in l_2$ como el punto a distancia $y$ de $O$. Sea $l_1’$ la recta que pasa por $q_1$ paralela a $l_1$ y sea $l_2’$ la recta que pasa por $p_1$ paralela a $l_2$; la intersección $l_1′ \cap l_2’$ es el punto $A$ que corresponde a la pareja $(x,y)$.

En el siguiente interactivo puedes jugar con la segunda parte de la construcción. Da clic para que se active y luego mueve los deslizadores para cambiar los valores de $X$ y $Y$. Al elegirlos, se realizará la construcción del punto $A$ de manera automática.

Así, hemos definido un sistema de coordenadas al elegir un punto $O$ (que corresponde al origen), una línea que conecta a este con un punto $P$ y otra línea que conecta a $O$ con un punto $Q$ (puntos distintos entre ellos) y al establecer las convenciones de signo.

La construcción que hicimos es muy general, y para nuestros propósitos será mejor centrarnos en el caso en el que las rectas $l_1$ y $l_2$ son ortogonales (forman un ángulo de 90°). Tradicionalmente, $l_1$ es conocida como el eje x y suele ser una línea horizontal cuya dirección positiva está hacia la derecha; $l_2$ (vertical y con dirección positiva hacia arriba) es conocida como el eje y. Este caso particular es conocido como los ejes cartesianos canónicos.

Plano cartesiano en 2 dimensiones.

Si resumimos lo que hemos desarrollado hasta ahora tenemos que, al fijar los ejes coordenados, a cada pareja de números $(x,y)$ le corresponde un punto $\textbf{a} \in \mathbb{E}^2$; además, esta relación también se vale en el otro sentido, por lo que podemos escribir que $\textbf{a}=(x,y)$. A este punto (o par de coordenadas) se le puede asignar una flecha (recta con dirección conocido como vector) que parte del origen y termina en el punto.

En el siguiente interactivo, puedes mover el punto $C$ para ver cómo cambia la flecha que une al origen con $C$.

Para concluir esta entrada, notemos que el procedimiento realizado lo podemos repetir para $n$ líneas; si bien en esta entrada construimos un sistema coordenado con $l_1$ y $l_2$, podemos agregar una $l_3$ que pase por el origen y que sea perpendicular a las otras dos líneas para llevar el plano al espacio (tri-dimensional).

Plano cartesiano en 3 dimensiones.

Más adelante…

En esta entrada construimos el puente entre el espacio descrito por Euclides y el álgebra que implementó Descartes obteniendo entonces el plano cartesiano en dos dimensiones. Esto servirá como base durante todo el curso y en especial para la siguiente entrada en la cual se hablará del espacio vectorial $\mathbb{R}^2$.

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.

  • Demuestra (no muy formalmente) la equivalencia entre el postulado 5, 5.a y 5.b. Sugerencia: Hazlo meramente con dibujos, intenta llegar de la representación de un postulado al otro de manera gráfica.
  • Ubica en el plano cartesiano de dos dimensiones los siguientes puntos:
    • $(2,3)$, $(7,1)$, $(5,10)$
    • $(-1,-5)$, $(-6,-2)$, $(-5,-8)$
    • $(-2,7)$, $(-5,4)$, $(-2,7)$
    • $(4,-3)$, $(2,-1)$, $(4,-5)$
      ¿Notas algún patrón entre los vectores de cada renglón relacionado a dónde quedan con respecto al eje $x$ y al eje $y$?
  • A partir del ejercicio anterior, identifica los cuadrantes (regiones del plano cartesiano divididas por los ejes) en los que las parejas de números tienen signos determinados: $(+,+)$, $(-,-)$, $(-,+)$, $(+,-)$.
  • ¿Cómo son los puntos $(x,y)$ en el plano cartesiano que cumplen que $x=1$? ¿Aquellos que cumplen $y=2$? ¿Y si $y<3$? ¿Y si $1\leq x < 5$?
  • Describe cómo sería la construcción del plano cartesiano de tres dimensiones siguiendo el procedimiento visto en esta entrada.

Geometría Analítica I: Introducción al curso

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Bienvenido al curso de Geometría Analítica I. A través de esta serie de entradas cubriremos el temario oficial del programa de la materia tal y como se requiere en la Facultad de Ciencias de la UNAM. Esto incluye desarrollar no sólo habilidades para ejecutar procedimientos («hacer cuentitas»), sino también aquellas que nos permitan deducir los resultados que obtendremos a través de razonamientos lógicos («demostrar»).

Pre-requisitos del curso

En la mayoría de las entradas seguiremos un flujo matemático, en el cual escribiremos definiciones, proposiciones, ejemplos, teoremas y otro tipo de enunciados matemáticos. Siempre que digamos que algo sucede, es importante argumentar o justificar por qué es esto, es decir, que demos una demostración. Las demostraciones nos ayudarán a justificar que ciertos procedimientos (para encontrar distancias, ángulos, etc.) son válidos.

Para entender un poco más al respecto, te recomendamos leer las siguientes dos entradas, o incluso llevar a la par un curso de Álgebra Superior I:

Además de estos pre-requisitos de pensamiento lógico, también es importante que recuerdes algunos de los conceptos fundamentales de geometría (punto, línea, segmento, triángulo, distancia, etc.). Si bien todo lo construiremos «desde cero», el recordar estos conceptos te ayudará mucho en la intuición de por qué ciertas cosas las definimos como lo haremos, y por qué ciertos enunciados que planteamos «deben ser ciertos».

Finalmente, también supondremos que sabes manejar a buen nivel las operaciones y propiedades en $\mathbb{R}$, los números reales. Por ejemplo, que la suma es conmutativa ($a+b=b+a$), que se distribuye con el producto ($a(b+c)=ab+ac$), etc. Si bien en otros cursos se definen a los reales con toda formalidad, para este curso sólo será importante que sepas hacer estas operaciones.

La idea fundamental

La geometría se trata de figuras, de ver, de medir. El álgebra se trata de sumar, de operar, de comparar. La idea clave que subyace a la geometría analítica, como la veremos en este curso, es la siguiente:

La geometría y el álgebra son complementarias e inseparables, ninguna con más importancia sobre la otra. Podemos entender al álgebra a partir de la geometría, y viceversa.

Un ejemplo muy sencillo que se ve desde la educación básica es que la suma de reales se corresponde con «pegar segmentos». Si en la recta real tenemos un segmento de longitud $a$ y le pegamos un segmento de longitud $b$, entonces el segmento que se obtiene tiene longitud $a+b$. Si bien es obvio, cuando estemos estableciendo los fundamentos tendremos que preguntarnos, ¿por qué pasa? ¿qué es pegar segmentos?

Nuestro objetivo será entender a profundidad muchas de estas equivalencias.

Interactivos

En este curso procuraremos incluir interactivos para que explores las ideas que vayamos introduciendo. Si bien un interactivo no reemplaza a una demostración, lo cierto es que sí ayuda muchísimo a ver más casos en los cuales una proposición o teorema se cumple. Nuestros interactivos están hechos en GeoGebra y necesitarás tener activado JavaScript en tu navegador.

En el siguiente interactivo puedes mover los puntos $A$, $B$ y $C$. Observa como la suma de dos segmentos siempre es igual al tercero. ¿Qué pasa si $B$ «se pasa de $C$»? ¿Cuál segmento es la suma de los otros dos?

Te recomendamos fuertemente que dediques por lo menos un rato a jugar con los interactivos: intenta ver qué se puede mover, qué no, qué cosas piensas que suceden siempre y para cuales crees que haya ejemplos que fallen.

Más adelante…

En esta entrada platicamos de cómo son las notas del curso en general. Platicamos de pre-requisitos y de la idea fundamental que subyace al curso. A partir de la siguiente entrada comenzaremos con el tratamiento teórico de la materia. Hablaremos de dos visiones de geometría: la sintética y la analítica. Veremos un primer resultado que nos dice que, en realidad, ambas están muy relacionadas entre sí.

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. Escribe en una hoja de papel o en un documento digital qué significan para ti los siguientes términos: punto, línea, círculo, plano, semiplano, elipse, intersección, alineado, longitud, ángulo, dirección, vector. ¿En cuáles de estas palabras tuviste que usar las otras? ¿En cuáles no? Más adelante formalizaremos cada una de estas.
  2. Explora el inicio del siguiente libro digital: Euclides de Byrne.
  3. Si aprendes a manejar GeoGebra por tu cuenta, podrás hacer interactivos tú mismo. Si te interesa esto, revisa el siguiente curso de GeoGebra.
  4. ¿Cómo le harías para a cada punto del plano asociarle una pareja de números reales? ¿Cómo le harías para a cada pareja de números reales asociarle un punto en el plano?
  5. Si la suma de números corresponde a pegar segmentos, ¿a qué corresponde la multiplicación de números?

Entradas relacionadas

Seminario de Resolución de Problemas: Factorización de polinomios

Por Fabian Ferrari

Deja un comentario

Introducción

En la entradas anteriores se trataron algunos temas de identidades algebraicas y se profundizó en el binomio de Newton y la identidad de Gauss. En esta y la siguiente entrada hablaremos de polinomios. Por ahora, comenzaremos recordando las nociones básicas de la aritmética de polinomios y hablando un poco de la factorización de polinomios. Más adelante hablaremos del poderoso teorema de la identidad.

Recordatorio de polinomios

Tenemos que un polinomio de grado $n$, donde $n$ es un número entero no negativo, es una expresión algebraica de la forma

\begin{equation*}
a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0.
\end{equation*}

Dicha expresión también podemos denotarla como

\begin{equation*}
P(x)=a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0,
\end{equation*}

en donde $a_n$ es distinto de $0$.

Los elementos $\left\{ a_n, a_{n-1}, … , a_0\right\}$ se conocen como coeficientes. Si $a_n=1$, decimos que el polinomio es mónico.

Nota: El polinomio cuyos coeficientes son todos ceros, se le conoce como el polinomio cero y no tiene grado.

Si dos polinomios son idénticos coeficiente por coeficiente, decimos que dichos polinomios son iguales. Esta noción será de utilidad más adelante en la entrada del teorema de la identidad.

Si todos los coeficientes de un polinomio son enteros, decimos que es un polinomio sobre los enteros. Si los coeficientes son números reales, entonces es un polinomio sobre los reales. De manera similar definimos a los polinomios sobre los racionales, los complejos o incluso sobre $\mathbb{Z}_n$. Aunque parezca irrelevante, conocer las características de los coeficientes de un polinomio, nos da mucha información sobre su constitución. Hay resultados que, por ejemplo, se valen para los polinomios sobre los complejos, pero no para los polinomios sobre los reales.

Otra cosa que es de nuestro interés son las operaciones en los polinomios, y es que al igual que los números enteros, podemos sumar, multiplicar y dividir polinomios.

Algoritmo de la división para polinomios

Para los polinomios, al igual que en los números enteros, existe un algoritmo de la división. Este nos ayudará posteriormente para cuando queramos hacer factorización en polinomios.

Teorema. Sean los polinomios $P(x)$ y $Q(x)$ definidos sobre un campo $\mathbb{K}$ con $Q(x)$ distinto de cero. Entonces existen dos únicos polinomios $C(x)$ y $R(x)$ tales que

\begin{equation*}
P(x)=C(x)Q(x)+R(x),
\end{equation*}

donde $C(x)$ y $R(x)$ son el coeficiente y el residuo respectivamente, resultado de dividir $P(x)$ entre $Q(x)$, y se tiene que $R(x)$ es el polinomio $0$ o bien tiene grado menor o igual al grado de $C(x)$.

Ejemplo. Dados los polinomios $P(x)=x^2-3x-28$ y $Q(x)=x-5$, tenemos que $C(x)=x+2$ y $R(x)=-18$.

En efecto,

\begin{equation*}
x^2-3x-28=(x+2)(x-5)-18.
\end{equation*}

$\square$

Algoritmo de Euclides para polinomios

Al igual que en los enteros, el algoritmo de la división es de ayuda para determinar el máximo común divisor entre dos polinomios: simplemente seguimos los pasos del algoritmo de Euclides. Es por ello que tenemos el siguiente resultado.

Teorema. Si tenemos dos polinomios $P(x)$ y $Q(x)$ sobre un campo $\mathbb{K}$, tenemos que existen polinomios $S(x)$ y $T(x)$ tales que

\begin{equation*}
\MCD{P, Q}= PS+QT.
\end{equation*}

Aquí $\MCD{P, Q}$ es el máximo común divisor de $P(x)$ y $Q(x)$.

Otra forma de ver o de entender el máximo común divisor entre dos polinomios es como el producto de todos aquellos factores que tienen en común.

Problema: Encuentra polinomios $F(x)$ y $G(x)$ tales que

\begin{equation*}
(x^8-1)F(x)+(x^5-1)G(x)=x-1.
\end{equation*}

Sugerencia pre-solución. Recuerda cómo encontrar el máximo común divisor de dos enteros usando el algoritmo de Euclides. Además, usa una factorización para cancelar el factor $x-1$ de la derecha.

Solución. Definamos

\begin{align*}
A(x)&=x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
B(x)&=x^4+x^3+x^2+x+1.
\end{align*}

Notemos que la ecuación es equivalente a

\begin{equation*}
A(x)F(x)+B(x)G(x)=1.
\end{equation*}

Tendría que suceder entonces que $A(x)$ y $B(x)$ sean primos relativos.

Aplicando el algoritmo de la división repetidamente, tenemos lo siguiente:

\begin{align*}
A(x)&=x^3B(x)+(x^2+x+1)\\
B(x)&=x^2(x^2+x+1)+(x+1)\\
x^2+x+1&=x(x+1)+1.
\end{align*}

Esto muestra que $A(x)$ y $B(x)$ son primos relativos, así que la combinación lineal que buscamos debe existir. Para encontrarla de manera explícita, invertimos los pasos. Trabajando hacia atrás, tenemos que

\begin{equation*}
\begin{split}
1 & =(x^2+x+1)-x(x+1)\\
& =(x^2+x+1)-x(B(x)-x^2(x^2+x+1))\\
& =(x^2+x+1)(x^3+1)-xB(x)\\
& =(x^3+1)(A(x)-x^3(B(x))-xB(x)\\
& =(x^3+1)A(x)-x^3(x^3+1)B(x)-xB(x)\\
& =(x^3+1)A(x)+(-x^6-x^3-x)B(x)
\end{split}
\end{equation*}

Así que podemos tomar a $F(x)=x^3+1$ y $G(x)=-x^6-x^3-x$.

$\square$

El teorema del factor

Sea $P(x)$ un polinomio sobre un dominio entero $D$. Decimos que un elemento $a$ de $D$ es raíz del polinomio $P(x)$ si $P(a)=0$. Si aplicamos el algoritmo de la división en los polinomios $P(x)$ y $x-a$ obtenemos el siguiente teorema, que es fundamental en la factorización de polinomios.

Teorema El elemento $a$ es raíz de $P(x)$ si y solo si $(x-a)$ es factor de $P(x)$.

Veamos cómo aplicar este teorema en un ejemplo concreto.

Problema. Dado $\omega=\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$, prueba que

\begin{equation*}
x^{n-1}+\ldots+x+1=(x-\omega)(x-\omega^2)\cdot\ldots\cdot(x-\omega^{n-1}).
\end{equation*}

Sugerencia pre-solución. Recuerda los resultados básicos de aritmética de los números complejos.

Solución. Por De Moivre tenemos que si

\begin{equation*}
\omega=\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)=e^{\frac{2\pi i}{n}}
\end{equation*}

entonces $ \{1, \omega, \omega^2,…,\omega^{n-1}\}$ son raíces de $x^n-1=0$. Además, como $e^{\pi i}=-1$, tenemos que $\omega^n=1$.

Así, tenemos que $\omega^{n+1}=\omega$ y de manera general $\omega^{n+k}=\omega^k$.

Por otro lado,

\begin{equation*}
x^n-1=(x-1)(x^{n-1}+\ldots+x+1)
\end{equation*}

Y como $ \{1, \omega, \omega^2,\ldots,\omega^{n-1}\}$ son raíces de $x^n-1$, tenemos entonces que $\{\omega, \omega^2,\ldots,\omega^{n-1}\}$ deben de ser las raíces de $$x^{n-1}+\ldots+x+1.$$

Aplicando repetidamente el teorema del factor, tenemos que

\begin{equation*}
x^{n-1}+\ldots+x+1=(x-\omega)(x-\omega^2)\cdot\ldots\cdot(x-\omega^{n-1}).
\end{equation*}

$\square$

Un problema para números algebraicos

Un número real es algebraico si es raíz de un polinomio sobre los números enteros.

Problema. Prueba que $\sqrt{2}+\sqrt{3}$ es un número algebraico.

Sugerencia pre-solución. Realiza operaciones de suma, resta y producto con $\sqrt{2}+\sqrt{3}$ y con enteros. Ve si puedes encontrar un patrón de cómo se comportan.

Solución. Tenemos que encontrar un polinomio $P(x)$ sobre los número enteros de tal forma que $P(\sqrt{2}+\sqrt{3})=0$.

Si consideramos $x=\sqrt{2}+\sqrt{3}$, entonces $x^2=5+2\sqrt{6}$

Para $P(x)=x^2-5$, tenemos que $P(\sqrt{2}+\sqrt{3})=2\sqrt{6}$

Así,

\begin{equation*}
(P(\sqrt{2}+\sqrt{3}))^2=(2\sqrt{6})^2=144.
\end{equation*}

Ahora, si consideramos el polinomio

\begin{equation*}
Q(x)=(P(x))^2-144.
\end{equation*}

Tenemos que

\begin{equation*}
Q(\sqrt{2}+\sqrt{3})=(P(\sqrt{2}+\sqrt{3}))^2-144=0.
\end{equation*}

Por lo tanto como el polinomio $Q(x)=x^4-10x^2-119$ es un polinomio sobre los enteros, y como $Q(\sqrt{2}+\sqrt{3})=0$ concluimos que $\sqrt{2}+\sqrt{3}$ es un número algebraico.

$\square$

Más problemas

Puedes encontrar más problemas de aritmética y factorización de polinomios en la Sección 4.2 del libro Problem Solving through Problems de Loren Larson.

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