Archivo de la etiqueta: heurísticas

Seminario de Resolución de Problemas: El teorema del valor intermedio

Por Fabian Ferrari

Introducción

El teorema del valor intermedio nos dice que si $f : [a, b] \to R$ es una función continua, entonces para todo $y$ entre $f (a)$ y $f (b)$ , existe un número $c \in [a, b]$ tal que $f (c) = y$ . La forma de pensar este teorema es que «las funciones continuas no se pueden saltar valores que quedan entre dos valores que ya tomaron», o bien «las funciones continuas no dan brincos en su imagen».

Veamos algunos problemas que se resuelven usando este teorema

Una aplicación directa del teorema del valor intermedio

Problema 1. Muestra que la ecuación $2 x^{3} + 7 x^{2} - 27 x = - 18$ tiene una solución en el intervalo $[- 7, - 5]$ .

Sugerencia pre-solución. Formula un problema equivalente definiendo una función continua $f$ para la cual si $f (x) = 0$ , entonces $x$ es solución a la ecuación.

Solución. La ecuación la podemos ver como $2 x^{3} + 7 x^{2} - 27 x + 18 = 0$ . Consideremos la función $f (x) = 2 x^{3} + 7 x^{2} - 27 x + 18.$ Como $f (x)$ es una función polinomial, sabemos que es continua en $R$ , así que es continua en el intervalo $[- 7, - 5]$ . Lo que queremos ver es que existe un $c$ entre $- 7$ y $- 5$ , tal que $f (c) = 0$ . Para esto, tenemos que evaluar la función en $- 7$ y en $- 5$ .

Tenemos que:

$f (- 7) = - 136$ y $f (- 5) = 78$ .

Tenemos que $0$ está entre $- 136$ y $78$ . Así, por el teorema del valor intermedio, debe de existir un número $c$ entre $- 7$ y $- 5$ de tal forma que $f (c) = 0$ . Por lo tanto $2 x^{3} + 7 x^{2} - 27 x = - 18$ tiene una solución entre $- 5$ y $- 7$ .

Notemos que no se encontró el valor de la raíz de la ecuación, sin embargo mostramos la existencia de esta. Esta es una de las características del teorema del valor intermedio: exhibir la existencia de algo sin necesidad de encontrarlo explícitamente.

Definir una buena función

En ocasiones podemos definir dos funciones para un problema y hacerlas interactuar para obtener una sola función continua que nos permite resolver un problema.

Problema 2. Un montañista empezó a escalar una montaña el sábado a las 8:00 hrs y llegó a la cima a las 18:00 hrs del mismo día. Decidió pasar la noche en la cima de la montaña. El día domingo empezó a descender a las 8:00 hrs y llegó al punto de partida a las 18:00 hrs. Prueba que hubo una hora en la que en ambos días estuvo a la misma altura de la montaña.

Sugerencia pre-solución. Plantea el problema usando dos funciones continuas que denoten la altura conforme pasa el tiempo en ambos días. Tienes mucha flexibilidad, así que usa notación efectiva para simplificar los cálculos.

Solución. Veamos que para este problema, podemos establecer dos funciones continuas para describir el cambio de altura con respecto al tiempo en horas, una para el ascenso y otra para el descenso del montañista en ambos días.

Sean $h_{1} (t)$ , y $h_{2} (t)$ las funciones que representan el ascenso y el descenso del montañista respectivamente. En otras palabras, $h_{1} (t)$ y $h_{2} (t)$ denotan la altura en la que está el montañista tras $t$ horas después de haber comenzado su ascenso y descenso, respectivamente. Como amabas funciones son continuas en el intervalo de tiempo $[0, 10]$ (esto es porque tardó $10$ horas para ascender y $10$ horas para descender), tenemos que la función $g (t) = h_{2} (t) - h_{1} (t)$ tiene que ser continua en $[0, 10]$ también.

Ahora bien, sea $M$ la altura en la cima de la montaña. Tenemos lo siguiente:

$h_{1} (0) = 0$ , $h_{1} (10) = M$ y $h_{2} (0) = M$ , $h_{2} (10) = 0$ .

Así, $g (0) = M$ y $g (10) = - M$ . A su vez, $0$ está entre $- M$ y $M$ , por lo que aplicando el teorema del valor intermedio, debe de existir un $t_{0}$ en el intervalo $[0, 10]$ tal que $g (t_{0}) = 0$ .

Y como

$g (t) = h_{2} (t) - h_{1} (t)$ ,

entonces

$g (t_{0}) = h_{2} (t_{0}) - h_{1} (t_{0})$

