Problema 6. 29a Olimpiada Mexicana de Matemáticas

Observa que basta demostrar que $p^2$ no divide a $n$ para todo primo $p$. Esta propiedad es conocida como Libre de cuadrados.

Observa que $n$ debe ser par (de lo contrario será f(n) < 0 )

Ahora bien, demuestra que si $n = p^\alpha m$ donde $p$ es un factor primo impar de $n$ y $alpha$ es su exponente máximo tal que $p^\alpha$ divide a $n$, entonces $$f(n) = (1+ p + p^2 +\dots + p^\alpha)f(m)$$

Observa entonces que si $n = 2^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k ^{\alpha_k}$ es la descomposición prima de $n$, entonces $$f(n) = (-1 + 2+ 2^2 + \cdots + 2^{\alpha_1})(1+ p_2 + p_2^2 +\dots + p_2^{\alpha_2}) \cdots (1+ p_k + p_k^2 +\dots + p_k^{\alpha_k})$$

Observa entonces que:

• $\alpha_1 = 2$
• $1+ p_i + p_i^2 +\dots + p_i^{\alpha_i}$ debe ser potencia de 2.

Demuestra que la siguiente proposión:

Para todo primo impar $p$, el número $1+p + p^2 +\cdots + p^n$ es potencia de 2, sólo cuando $n=1$, es decir, cuando $n>1$ es imposible.

Para demostrar lo anterior puedes hacer lo siguiente:

• Supon que existe un primo $p$ impar y un entero $n>1$ tal que $1+p + p^2 +\cdots + p^n$ es potencia de $2$.
• Consiera el mínimo de tales números $n$,
• Demuestra que $n$ es impar:  $n=2m+1$
• Utiliza las siguientes dos factorizaciones para demostrar que $1 + p + p^2 + \cdots + p^m$ debe ser también potencia de 2.
  • $1 + p + p^2 + \cdots + p^{2m+1} = (p+1)(1+p^2+p^4+\cdots + p^{2m}$
  • $(1+p^2+p^4+\cdots + p^{2m}) = (1+p+p^2+\dots + p^m)(p^{m+1} + 1)$
• Utiliza la minimalidad de $n$  para demostrar que $m=1$ y por lo tanto $n=3$
• Demuestra que $1 + p + p^2+p^3$ no puede ser una potencia de 2
• Concluye