1.4: Combinatoria y Teoría de Números
- Page ID
- 118269
En términos generales, la teoría de números se ocupa de las propiedades de los enteros positivos. G.H. Hardy fue un brillante matemático británico que vivió ambas guerras mundiales y realizó una gran cantidad de investigaciones teóricas de números. También era un pacifista que estaba contento de que, desde su perspectiva, su investigación no fuera “útil”. Escribió en su ensayo de 1940 La disculpa de un matemático “[n] o uno todavía ha descubierto algún propósito bélico para ser servido por la teoría de los números o la relatividad, y parece muy poco probable que alguien lo haga durante muchos años”. Poco sabía él, las ideas matemáticas más puras de la teoría de números pronto se volverían indispensables para las técnicas criptográficas que mantenían seguras las comunicaciones. Nuestro tema aquí no es la teoría de números, sino que veremos algunas veces donde las técnicas combinatorias son de utilidad en la teoría de números.
Formar una secuencia de enteros positivos usando las siguientes reglas. Comience con un entero positivo\(n > 1\). Si\(n\) es impar, entonces el siguiente número es\(3n+1\). Si\(n\) es par, entonces el siguiente número es\(n/2\). Detente si alguna vez llegas a 1. Por ejemplo, si empezamos con 28, la secuencia es
\(28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1\)
Ahora suponga que empiezas con 19. Entonces los primeros términos son
\(19,58,29,88,44,22\)
Pero ahora notamos que el entero 22 aparece en la primera secuencia, por lo que las dos secuencias coincidirán a partir de este momento. Las secuencias formadas por esta regla se denominan secuencias de Collatz.
Escoge un número en algún lugar entre 100 y 200 y anota la secuencia que obtengas. Independientemente de su elección, eventualmente se detendrá con un 1. Sin embargo, ¿hay algún número entero positivo\(n\) (posiblemente bastante grande) para que si empiezas\(n\), nunca alcanzarás 1?
A los estudiantes de secundaria se les enseña a sumar fracciones encontrando múltiplos menos comunes. Por ejemplo, el múltiplo menos común de 15 y 12 es 60, entonces:
\(\dfrac{2}{15} + \dfrac{7}{12} = \dfrac{8}{60} + \dfrac{35}{60} = \dfrac{43}{60}\)
¿Qué tan difícil es encontrar el múltiplo menos común de dos enteros?
Es realmente fácil si puedes factorizarlos en primos. Por ejemplo, considera el problema de encontrar el múltiplo menos común de\(351785000\) y\(316752027900\) si solo te pasa a saber que
\(351785000 = 2^3 \times 5^4 \times 7 \times 19 \times 23^2\)y
\(316752027900 = 2^2 \times 3 \times 5^2 \times 7^3 \times 11 \times 23^4\).
Entonces el múltiplo menos común es
\(300914426505000 = 2^3 \times 3 \times 5^4 \times 7^3 \times 11 \times 19 \times 23^4\).
Entonces, para encontrar el múltiplo menos común de dos números, solo tenemos que factorizarlos en primos. Eso no suena muy duro. Para empezar, ¿se puede factorizar 1961? Bien, ¿qué tal 1348433? Ahora para un verdadero reto. Supongamos que te dicen que el entero
\(c = 55684901170770357082442831733350405217163692355899511509652043138898236817075547572153799\)
es producto de dos primos\(a\) y\(b\). ¿Los puedes encontrar?
¿Y si el factoring es difícil? ¿Se puede encontrar el múltiplo menos común de dos enteros relativamente grandes, digamos cada uno con aproximadamente 500 dígitos, por otro método? ¿Cómo se debe enseñar a los estudiantes de secundaria a sumar fracciones?
Como un aparte, observamos que la mayoría de las calculadoras no pueden sumar o multiplicar dos números de 20 dígitos, mucho menos dos números con más de 500 dígitos. Pero es relativamente sencillo escribir un programa de computadora que haga el trabajo por nosotros. Además, hay algunas poderosas herramientas de software matemático disponibles. Dos ejemplos comerciales muy conocidos son Maple® y Mathematica®. En este texto, de vez en cuando, haremos uso del sistema de álgebra informática de código abierto SaeMath. A veces incrustaremos celdas interactivas de SaeMath en el texto, pero también puedes usar SaeMath de forma gratuita en línea a través de SaeMath Cloud. Por ejemplo, la celda SaeMath a continuación producirá la factorización que se muestra arriba.
//Código
Si estás leyendo este texto en un navegador web, sigue adelante y cambia el número entero en la celda de SaeMath anterior a algún otro entero, tal vez más grande, y haz clic nuevamente en el botón para obtener la factorización prima de tu nuevo entero.
Ahora bien, así es como inventamos el problema del reto. Primero, encontramos un sitio en la web que enumera primos grandes y encontramos estos dos valores:
\(a=2425967623052370772757633156976982469681\)y
\(b=22953686867719691230002707821868552601124472329079\).
El código de SaeMath a continuación calcula\(a×b\) y devuelve el resultado al instante.
//Código
Por otro lado, si le pides a SaeMath que factorice\(c\), como en la celda de abajo, probablemente estarás esperando mucho tiempo. Si obtiene una respuesta en más de un par de minutos, envíenos un correo electrónico para que podamos actualizar el texto con números primos más grandes\(a\) y\(b!\)
//Código
Las preguntas que surgen en la teoría de números también pueden tener un estilo enumerativo, como muestra el siguiente ejemplo.
En la Figura 1.11, mostramos las particiones enteras de 8.
Figura 1.11. Las particiones de 8, señalando esas en partes distintas y aquellas en partes impares.
Hay 22 particiones en total, y como se señaló, exactamente 6 de ellas son particiones de 8 en partes impares. Además, exactamente 6 de ellos son particiones de 8 en partes distintas.
¿Cuál sería tu reacción si te pidiéramos que encontraras el número de particiones enteras de 25892? ¿Cree que el número de particiones de 25892 en partes impares es igual al número de particiones de 25892 en partes distintas? ¿Hay alguna manera de responder a esta pregunta sin calcular realmente el número de particiones de cada tipo?