Decimos que un entero positivo es básico si no existe ningún primo $p\geq 5$ que lo divida. Demostrar que todo entero positivo se puede escribir como la suma de varios números básicos, tales que ninguno de ellos es divisor de otro.
El problema lo reescribimos como "Probar que todo entero positivo puede ser escrito como la suma de uno o más enteros positivos de la pinta $2^x3^y$ tales que no haya un término que divida a otro"... Ahora si, manos a la obra:
Vamos a tirar una inducción fuerte para el problema... ¿Qué es una inducción fuerte? Es como una inducción normal pero con esteroides. ¿En qué consiste se preguntarán? En lugar de suponer que algo vale para $n$ y probar entonces que vale para $n+1$, suponemos que vale para TODOS los enteros positivos hasta $n$ y probamos que entonces va a valer para $n+1$. Nuestro caso base trivial es $1=2^03^0$.
Supongamos ahora que el enunciado es cierto hasta un $n$ entero positivo... Vamos a probar que entonces es cierto para $n+1$.
Si $n+1$ es impar, definimos $x$ como el máximo entero positivo tal que $3^x \leq n+1$. Si $n+1$ es potencia de $3$ estamos. Supongamos entonces que $n+1$ no es potencia de $3$, como es impar, $n+1>\frac{n+1-3^x}{2}$ y que encima es entero! Entonces, por nuestra hipótesis inductiva, existen $a_1,...,a_i$ que cumplen el enunciado, es decir $\frac{n+1-3^x}{2}=a_1+...+a_i$ y que no hay dos que se dividan entre ellos. Despejando $n+1$ nos queda $n+1=3^x+2a_1+...+2a_i$. Por nuestra hipótesis, como los $a_j$ no se dividían entre ellos, entonces los $2a_j$ tampoco van a hacerlo. Supongamos que $3^x$ divide a algún $2a_j$, entonces $3^x$ divide a $a_j$, pero entonces, $3^x \leq a_j$, de donde $n+1=3^x+2a_1+...+2a_i \geq 3^x+2a_j \geq 3^x+2.3^x=3^{x+1}$, absurdo por como habíamos definido $x$, luego $3^x$ no divide a ningún $a_j$. Por otro lado, como $2a_j$ es par, nunca va a dividir a $3^x$, luego, si $n+1$ es impar escribimos $n+1=3^x+2a_1+...+2a_i$ y estamos.
Por último, si $n+1$ fuera par, $n+1> \frac{n+1}{2}$ que encima es entero, por lo que podemos escribir $\frac{n+1}{2}=a_1+...+a_i$ con los $a_i$ cumpliendo el enunciado. Despejando nos queda $n+1=2a_1+...+2a_i$, pero claramente si los $a_j$ no se dividían entre ellos, los $2a_j$ tampoco lo hacen... Luego, Nuestra induccionaza está terminada y el problema completo $\blacksquare$