$0 = h_{2} (t_{0}) - h_{1} (t_{0})$

$h_{1} (t_{0}) = h_{2} (t_{0}) .$

Con esto podemos concluir que en el tiempo $t_{0}$ el día domingo estuvo a la misma altura que el día sábado al tiempo $t_{0}$ .

Definir un buen intervalo

En algunas ocasiones no es directo qué valores tenemos que usar como los extremos del intervalo al que aplicaremos el teorema del valor intermedio. Un ingrediente adicional que se necesita en el siguiente problema es elegir de manera correcta el extremo derecho.

Problema 3. Prueba que si $n$ es un entero positivo y $x_{0} > 0$ , entonces existe un único número positivo $x$ tal que $x^{n} = x_{0}$ .

Sugerencia pre-solución. Necesitarás modificar el problema un poco. Se quiere encontrar una solución a $x^{n} = x_{0}$ . Limítate a encontrarla en el intervalo $[0, c]$ para una buena elección de $c$ .

Solución. Sea $c$ un número mayor que $1$ de tal forma que $0 < x_{0} < c$ . Si consideramos la función $f (x) = x^{n}$ , tenemos que dicha función es continua en el intervalo $[0, c]$ , y tenemos que

$f (0) = 0$ y $f (c) = c^{n} .$

Como $0 < x_{0} < c < c^{n},$ tenemos que $x_{0}$ está en el intervalo $(0, c)$ , y por el teorema del valor intermedio, tenemos que existe $x$ en el intervalo $(0, c)$ tal que $f (x) = x_{0}$ , que usando la definición de $f$ quiere decir que $x^{n} = x_{0} .$

No puede existir otro además de $x_{0}$ ya que la función $f (x) = x^{n}$ es creciente en el intervalo $[0, c]$ .

Más ejemplos

Puedes encontrar más problemas que se pueden resolver usando el teorema del valor intermedio en el libro Problem Solving Strategies de Loren Larson, en la Sección 6.2.

Seminario de Resolución de Problemas: Aritmética de números complejos

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En entradas anteriores de esta sección hablamos de propiedades aritméticas de números enteros. En esta entrada veremos varias de las propiedades aritméticas de los números complejos y cómo se pueden usar para resolver problemas, incluso aquellos en los que los números complejos no están mencionados de manera explícita en el enunciado.

Distintas formas de los números complejos

La forma más común en la que pensamos en números complejos es en su forma rectangular, en donde un complejo se escribe de la forma $z = a + b i$ , en donde $a$ y $b$ son números reales y pensamos a $i$ como un número tal que $i^{2} = - 1$ . A $a$ le llamamos la parte real y a $b$ la parte imaginaria.

Podemos colocar al complejo $z = a + i b$ en el plano cartesiano, identificándolo con el punto $(a, b)$ . De aquí, la forma polar del complejo es $z = r (\cos θ + i \sin θ)$ , en donde $r$ es la norma $| z | := \sqrt{a^{2} + b^{2}}$ y si $z \neq 0$ , $θ$ es el argumento, que es el ángulo en el sentido antihorario desde el origen entre el eje horizontal y el punto $(a, b)$ . Si $z = 0 + i 0 = 0$ , no definimos el argumento.

Forma polar y rectangular de un complejo.

Así como le hacíamos en el caso de trabajar con módulos, a veces conviene pensar que el argumento es el único ángulo en $[0, 2 π)$ que cumple lo anterior. En otras ocasiones, conviene pensar al argumento como a veces que es la clase de todos los ángulos módulo $2 π$ .

Cuando tenemos a complejos $w = a + i b$ y $z = c + i d$ en forma rectangular, su suma $w + z = (a + c) + i (b + d)$ corresponde geométricamente a encontrar la diagonal del paralelogramo definido por $(a, b)$ , $(c, d)$ y el origen, pues corresponde justo al punto $(a + c, b + d)$ .

Su multiplicación $w z$ en forma rectangular es $(a c - b d) + (a d + b c) i$ , que geométricamente no es tan claro que sea.

La forma exponencial $z = r e^{i θ}$ es simplemente una forma de abreviar a la forma polar, pues por definición $e^{i θ} = \cos θ + i \sin θ$ . En forma exponencial, el producto es más sencillo de entender.

Ejercicio. Demuestra lo siguiente:

Muestra que la norma es multiplicativa, es decir, que para complejos $r$ y $s$ se tiene que $| r s | = | r | | s |$ .
Muestra que $e^{i α} e^{i β} = e^{i (α + β)}$ .

