Archivo de la etiqueta: euclides

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

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 el 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 ere 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 a el espacio (tri-dimensional).

Plano cartesiano en 3 dimensiones.

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.

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.

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

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.

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.

  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?

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

Entradas relacionadas

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

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 \right\{a_n, a_{n-1}, ... , a_0\left\} 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

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 para todo entero.

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: Problemas de divisibilidad

A continuación les dejo los links que les preparé para hoy. Se ven en el orden que están. Si tienen dudas, pueden ponerlas en la sección de comentairos de aquí del blog.

Ejemplo de algoritmo de la división de Euclides
Condición necesaria para que 2^n+1 sea primo
a-b divide a a^n-b^n