Archivo de la etiqueta: dígitos

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

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 \pmod 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\pmod {13}, 1302\equiv 2 \pmod {13}, 1314\equiv 1 \pmod {13} y 1311\equiv 11 \pmod {13}. Así, trabajando módulo 1 tenemos que:

    \begin{align*}1305\cdot 1302+1314\cdot 1311 &\equiv 5\cdot 2 + 1\cdot 11 \\&\equiv 10 + 11 \equiv 21 \\&\equiv 8 \pmod {13}\end{align*}


De esta forma, 1305\cdot 1302+1314\cdot 1311 deja residuo 8 al dividirse entre 13.

\square

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,\ldots,n-1\} tal que a\equiv r\pmod 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\mid (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:

nn^2 \pmod {11}
00
11
24
39
416\equiv 5
525\equiv 3
636\equiv 3
7(-4)^2\equiv 5
89
94
101

A partir del 6 estamos aprovechando que ya conocemos los del 1 al 6 y que a \equiv a-11 \pmod {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\mid a-b, 11\mid b-c y 11\mid c-a, de donde se sigue la conclusión que queremos.

\square

Ú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{align*}25^2&=(20+5)^2\\&=20^2+2\cdot 20 \cdot 5 + 25\\&\equiv 25,\end{align*}

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.

\square

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\cdots770, 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 2002m+10^{2003}n=2.

Multiplicando esta igualdad por el entero N/2, obtenemos que 2002\cdot \frac{mN}{2}+10^{2003}\frac{nN}{2}=N. Aplicando módulo 10^{2003} obtenemos que 2002\cdot \frac{mN}{2} \equiv N \pmod {10^{2003}}.

Como N<10^{2003}, esto nos dice que 2002\cdot \frac{mN}{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.

\square

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,\ldots,n\} y m_i enteros positivos para i\in\{1,\ldots,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{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\end{align*}


tiene una y sólo una solución módulo m_1m_2\ldots 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{align*}n&\equiv 0 \pmod{2^3}\\n&\equiv -1\pmod{3^3}\\n&\equiv -2\pmod{5^3}\\n&\equiv -3\pmod{7^3}\\n&\equiv -4\pmod{11^3}\end{align*}

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.

\square

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.

Seminario de Resolución de Problemas: Bases numéricas y dígitos

Introducción

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

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

Expresión en una base arbitraria

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

Teorema. Sea r un número real y b\geq 2 un entero. Entonces, existen únicos enteros A_0,A_1,\ldots, a_1,a_2,\ldots en \{0,1,\ldots,b-1\} tales que

    \[r=\sum_{i=0}^\infty A_i b^i + \sum_{i=0}^{\infty} a_i 10^{-i}\]

y a_i\neq b-1 para una infinidad de i‘s.

Para estos a_i y A_i escribimos

    \[r=(\ldots A_2A_1A_0.a_1a_2\ldots)_b,\]

en donde el subíndice indica la base que se está usando.

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

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

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

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

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

Problema. Determina si existe un real x tal que

    \[\floor{x}+\floor{2x}+\floor{4x}+\floor{8x}= 2222.\]

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

Solución. Tenemos que r\geq \floor{r} para todo real r, de modo que si dicho número x existe, se cumple

    \[17x\geq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} = 2222.\]

De aquí, x\geq 2222/17 = 130.705\ldots\geq 130. También, r\leq \floor{r}+1, de modo que si x existe necesitamos

    \[17x\leq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} + 4 = 2226.\]

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

Esto nos dice que x es un real entre 130 y 131. Escribámoslo como 130 más una parte fraccional en base 2, es decir, de la forma x=130+(abcde\ldots)_2. Multiplicar por 2 simplemente recorre el punto decimal en base 2 un lugar hacia la derecha, de modo que

    \begin{align*}2x&=260+(a.bcde\ldots)_2\\4x&=520+(ab.cde\ldots)_2\\8x&=1040+(abc.de\ldots)_2,\end{align*}

y por lo tanto

    \begin{align*}\floor{x}&=130\\\floor{2x}&=260+(a)_2=260+a\\\floor{4x}&=520+(ab)_2=520+2a+b\\\floor{8x}&=1040+(abc)_2=1040+4a+2b+c.\end{align*}

Concluimos entonces que la suma buscada es igual a 1950+7a+3b+c. Si existe el número que queremos, la ecuación

    \[1950+7a+3b+c=2222\]

debe tener una solución con a, b y c iguales a 0 o a 1. Pero esto es imposible, pues incluso aunque los tres sean iguales a 1, tenemos a lo más 1950+11=1961. De esta forma, no existe la x que buscamos.

\square

Bases y números racionales

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

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

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

Problema. Considera el número en binario

    \[r=(0.a_1a_2a_3\ldots)_2\]

en donde a_i=0 si i es primo y a_i=1 si no. Determina si r es un número racional o irracional.

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

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

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

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

\square

Criterios de divisibilidad

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

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

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

Demostrar estos criterios es sencillo. Por ejemplo, un número (A_nA_{n-1}\ldots A_0)_{10} en base 10 es igual a

    \[10^{n}A_n+10^{n-1}A_{n-1}+\ldots+10 A_1+ A_0.\]

Trabajando módulo 9, todos los 10 son 1, así que

    \[n=10^nA_n+\ldots+A_0\equiv A_n + A_{n-1}+\ldots+A_0.\]

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

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

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

Solución. Vamos a estudiar al número módulo 1001. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda

    \[515, 514, 513, 512, 1\]

y hacemos la suma alternada

    \[515-514+513-512+1=3.\]

Por el tercer criterio de divisibilidad, tenemos que n\equiv 3 \pmod{1001}. Notemos que 1001=7\cdot 11 \cdot 13, de modo que n\equiv 3 \pmod{13}. Así, el residuo al dividir n entre 13 es 3.

\square

En general, tenemos lo siguiente.

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

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

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

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

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

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

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

\square

Más ejemplos

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

Usa la paridad

HeuristicasLos números enteros pueden ser pares o impares, dependiendo de si son divisibles entre dos o no. Más aún, se van alternando uno y uno. Además, es muy sencillo saber cómo es la paridad de la suma de dos números o bien de su producto si sabes la paridad de esos números. Estas ideas pueden parecer muy básicas, pero ayudan en una gran cantidad de problemas y son una introducción a los invariantes.

Cuando en un problema observamos nada más la paridad, estamos cubriendo una gran cantidad de casos nada más analizando pocos. En estos videos vemos cómo se aplica la idea de paridad en varios problemas de tableros, juegos, álgebra y teoría de números.

Ir a los videos…

Busca una contradicción

HeuristicasTerminamos esta serie de técnicas de resolución de problemas con una de las técnicas más finas y más usadas en las matemáticas: las pruebas por contradicción.

La idea es la siguiente. Por un momento suponemos que lo que queremos demostrar es falso. Después trabajaremos haciendo todo lo demás correctamente. La idea es llegar a una contradicción con las hipótesis del problema, o bien a algo que sabemos que es imposible. De esta forma, sabemos que debe haber un error en la demostración de eso imposible. Y como lo único que hicimos mal fue suponer que lo original era falso, debemos tener que en realidad es verdadero.

En estos videos veremos varios ejemplos de este argumento para acostumbrarnos. Es súper útil pensar en estos argumentos casi automáticamente.

Ir a los videos…