Sugerencia. Para el primer punto, haz las cuentas usando la forma rectangular. Para el segundo punto, escribe las definiciones de todos los términos en forma polar. Haz las multiplicaciones en el lado izquierdo y usa las fórmulas trigonométricas para sumas de ángulos.

Por el ejercicio anterior, si tenemos a los complejos en forma polar $w = r e^{i α}$ , $z = s e^{i β}$ , entonces el producto es $w z = r s e^{i (α + β)}$ , de modo que el producto corresponde al complejo con el producto de normas y suma de argumentos. En ocasiones esto nos permite plantear algunos problemas geométricos en términos de números complejos.

Producto de números complejos. — Multiplicación de números complejos.

Aplicaciones de aritmética de complejos

Veamos dos aplicaciones de la teoría anterior a problemas que no mencionan en el enunciado a los números complejos.

Problema. Sean $a$ y $b$ enteros. Muestra que el número $(a^{2} + b^{2})^{n}$ se puede expresar como la suma de los cuadrados de dos números enteros.

Podría ser tentador usar el binomio de Newton para elevar el binomio a la $n$ -ésima potencia. Sugerimos que intentes esto para darte cuenta de las dificultades que presenta.

Sugerencia pre-solución. Escribe a $a^{2} + b^{2}$ como el cuadrado de la norma de un complejo y usa que es multiplicativa.

Solución. El número $r = a^{2} + b^{2}$ es la norma al cuadrado del número complejo $z = a + i b$ . Entonces, el número $r^{n} = (a^{2} + b^{2})^{n}$ es la norma al cuadrado del número complejo $z^{n} = (a + i b)^{n}$ . Pero al desarrollar $(a + i b)^{n}$ obtenemos únicamente a $i$ , potencias de $a$ y de $b$ , y coeficientes binomiales. De modo que $z^{n} = (a + i b)^{n} = c + i d$ con $c$ y $d$ enteros (aquí estamos usando notación adecuada: no es necesario saber quienes son, sólo que son enteros). Así, $r^{n} = c^{2} + d^{2}$ con $c$ y $d$ enteros.

Veamos ahora un ejemplo de geometría. Este problema es posible resolverlo de muchas formas, pero notemos que los números complejos nos dan una forma de hacerlo de manera algebraica de manera inmediata.

Problema. En la siguiente figura hay tres cuadrados de lado $1$ pegados uno tras otro. Determina la suma de los ángulos marcados con $α$ y $β$ .

Problema de suma de ángulos — Determinar el valor de la suma $α + β$ .

Sugerencia pre-solución. El problema pide determinar una suma de ángulos, así que conviene pensar esta suma de ángulos como el ángulo del producto de dos complejos. Haz tu propia figura, pero ahora sobre el plano complejo.

Solución. El ángulo $α$ es igual al argumento del complejo $2 + i$ y el ángulo $β$ es igual al argumento del complejo $3 + i$ . De esta forma, $α + β$ es igual al argumento del complejo $(2 + i) (3 + i) = (6 - 1) + (2 + 3) i = 5 + 5 i$ . Este complejo cae sobre la recta $Re (z) = Im (z)$ , de modo que su argumento es $π / 4$ .

Este problema también se puede resolver de (numerosas) maneras geométricas, que puedes consultar en este video.

Fórmula de De Moivre

El siguiente teorema se puede demostrar por inducción sobre $n$ .

Teorema (fórmula de De Moivre). Para cualquier entero $n$ y ángulo $θ$ se tiene que $(\cos θ + i \sin θ)^{n} = \cos (n θ) + i \sin (n θ) .$ Dicho de otra forma, en términos de la forma exponencial, se vale usar la siguiente ley de los exponentes $(e^{θ i})^{n} = e^{(n θ) i} .$

La fórmula de De Moivre es otra herramienta que ayuda a resolver problemas de números reales enunciándolos en términos trigonométricos. El truco consiste en:

Tomar una expresión real que queramos entender.
Identificarla como la parte real o imaginaria de una expresión compleja.
Usar la aritmética de números complejos para entender la expresión compleja.
Regresar lo que entendamos a los reales.

Veamos un par de ejemplos, relacionados con funciones trigonométricas. Comenzamos con una fórma de encontrar la fórmula para el coseno de cinco veces un ángulo.

Problema. Sea $θ \in [0, 2 π)$ . Expresa a $\cos 5 θ$ en términos de $\cos θ$ .

Sugerencia pre-solución. Identifica a $\cos 5 θ$ como la parte real de un número complejo. Inspírate en la fórmula de De Moivre. Usa binomio de Newton.

