Este problema es un buen ejercicio en inducción matemática, pero también en el uso de las leyes de los exponentes.
El método expuesto de manera abreviada en la solución facilita el uso de la inducción y es clásico en problemas de este tipo donde se tiene que probar divisibilidad entre un módulo $m$ de una función $f(n)$.
La idea clave es expresar la diferencia $f(n+1)-f(n)$ en términos de $n$, digamos que resulte $f(n+1)-f(n)=g(n)$. Si logramos demostrar que $g(n)$ es múltiplo de $m$, el problema está resuelto. Pues, por hipótesis de inducción $f(n)$ es múltiplo de $m$ y tal divisibilidad se transfiere a $f(n+1)$ (se transfiere de los sumandos a la suma --como en el algoritmo de Euclides).
Pero quizá la verdadera dificultad del problema sea la manipulación de las potencias. Por ejemplo, al llegar a $g(k)=16^{2^k}-2^{2^k}$ el resolutor se preguntará ¿Y ahora? ¿Cómo se juega esto?
(El problema me lo planteó arbiter --aka Bernardo Tovías--, y a pesar de que lo ví muy simple de resolver con el método antedicho, al llegar a este punto me hice las preguntas anteriores.)
Pero puesto que es seguro que $g(k)=16^{2^k}-2^{2^k}$ debe ser múltiplo de 7, el resolutor debe insistir en su estrategia y buscar la factorización. Pero la factorización no es trivial, a pesar de que es claro que $2^{2^k}$ tiene que ser un factor. Y es notrivial porque requiere un manejo mucho más fino de los exponentes que el que se aprende en la escuela.
La pregunta clave es ¿cuánto debe ser $x$ para que $2^{2^k} \cdot x$ sea igual a $2^{2^{k+2}}$? Y, bueno, despejando la $x$ se obtiene que es $2^{(2^k)\cdot3}$. Al final, puesto que el 8 es equiresidual con el 1, tuve que irme por la vía corta de las congruencias.
Los saluda
jmd
PD: Se deja como ejercicio para el cibernauta interesado en las matemáticas de concurso el resolver el problema directamente con aritmética modular.
Solución alternativa --identificando la estructura de la diferencia de cubos:
En $ f(k)= 4^{2^k}+2^{2^k}+1= (2^{2^k})^2+2^{2^k}+1$ se puede identificar la estructura $z^2+z+1$ --con $z=2^{2^k}$. Esto sugiere trabajar la factorización $(z^3-1)=(z-1)(z^2+z+1)$.
Puesto que, como se vio en la solución oficial, $2^{(2^k)\cdot3}-1=(8^{2^k}-1)$ es múltiplo de 7, entonces bastaría con demostrar que $2^{2^k}-1$ es primo con 7 (no contiene un factor 7).
Pero esto es fácil de ver, pues si 7 fuese un factor de $2^{2^k}-1$, en las factorizaciones sucesivas como diferencia de cuadrados, eventualmente debería aparecer el factor $2^3-1$. Pero 3 no es potencia de 2. Por tanto el factor 7 no puede aparecer.
De aquí que, como en $(z^3-1)=(z-1)(z^2+z+1)$, el lado izquierdo es múltiplo de 7 y $z-1$ es primo con 7, se sigue que $(z^2+z+1)$ es múltiplo de 7.
Enviado por jesus el 18 de Agosto de 2010 - 13:38.
Me queda la duda sobre esta afirmación:
Pero esto es fácil de ver, pues si 7 fuese un factor de , en las factorizaciones sucesivas como diferencia de cuadrados, eventualmente debería aparecer el factor .
Entiendo que, de la factorización sucesivas como diferencias de cuadrados, se desprende algo así:
De aquí, con tal vez algo de inducción, se pueda llegar a que: 2^{2^{k}} \equiv \left\{\begin{array}{rl} 2 & \text{si } k \textrm{ es par}\\ 4 & \text{si } k \textrm{ es impar} \right. \end{array} \pmod{7} 4^{2^{k}} \equiv & \left\{\begin{array}{rl} 4 & \text{si } k \textrm{ es par}\\ 2 & \text{si } k \textrm{ es impar} \right.\end{array} \pmod{7}
Entonces, usando éstas dos identidades (\ref{gen_1}) y (\ref{gen_2}) se conluye inmediatamente que:
Bueno, quizá lo que quise decir es que $2^{2^n}-1$si va a ser múltiplo de 7 para algún n, donde hay que buscar es en los factores $2^{2^k}-1$ porque los de la forma $2^{2^k}+1$ son todos primos con 7.
Y, bueno, de paso se me ocurre que estos son dos problemitas básicos de números que podemos poner en matetam:
1) Demostrar que para todo $k$ entero no negativo, la función $f(k)=2^k+1$ no contiene ningún factor 7 (es primo con 7).
2) Encontrar todos los enteros no negativos para los cuales $2^k-1$ es múltiplo de 7.
Este problema es un buen
Este problema es un buen ejercicio en inducción matemática, pero también en el uso de las leyes de los exponentes.
El método expuesto de manera abreviada en la solución facilita el uso de la inducción y es clásico en problemas de este tipo donde se tiene que probar divisibilidad entre un módulo $m$ de una función $f(n)$.
La idea clave es expresar la diferencia $f(n+1)-f(n)$ en términos de $n$, digamos que resulte $f(n+1)-f(n)=g(n)$. Si logramos demostrar que $g(n)$ es múltiplo de $m$, el problema está resuelto. Pues, por hipótesis de inducción $f(n)$ es múltiplo de $m$ y tal divisibilidad se transfiere a $f(n+1)$ (se transfiere de los sumandos a la suma --como en el algoritmo de Euclides).
Pero quizá la verdadera dificultad del problema sea la manipulación de las potencias. Por ejemplo, al llegar a $g(k)=16^{2^k}-2^{2^k}$ el resolutor se preguntará ¿Y ahora? ¿Cómo se juega esto?
(El problema me lo planteó arbiter --aka Bernardo Tovías--, y a pesar de que lo ví muy simple de resolver con el método antedicho, al llegar a este punto me hice las preguntas anteriores.)
Pero puesto que es seguro que $g(k)=16^{2^k}-2^{2^k}$ debe ser múltiplo de 7, el resolutor debe insistir en su estrategia y buscar la factorización. Pero la factorización no es trivial, a pesar de que es claro que $2^{2^k}$ tiene que ser un factor. Y es notrivial porque requiere un manejo mucho más fino de los exponentes que el que se aprende en la escuela.
La pregunta clave es ¿cuánto debe ser $x$ para que $2^{2^k} \cdot x$ sea igual a $2^{2^{k+2}}$? Y, bueno, despejando la $x$ se obtiene que es $2^{(2^k)\cdot3}$. Al final, puesto que el 8 es equiresidual con el 1, tuve que irme por la vía corta de las congruencias.
Los saluda
jmd
PD: Se deja como ejercicio para el cibernauta interesado en las matemáticas de concurso el resolver el problema directamente con aritmética modular.
Solución alternativa
Solución alternativa --identificando la estructura de la diferencia de cubos:
En $ f(k)= 4^{2^k}+2^{2^k}+1= (2^{2^k})^2+2^{2^k}+1$ se puede identificar la estructura $z^2+z+1$ --con $z=2^{2^k}$. Esto sugiere trabajar la factorización $(z^3-1)=(z-1)(z^2+z+1)$.
Puesto que, como se vio en la solución oficial, $2^{(2^k)\cdot3}-1=(8^{2^k}-1)$ es múltiplo de 7, entonces bastaría con demostrar que $2^{2^k}-1$ es primo con 7 (no contiene un factor 7).
Pero esto es fácil de ver, pues si 7 fuese un factor de $2^{2^k}-1$, en las factorizaciones sucesivas como diferencia de cuadrados, eventualmente debería aparecer el factor $2^3-1$. Pero 3 no es potencia de 2. Por tanto el factor 7 no puede aparecer.
De aquí que, como en $(z^3-1)=(z-1)(z^2+z+1)$, el lado izquierdo es múltiplo de 7 y $z-1$ es primo con 7, se sigue que $(z^2+z+1)$ es múltiplo de 7.
Los saluda
Me queda la duda sobre esta
Me queda la duda sobre esta afirmación:
Entiendo que, de la factorización sucesivas como diferencias de cuadrados, se desprende algo así:
Lo que no veo, es porqué debe apareces el factor
Seguramente estoy pensando algo mal
Muy padres soluciones, la
Muy padres soluciones, la verdad no se me hubieran ocurrido.
Yo, por lo general, procedo a base de puras congruencias:
En este caso, pues uso las siguientes dos congruencias:
De aquí, con tal vez algo de inducción, se pueda llegar a que:2^{2^{k}} \equiv \left\{\begin{array}{rl} 2 & \text{si } k \textrm{ es par}\\ 4 & \text{si } k \textrm{ es impar} \right. \end{array} \pmod{7} 4^{2^{k}} \equiv & \left\{\begin{array}{rl} 4 & \text{si } k \textrm{ es par}\\ 2 & \text{si } k \textrm{ es impar} \right.\end{array} \pmod{7}
Entonces, usando éstas dos identidades (\ref{gen_1}) y (\ref{gen_2}) se conluye inmediatamente que:
Finalmente, sumamos uno y concluimos.
Acepto la tacha y me
Acepto la tacha y me explico:
Bueno, quizá lo que quise decir es que $2^{2^n}-1$si va a ser múltiplo de 7 para algún n, donde hay que buscar es en los factores $2^{2^k}-1$ porque los de la forma $2^{2^k}+1$ son todos primos con 7.
Y, bueno, de paso se me ocurre que estos son dos problemitas básicos de números que podemos poner en matetam:
1) Demostrar que para todo $k$ entero no negativo, la función $f(k)=2^k+1$ no contiene ningún factor 7 (es primo con 7).
2) Encontrar todos los enteros no negativos para los cuales $2^k-1$ es múltiplo de 7.
Los saluda