Sumando potencias

Enunciado

Es evidente que lo que pretende este problema es que descompongamos esta suma en un producto que sea expresable con números enteros. Tal vez, lo más interesante sea que las potencias de 2 se puedan expresar como si se tratase de una única variable, que podría ser 2^m. Supongo que todo el mundo sabe que 2^5m = (2^m)⁵, así que el número que hemos de descomponer se puede expresar como un polinomio x⁵ + x + 1, donde x = 2^m.

Valor X	Polinomio	Factorización
2 = 21	35	5*7
3	247	13*19
4 = 22	1029	3*343 = 21*49 = 7*149
5	3131	31*101

Tabla de valores

Aquí es donde te puedes encontrar con un dilema. ¿Se podrá descomponer siempre el polinomio, o se trata de una propiedad exclusiva de las potencias de 2? En el caso de una competición como la olimpiada, en la que el tiempo cuenta, puede tratarse de una manera de hacerte perder el tiempo. Calculemos unos cuantos valores para distintas x, que puede que nos sean de utilidad. Puedes verlos en la tabla del lateral.

La idea es utilizar los valores calculados para encontrar polinomios útiles para hacer la división. Evidentemente, el polinomio x⁵ + x + 1 no es divisible por x + 1 ni por x - 1, es decir, no tiene divisores enteros de grado 1 (si los tuviese, ya sabes que el término independiente dividiría al término independiente de x⁵ + x + 1, es decir, a 1).

Si vamos a probar a dividirlo con polinomios de grado 2, podemos probar más rápidamente si probamos valores de los que tenemos en la tabla, ya que tiene que proporcionar uno de los factores. El polinomio x² - 1 cumple para 2, pero falla para los demás. Los polinomios x² + 1 y x² + x - 1 no cumplen ni siquiera el 2. Sin embargo, x² + x + 1 proporciona valores que sí aparecen en la tabla: para 2, el 7, para 3, el 13, para 4, el 21, y para 5, el 31. Demasiada casualidad.

Si realizamos la división entre polinomios, observaremos que x⁵ + x + 1 = (x² + x + 1)(x³ - x² + 1), de forma que esta es la factorización que buscamos.

Es decir, que 2^5m + 2^m + 1 = (2^2m + 2^m + 1)(2^3m - 2^2m + 1). Además, es sencillo comprobar que ambos factores son mayores que 1, ya que 2^3m es mayor para todo m positivo que 2^2m.

Observa que en problemas de este tipo no siempre es útil convertirlo en un polinomio, ya que hay veces que la factorización podría depender realmente de que los sumandos sean una potencia de 2.