Con referencia al problema de los Libre de cuadrados [1], me gustaría decir dos o tres cosas que podrían ser útiles para los novicios en concursos. El problema que planteó Jesús --y que resolvió Zzq-- sobre los libres de cuadrados, es un buen ejercicio en demostración matemática y tiene el nivel de concurso interestatal e incluso de un fácil de un nacional. (Los novicios harían bien en irse familiarizando con los usos y costumbres de la demostración matemática y es para ellos que va dedicado este post.)
Supongamos que un entero positivo $ n $ se descompone en dos sumandos también enteros positivos $a, b$ ($n=a+b$), y que esa descomposición cumple la restricción adicional de que $ab$ es múltiplo de $ n $. ¿Qué se puede inferir de $ n $ a partir de esa descomposición? (La respuesta es que $ n $ debe tener un primo a una potencia mayor que 1 en su descomposición canónica. Pero veamos cómo se puede llegar a ella.)
Bueno, en primer lugar digamos que la descomposición canónica de un número con frecuencia es útil para problemas en que casi no se sabe nada del número. Porque es una propiedad que todos los enteros cumplen. Aquí la vamos a usar de manera no tan canónica, pues vamos a apartar todos los factores primos de $ n $ a la primera potencia y a dejar en un $ N $ el producto de esos mismos primos elevados a alguna potencia desconocida.
Sea pues $n=pq... N$, donde $p, q,$ etc son los primos diferentes a la primera potencia y $ N $ el producto de esos mismos primos elevados a una potencia mayor o igual que cero. Si $ n $ está libre de cuadrados entonces $N=1$ (todas las potencias son cero), de otra manera $ N$ es uno de los primos $p, q,$ etc. o bien el producto de dos o más primos de entre los mismos $p, q,...$ (eso es fácil de imaginar pero, para mantenerse en lo concreto, el novicio haría bien en seguir el argumento con un ejemplo --como $n=2009$).
De esta manera, según la hipótesis de que $ab$ es múltiplo de $n, p$ divide a $ab, q$ divide a $ab$, etc. De aquí que $p$ divide a $a$ o $p$ divide a $b$ ($p$ divide a al menos uno de los dos factores). Pero la hipótesis de que $n=a+b$ nos lleva a concluir que $p$ divide a ambos factores, $q$ divide a ambos factores, etc. Se sigue que $ab$ puede ser factorizado como $ab=p^2q^2...M$, y $n=a+b$ puede ser factorizado como $n=a+b=pq...(a'+b')$, donde ya todos los factores primos diferentes se han factorizado. Es decir, $a'+ b'$ ya no tiene factores primos distintos de $p, q$, etc.
Pero $a'+b'$ es un entero positivo y, por tanto, debe tener factores primos. Se concluye que $a'+b'$ es igual a $p$,o a $q$, etc. o bien es producto de dos o más primos de entre los distintos ya factorizados. Y esto se ve muy claro si uno imagina el cociente $ab/n$ con numerador y denominador ya factorizados: $ab=p^2q^2...M$ y $n=pq...(a'+b')$. Cancelamos lo que es evidente que se puede cancelar... pero nos falta por cancelar $a'+b'$... ¿con qué lo cancelamos?
La conclusión de que $a'+b'$ es uno de los primos $p, q$, etc. o el producto de dos o más de ellos, solamente tiene el valor de una conjetura. Pues este argumento no es lo suficientemente formal para pasar como una demostración matemática (y por ello se prefiere la prueba por contradicción).
Pero sí que es muy útil para generar el método de descomposición de un $ n $ (que no está libre de cuadrados) en $n=a+b$ y $ab$ múltiplo de $ n $. Porque lo que el argumento sugiere es que se tome uno de los primos repetidos (o el producto de dos o más repetidos) en la descomposición canónica de $ n $ y se parta en dos sumandos, $a'$ y $b'$.
Ejemplo: si $n=p^2N$ (con uno que se repita es suficiente, $ N $ puede tener más primos $p$ como factores y otros primos más) entonces parto $p$ en $p=a'+b'$ y ¿qué tengo ahora? Tengo $n=(a'+b')pN=a'pN+b'pN$, con $a$ el primer sumando y $b$ el segundo. Pero entonces $ab=a'b'p^2N^2=a'b'N(p^2N)=a'b'Nn$. ¿Lo vieron? (Y se puede decir más. La descomposición de $p$ se puede hacer de $p-1$ formas: si $m$ está en $\{1,2,...,p-1\}$ entonces $a'=p-m$ y $b'=m$ hace el truco, porque ambas partes son positivas y suman $p$.)
Este ejemplo (o cuasiejemplo, dado que no es un caso particular en sentido estricto) es lo suficientemente formal para pasar como una prueba de la proposición "si $ n $ no está libre de cuadrados, entonces existen $a, b$ enteros positivos tales que $n=a+b$, con $ab$ múltiplo de $ n $". Y tiene la ventaja de ser una demostración constructiva (está mostrando cómo hacer la descomposición). La demostración de su conversa (recíproca) es la que presenta más problemas y parece ser que no se puede evitar el argumento por contradicción.
Digamos, para finalizar, que el problema que planteó Brandon --ya depurado después de la corrección de Zzq-- tiene el nivel de un fácil de un concurso estatal. Ya depurado, por ejemplo, a "encontrar todas las soluciones en enteros positivos $a, b$ de la ecuación diofantina $a+b=2009$ tales que $ab$ es múltiplo de $2009$" sería uno de los fáciles si el concursante conoce el método que arriba comento --de otra manera, el problema es endiabladamente difícil...
Los saluda
jmd
woow! :D eso es muy [4]
eso es muy fascinante :), siempre tuve problemas con los problemas (ataque de redundancia) de "sí y sólo sí" y "demuestra que", pues casi siempre me faltaban considerar casos, o usaba mi hipótesis de manera incorrecta, entre otros errores.
es muy interesante el post :D, como muchos otros (muchísimos otros) que ha escrito :D, gracias! :D