Solución. Por la fórmula de De Moivre, $\cos 5 θ$ es la parte real del complejo $(\cos θ + i \sin θ)^{5}$ , así que calculemos quién es exactamente este número usando binomio de Newton. Para simplificar la notación, definimos $a = \cos θ$ y $b = \sin θ$ . Tenemos que

$\begin{aligned} (a + i b)^{5} & = a^{5} + 5 a^{4} (b i) + 10 a^{3} (i b)^{2} + 10 a^{2} (i b)^{3} + 5 a (i b)^{4} + (i b)^{5} \\ = (a^{5} - 10 a^{3} b^{2} + 5 a b^{4}) + (5 a^{4} b - 10 a^{2} b^{3} + b^{5}) i . \end{aligned}$

Además, por la identidad pitagórica recordemos que $a^{2} + b^{2} = 1$ , de donde $b^{2} = 1 - a^{2}$ , de modo que la parte real de la expresión anterior es $a^{5} - 10 a^{3} (1 - a^{2}) + 5 a (1 - 2 a^{2} + a^{4}),$ que agrupando es $16 a^{5} - 20 a^{3} + 5 a .$ Recordando que $a$ es $\cos θ$ , obtenemos la fórmula final $\cos 5 θ = 16 \cos^{5} θ - 20 \cos^{3} θ + 5 \cos θ .$

Raíces de la unidad

En muchos problemas se utilizan las raíces de la ecuación $x^{n} = 1$ .

Teorema. Sea $n \geq 1$ un entero. Las ecuación $x^{n} = 1$ tiene $n$ soluciones complejas, que en el plano complejo forman los vértices del $n$ -ágono regular con centro en $0$ y tal que uno de sus vértices es $1$ . Si $ω$ es la raíz de menor argumento positivo, entonces estas soluciones son $1, ω, ω^{2}, \dots, ω^{n - 1}$ .

Raíces de la unidad en los números complejos — Raíces $n$ -ésimas de la unidad para $n = 5$ .

A estas soluciones les llamamos las raíces $n$ -ésimas de la unidad. Notemos que $ω^{n} = 1$ , y que en general si escribimos a un entero $m$ usando el algoritmo de la división como $m = q n + r$ , entonces $ω^{m} = ω^{r}$ . ¡Los productos de raíces de la unidad se comportan como los elementos de $Z_{n}$ bajo suma módulo $n$ !

Proposición. Sea $n \geq 2$ un entero. La suma de las $n$ raíces $n$ -ésimas de la unidad es $0$ y su producto es $1$ .

La proposición anterior nos permite, en ocasiones, «filtrar» ciertas expresiones algebraicas. A continuación presentamos un ejemplo, que retomamos de los primeros ejemplos que vimos, cuando estábamos aprendiendo la heurística de encontrar un patrón.

Problema. Determina el valor de la suma $(\binom{100}{0}) + (\binom{100}{3}) + (\binom{100}{6}) + \dots + (\binom{100}{99}) .$

Sugerencia pre-solución. Si no recuerdas lo que debería salir, vuelve a experimentar con los primeros valores, para cuando en vez de usar $100$ se usan números más chiquitos. Para entender mejor el patron, generaliza el problema, y en vez de sólo tener múltiplos de $3$ abajo, explora también qué sucede cuando tienes los números que dejan residuo $0$ , $1$ o $2$ módulo $3$ .

Ya que recuerdes la fórmula que queremos, considera una raíz cúbica $ω$ de la unidad distinta de $1$ . Calcula $(1 + 1)^{100}$ , $(1 + ω)^{100}$ y $(1 + ω^{2})^{100}$ usando el binomio de Newton y aprovechando que toda potencia de $ω$ es $1$ , $ω$ u $ω^{2}$ para simplificar la notación.

Solución. Sea $ω$ una raíz cúbica de la unidad distinta de $1$ . Tenemos que $ω^{3} = 1$ y que $1 + ω + ω^{2} = 0$ . De este modo, podemos usar $ω$ y el binomio de Newton para calcular las siguientes expresiones

$\begin{aligned} (1 + 1)^{100} & = (\binom{100}{0}) + (\binom{100}{1}) + (\binom{100}{2}) + (\binom{100}{3}) + \dots \\ (1 + ω)^{100} & = (\binom{100}{0}) + (\binom{100}{1}) ω + (\binom{100}{2}) ω^{2} + (\binom{100}{3}) + \dots \\ (1 + ω^{2})^{100} & = (\binom{100}{0}) + (\binom{100}{1}) ω^{2} + (\binom{100}{2}) ω + (\binom{100}{3}) + \dots \end{aligned}$

