La dificultad de un problema depende del resolutor

Enviado por jmd el 25 de Septiembre de 2015 - 10:34.

En el presente post voy a presentar la solución de un problema de números que se me hizo realmente difícil y no lo pude resolver sin ayuda. Trato también de trasmitir a los lectores de MaTeTaM el modo de razonar de un experto en el problem solving de concurso. El problema es el siguiente:

Demostrar que, para todo entero no negativo k, $$2^{2^{6k+2}}+3$$ es múltiplo de 19.

Demostración (reconstruida a partir de una realizada por JRV en conversación telefónica con el que esto escribe)

Según me lo hizo saber Jesús al final de la conversación, primero vio el problema más general "¿para qué n la expresión $2^n+3$ es múltiplo de 19?" Después de eso, y evocando el Pequeño Teorema de Fermat, se hace evidente --me dijo-- que n debe ser de la forma $18r+4$ (pues, en ese caso, $2^{18r+4}$ es congruente con $1\cdot 2^4$ módulo 19 y el problema quedaría resuelto). (Notemos que de un vistazo el experto ya tiene, en principio, la solución.)

De ahí que, para el problema que nos ocupa, sólo faltaría verificar que $2^{6k+2}$ es congruente con 4 módulo 18. La verificación es la siguiente:

$$2^{6k}\equiv{64^k}\equiv{(54+10)^k}\equiv{10}\pmod{18}$$
Nota: Se usa el hecho de que cualquier potencia de 10 es congruente con 10 módulo 18.

Así que $$2^{6k+2}\equiv{4\cdot10}\equiv{4}\bmod{18}$$
Es decir, $2^{6k+2}=18r+4$ como se quería.

Comentarios

El problema es el número 5 del libro "250 problems in elementary number theory" de Waclaw Sierpinski. Cuando tuve acceso al libro (lo atacho en pdf) me dije "este problema no debería ser difícil" --pues pertenece a la sección "Divisibility of Numbers"-- y me puse a resolverlo.

Pero después de muchos intentos no logré ver la ruta hacia la solución. Así que le pedí ayuda a Jesús Rodríguez Viorato (ex-olímpico internacional) quien lo resolvió en tres patadas. Le pedí entonces que me explicara la lógica de su solución (sobre todo la parte del módulo 18) y ... pues se trataba del Pequeño Teorema de Fermat... Elemental ¿no es cierto? Pues sí pero no para mí que abordé el problema con la idea de que solamente se necesitaban los conocimientos de divisibilidad que están más acá de los teoremas famosos...

Ahora bien, viendo la solución de Jesús y después de haberla entendido puedo conjeturar que sus ojos de experto en el problem solving de concurso vieron Fermat al ver el exponente $2^{6k+2}$ y la necesidad de simplificar el problema. Porque, de nuevo, en un análisis postsolución, Fermat se puede ver como una técnica para encontrar el inverso de un número módulo un primo (¿cuál es el inverso de 2 módulo 19?).

Y una regla más general es:

"si trabajas módulo un primo p, toma los exponentes módulo p-1".

Por ejemplo, para encontrar el residuo de $2^{402}$ en la división entre 11 tomamos el exponente 402 módulo 10 (que es 2). Entonces $2^{402}=2^{400+2}$ y se hace evidente que el residuo buscado es 4.

Los saluda
jmd

PD: Como se puede verificar en el libro atachado, la solución del Sierpinski oculta la lógica del PTF en la resolución del problema. Se trata de la clásica reticencia de una didáctica de las matemáticas orientada a matemáticos --usual en los libros clásicos.