¿Qué sucede al sumar las tres expresiones? En el lado derecho, cada vez que $m$ es un múltiplo de $3$ , tenemos $3 (\binom{100}{m})$ , y cada vez que $m$ no es un múltiplo de $3$ , tenemos $(1 + ω + ω^{2}) (\binom{100}{m}) = 0.$ ¡Se filtran exactamente los coeficientes binomiales con parte inferior múltiplo de $3$ ! Así, tres veces la suma que buscamos es igual a $2^{100} + (1 + ω)^{100} + (1 + ω^{2})^{100} .$

Esta ya es una expresión suficientemente cerrada, pero podemos simplificar todavía más:

$\begin{aligned} (1 + ω)^{100} & = (- ω^{2})^{100} = ω^{200} = ω^{2} \\ (1 + ω^{2})^{100} & = (- ω)^{100} = ω \\ (1 + ω)^{100} + (1 + ω^{2})^{100} & = ω^{2} + ω = - 1. \end{aligned}$

Así, la expresión que queremos es $\frac{2^{100} - 1}{3}$ .

Más ejemplos

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

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

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

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

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

Números primos

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

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

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

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

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

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

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

Proposición 2. Si $p$ es primo, $a$ un entero y $n$ un entero positivo tales que $p ∣ a^{n}$ , entonces $p^{n} ∣ a^{n}$ .

Teorema fundamental de la aritmética

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

Teorema (teorema fundamental de la aritmética). Sean $a$ un entero positivo. Entonces existe un único $n$ , únicos primos $p_{1} < \dots < p_{n}$ y exponentes $α_{1}, \dots, α_{n}$ tales que $a = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}} .$

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

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

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

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

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

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

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

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

Solución. Vamos a comenzar suponiendo $m^{2} = 2^{8} + 2^{11} + 2^{n}$ . De aquí, $\begin{aligned} 2^{n} & = m^{2} - 2^{8} (1 + 2^{3}) \\ = m^{2} - (3 \cdot 2^{4})^{2} \\ = (m + 48) (m - 48) . \end{aligned}$

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números $m + 48$ y $m - 48$ tienen que ser potencias de $2$ , digamos $m + 48 = 2^{a}$ y $m - 48 = 2^{b}$ con $a > b$ y $a + b = n$ . Además tenemos que $2^{b} (2^{a - b} - 1) = 96 = 2^{5} \cdot 3.$

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

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

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

Sean $a$ y $b$ números enteros positivos y $P = p_{1}, \dots, p_{n}$ el conjunto de números primos que dividen a alguno de $a$ o $b$ . Por el teorema fundamental de la aritmética, existen exponentes $α_{1}, \dots, α_{n}$ y $β_{1}, \dots, β_{n}$ , tal vez algunos de ellos cero, tales que $\begin{aligned} a & = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot \dots \cdot p_{n}^{α_{n}} \\ b & = p_{1}^{β_{1}} \cdot p_{2}^{β_{2}} \cdot \dots \cdot p_{n}^{β_{n}} . \end{aligned}$

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

Proposición 3. Se tiene que $a$ divide a $b$ si y sólo si para todo primo $p_{i}$ se tiene que $α_{i} \leq β_{i}$ .

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

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

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

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

Proposición 4. El entero $a$ tiene $(α_{1} + 1) (α_{2} + 1) \dots (α_{n} + 1)$ divisores positivos.

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

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

Solución. Tomemos $a$ un entero y $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}}$ su factorización en primos. Por la Proposición 4, necesitamos que $(α_{1} + 1) (α_{2} + 1) \dots (α_{n} + 1) = 49$ .

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

El número $a$ tiene sólo un divisor primo y $a = p_{1}^{48}$ .
El número $a$ tiene dos divisores primos y $a = p_{1}^{6} p_{2}^{6}$ .

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

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

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

Proposición 4. Se pueden calcular $MCD (a, b)$ y $mcm (a, b)$ como sigue:
$\begin{aligned} MCD (a, b) & = p_{1}^{min (α_{1}, β_{1})} \cdot p_{2}^{min (α_{2}, β_{2})} \cdot \dots \cdot p_{n}^{min (α_{n}, β_{n})} \\ mcm (a, b) & = p_{1}^{max (α_{1}, β_{1})} \cdot p_{2}^{max (α_{2}, β_{2})} \cdot \dots \cdot p_{n}^{max (α_{n}, β_{n})} . \end{aligned}$

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

Problema. Demuestra que $MCD (a, b) mcm (a, b) = a b$ .

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

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

Más ejemplos

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

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

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 = r a$ . Lo escribimos en símbolos como $a ∣ 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 ∣ b$ y $b ∣ a$ , entonces $| a | = | b |$ , es decir $a = b$ o $a = - b$ .

Si tenemos varios números $a_{1}, \dots, 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}, \dots, a_{n})$ y $mcm (a_{1}, \dots, a_{n})$ .

Proposición 2. Si $n$ divide a $a$ y a $b$ , entonces divide a cualquier combinación lineal entera $r a + s b$ 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 : Z^{+} \times Z^{+} \to Z^{+}$ tales que cumplen las siguientes tres propiedades simultáneamente:

$f (a, a) = a$ para todo entero positivo $a$ .
$f (a, b) = f (b, a)$ para todo par de enteros positivos $a$ y $b$ .
$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, \dots, 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.

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}, \dots, a_{n}$ , entonces $d ∣ MCD (a_{1}, \dots, a_{n}) .$ Si tenemos otro número $M$ que sea múltiplo de $a_{1}, \dots, a_{n}$ , entonces $mcm (a_{1}, \dots, a_{n}) ∣ M .$

Problema. Sean $a$ y $b$ enteros positivos. Muestra que $MCD (a, b) mcm (a, b) = a b .$

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 = r D$ y $b = s D$ . Notemos que $r s D = a s = b r$ , así que $r s D$ es un múltiplo de $a$ y $b$ , y por la Proposición 3, tenemos que $m ∣ r s D$ . Multiplicando por $D$ esta divisibilidad, tenemos que $D m ∣ r s D^{2} = a b$ .

Como $a b$ es múltiplo de $a$ y de $b$ , por la Proposición $3$ es múltiplo de $m$ , digamos $a b = k m$ . 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 ∣ D$ . Multiplicando por $m$ esta divisibilidad, tenemos que $k m ∣ D M$ , es decir, $a b ∣ D m$ .

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

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 = b q + r$ .

Consideremos la igualdad $a = b q + 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{aligned} a & = b q_{1} + r_{1} \\ b & = r_{1} q_{2} + r_{2} \\ r_{1} & = r_{2} q_{3} + r_{3} \\ ⋮ \\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n} \\ r_{n - 1} & = r_{n} q_{n + 1} + 0 \end{aligned}$

de las que obtenemos $MCD (a, b) = MCD (b, r_{1}) = \dots = MCD (r_{n}, 0) = r_{n} .$
En las igualdades llegamos a un residuo $0$ pues $b > r_{1} > r_{2} > r_{3} > \dots \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 $R^{3}$ como sigue:

$\begin{aligned} v_{1} & = (a, 1, 0) \\ v_{2} & = (b, 0, 2) \\ v_{i + 2} & = v_{i} - q_{i} v_{i + 1} para i = 1, \dots, n - 1 \end{aligned}$

Sean $r_{- 1} = a$ y $r_{0} = b$ . Muestra que para $i = 1, 2, 3, \dots, n + 1$ se tiene que $v_{i} = (x_{i}, y_{i}, z_{i})$ , en donde:

$x_{i} = r_{i - 2}$
$x_{i} = a y_{i} + b z_{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, \dots, 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{aligned} x_{k + 1} & = x_{k - 1} - q_{k - 1} x_{k} \\ = r_{k - 3} - q_{k - 1} r_{k - 2} \\ = r_{k - 1}, \end{aligned}$

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{aligned} x_{k + 1} & = x_{k - 1} - q_{k - 1} x_{k} \\ = a y_{k - 1} + b z_{k - 1} - q_{k - 1} (a y_{k} + b z_{k}) \\ = a (y_{k - 1} - q_{k - 1} y_{k}) + b (z_{k - 1} - q_{k - 1} z_{k}) \\ = a y_{k + 1} + b z_{k + 1} . \end{aligned}$

Con esto terminamos la inducción.

El problema anterior nos dice que, en particular, $r_{n} = a y_{n} + b x_{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) = a m + b n$ .

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

		3	2	2	3
754	221	91	39	13	0
1	0	1	-2	5	-17
0	1	-3	7	-17	58

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

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 - 6 n}{9 n - 61}$ es irreducible.

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

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

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

Problema. Se tiene un número irracional $α$ para el cual $α^{91}$ y $α^{119}$ son números racionales. Muestra que $α^{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 = 91 m + 119 n$ , de donde $14 = 91 \cdot (2 m) + 119 \cdot (2 n)$ .

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

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

Seminario de Resolución de Problemas: Aritmética modular

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En la entrada anterior hablamos de divisibilidad, máximo común divisor y combinaciones lineales enteras. Cuando hablamos de trabajar en artimética modular nos referimos a que tomamos un entero $n$ y realizamos todas las operaciones «sólo en el mundo de $n$ », es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre $n$ .

Cuando estamos trabajando módulo $n$ , dos enteros $a$ y $b$ «son los mismos» si $n$ divide a $a - b$ . En este caso decimos que $a \equiv b (\mod n)$ , que se lee « $a$ es congruente con $b$ módulo $n$ ».

En esta entrada de blog discutimos la relación «ser congruente con» y cómo se puede enunciar en términos de anillos. Ahí damos las demostraciones de varias de las propiedades que no probaremos aquí. Es recomendable por lo menos echarle un ojo.

Aritmética modular

Para recordar los principios básicos de la aritmética modular, comencemos con el siguiente problema.

Problema. Determina cuál es el residuo obtenido de dividir $1305 \cdot 1302 + 1314 \cdot 1311$ al dividirse entre $11$ .

Sugerencia pre-solución. Intenta resolver este problema trabajando módulo $11$ .

Solución. Tenemos que $1305$ , $1302$ , $1314$ y $1311$ los podemos poner como un múltiplo de $13$ más un residuo como sigue: $1300 + 5$ , $1300 + 2$ y $1313 + 1$ , $1300 + 11$ . Así, $1305 \equiv 5 (\mod 13)$ , $1302 \equiv 2 (\mod 13)$ , $1314 \equiv 1 (\mod 13)$ y $1311 \equiv 11 (\mod 13)$ . Así, trabajando módulo $1$ tenemos que:

$\begin{aligned} 1305 \cdot 1302 + 1314 \cdot 1311 & \equiv 5 \cdot 2 + 1 \cdot 11 \\ \equiv 10 + 11 \equiv 21 \\ \equiv 8 (\mod 13) \end{aligned}$
De esta forma, $1305 \cdot 1302 + 1314 \cdot 1311$ deja residuo $8$ al dividirse entre $13$ .

Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.

Proposición. Para cada entero $a$ y entero positivo $n$ , existe un único número $r$ en ${0, 1, \dots, n - 1}$ tal que $a \equiv r (\mod n)$ , que es justo el residuo obtenido al dividir $a$ entre $n$ .

Dicho en otras palabras, sólo hay $n$ posibles residuos al dividir entre $n$ . Esto nos permite que las operaciones módulo $n$ siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre $n$ dependen sólo de $n$ casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.

Problema. Se tienen $13$ números enteros. Muestra que hay tres de ellos $a, b, c$ que satisfacen que $1331 ∣ (a - b) (b - c) (c - a) .$

Sugerencia pre-solución. Notemos que $1331 = 11^{3}$ , así que trabajamos módulo $11$ . Encuentra todas las posibilidades que pueden tener los números cuadrados.

Solución. Un entero $n$ sólo puede ser congruente con alguno de los números $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ módulo $11$ . Los cuadrados tienen entonces las siguientes posibilidades:

$n$	$n^{2} (\mod 11)$
$0$	$0$
$1$	$1$
$2$	$4$
$3$	$9$
$4$	$16 \equiv 5$
$5$	$25 \equiv 3$
$6$	$36 \equiv 3$
$7$	$(- 4)^{2} \equiv 5$
$8$	$9$
$9$	$4$
$10$	$1$

A partir del $6$ estamos aprovechando que ya conocemos los del $1$ al $6$ y que $a \equiv a - 11 (\mod 11)$ . Notemos que sólo hay $6$ residuos posibles para los cuadrados módulo $11$ , que son $0$ , $1$ , $4$ , $9$ , $5$ y $3$ .

Ahora sí, resolvamos el problema. Como tenemos $13$ números enteros y sólo hay $6$ posibles residuos para los cuadrados módulo $11$ , entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre $11$ , digamos $a, b, c$ . Como dejan los tres el mismo residuo, tenemos $11 ∣ a - b$ , $11 ∣ b - c$ y $11 ∣ c - a$ , de donde se sigue la conclusión que queremos.

Últimos dígitos

Los últimos $m$ dígitos de un entero $n$ corresponden con el residuo de dividir $n$ entre $10^{m}$ . Por esta razón, en este tipo de problemas es conveniente usar módulos.

Problema. Determina los últimos dos dígitos de $7^{25} + 25^{7}$ .

Sugerencia pre-solución. Trabajamos módulo $100$ , así que todas las congruencias son módulo $100$ . Hay muchas formas de proceder para encontrar $7^{21}$ . Notemos que $7^{2} \equiv 49$ . y que $7^{4} \equiv 49 \times 49 = 2401 \equiv 1.$ Esto es una gran ventaja, pues entonces $7^{24} \equiv (7^{4})^{6} \equiv 1^{6} \equiv 1$ , así que $7^{25} \equiv 7$ .

Para $25^{7}$ , nos conviene notar que $25 = 20 + 5$ , de modo que
$\begin{aligned} 25^{2} & = (20 + 5)^{2} \\ = 20^{2} + 2 \cdot 20 \cdot 5 + 25 \\ \equiv 25, \end{aligned}$

pues los primeros dos sumandos son múltiplos de $100$ . De esta forma, $25^{7} \equiv 25$ . Así, $7^{25} + 25^{7} \equiv 7 + 25 \equiv 32$ , por lo que los dos últimos dígitos de la expresión son $32$ .

Veamos otro ejemplo en el que además combinamos un poco de la teoría mencionada en la entrada anterior.

Problema. Demuestra que existe un entero que es múltiplo de $2002$ y que tiene por lo menos $2002$ dígitos iguales a $7$ .

Sugerencia pre-solución. Intenta hacer que los $2002$ dígitos $7$ que se necesitan aparezcan hacia el final. Esto te permitirá usar congruencias. Además, necesitarás el resultado de la entrada anterior que dice que el máximo común divisor de dos números se puede expresar como combinación lineal entera de ellos.

Solución. Tomemos el número $N = 777 \dots 770$ , en donde hay $2002$ dígitos iguales a $7$ .

El máximo común divisor de $2002$ y $10^{2003}$ es $2$ , de modo que existen enteros $m$ y $n$ tales que $2002 m + 10^{2003} n = 2$ .

Multiplicando esta igualdad por el entero $N / 2$ , obtenemos que $2002 \cdot \frac{m N}{2} + 10^{2003} \frac{n N}{2} = N$ . Aplicando módulo $10^{2003}$ obtenemos que $2002 \cdot \frac{m N}{2} \equiv N (\mod 10^{2003})$ .

Como $N < 10^{2003}$ , esto nos dice que $2002 \cdot \frac{m N}{2}$ es un múltiplo de $2002$ cuyos últimos $2003$ dígitos son los de $N$ , es decir, que tiene por lo menos $2002$ dígitos iguales a $7$ .

Teorema chino del residuo

En algunos problemas necesitamos construir un entero que satisfaga un conjunto de congruencias. El teorema chino del residuo nos da una condición bajo la cual podemos garantizar la existencia de dicho número.

Teorema. Sea $n \geq 2$ un entero, $b_{i}$ enteros para $i \in {1, 2, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, n}$ . Supongamos además que cada par $m_{i}, m_{j}$ de enteros ( $i \neq j$ ) son primos relativos. Entonces el sistema lineal de congruencias
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene una y sólo una solución módulo $m_{1} m_{2} \dots m_{n}$ .

El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.

Problema. ¿Será posible encontrar $5$ enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de $1$ ?

Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con $5$ módulos y en donde los $b_{i}$ son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo $n$ tal que
$\begin{aligned} n & \equiv 0 (\mod 2^{3}) \\ n & \equiv - 1 (\mod 3^{3}) \\ n & \equiv - 2 (\mod 5^{3}) \\ n & \equiv - 3 (\mod 7^{3}) \\ n & \equiv - 4 (\mod 11^{3}) \end{aligned}$

Para este entero, se tiene que $2^{3}$ divide a $n$ , $3^{3}$ divide a $n + 1$ , $5^{3}$ divide a $n + 2$ , $7^{3}$ divide a $n + 3$ y $11^{3}$ divide a $n + 4$ .

Más ejemplos

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

Hay otros dos teoremas que sirven cuando estamos trabajando módulo $n$ , de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo $n$ .

El teorema de Fermat y el de Wilson ayudan a entender potencias y factoriales, respectivamente. En la entrada sobre el teorema chino del residuo damos una demostración al teorema.

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Archivo de la etiqueta: heurísticas

Seminario de Resolución de Problemas: El teorema del valor intermedio

Introducción

Una aplicación directa del teorema del valor intermedio

Definir una buena función

Definir un buen intervalo

Más ejemplos

Seminario de Resolución de Problemas: Aritmética de números complejos

Introducción

Distintas formas de los números complejos

Aplicaciones de aritmética de complejos

Fórmula de De Moivre

Raíces de la unidad

Más ejemplos

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

Introducción

Números primos

Teorema fundamental de la aritmética

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

Más ejemplos

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

Divisibilidad y máximo común divisor

Algoritmo de la división y algoritmo de Euclides

Más ejemplos

Seminario de Resolución de Problemas: Aritmética modular

Introducción

Aritmética modular

Últimos dígitos

Teorema chino del residuo

Más ejemplos