Encuentra los polinomios

Vamos con el problema de esta semana:

Encontrar todos los polinomios $p(x)$ con coeficientes enteros que verifican que $p(n)$ divide a $2^n-1$ , para todo $n\in\mathbb{N}$ .

A por él.

62 comentarios

Trackback | 15 Nov, 2010

Tweets that mention Encuentra los polinomios | Gaussianos -- Topsy.com
josejuan | 15 de November de 2010 | 09:52

Buff… ni idea, pero por mi que no quede

p(x)=1 es uno de ellos.

Os dejo los demás, que no quiero acaparar…
zelig | 15 de November de 2010 | 11:26

(Comentario eliminado por el autor; argumento erróneo).
mimetist | 15 de November de 2010 | 12:40

Voy justo de tiempo, pero ¿esta pregunta no es equivalente a un problema no resuelto? (a ver si estoy metiendo la pata como cada vez que participo xD)

Por reducción al absurdo:
Sea $P(n) = a_k n^k + \ldots + a_0$ tal que divide a $2^n - 1 \; \forall n\in\mathbb{N}$ entonces, en concreto, P(n) debe dividir a todos los primos de la secuencia $2^n -1$ (los primos de Mersenne)

Obviamente los números primos no son divisibles más que por 1 y por si mismos, luego: o bien $P(n) = 1$ (el caso trivial), o bien $P(r) = 2^r - 1$ (una fórmula polinómica para hallar ¡¡todos los primos de Mersenne!!).

Podríamos formar así un sistema de r ecuaciones con al menos r incógnitas (que serían los coeficientes $a_i$ )… de esta manera, si el sistema es compatible determinado obtendríamos una solución o infinitas si fuese indeterminado.

Sin embargo, si hubiera infinitos números primos de Mersenne, lo cual es un problema abierto, dicho sistema necesitará una infinidad de ecuaciones con polinomios que tengan una infinidad de términos para que el sistema pueda ser compatible. Por lo tanto, si hubiese infinitos primos, no podría existir dicho polinomio… salvo el del caso trivial P(n) = 1 para todo n.

Así que yo me uno a josejuan y me quedo con la respuesta trivial.
Trackback | 15 Nov, 2010

Bitacoras.com
vayapordios | 15 de November de 2010 | 15:14

Creo que sólo hay uno, el que ya han apuntado de P(x) = 1 La secuencia de los divisores de cada término de la sucesión parece muy irregular, demasiados puntos (infinitos) para poder ser ajustados con un polinomio.
josejuan | 15 de November de 2010 | 16:39

Uhm… pues yo diría que ese polinomio existe ( p(n)=2^n-1 para todo n ), no se muy bien como se comportaría en el infinito, pero para cualquier n natural (que es lo “único” que exige el problema) parece claro que tal polinomio existe.

Si no hay una expresión general, es obvio que únicamente podemos extender su construcción (ej. ecuaciones=incógnitas), pero que para todo n existe parece claro.

¿Existirá una expresión general?
josejuan | 15 de November de 2010 | 16:53

Bueno… igual precisamente la restricción “fatal” podría estar precisamente ahí, en el infinito. El razonamiento sería:

1. p(x) debe dividir a todo 2^n-1 (en p(n))

2. p(x) por tanto ha de tener infinitos términos, si no fuera así, todos los 2^n-1 con n>Q serían compuestos para algún Q>43112609

3. aceptado que tiene infinitos términos, los coeficientes han de ser n^-n o menores (para que converja la serie)

4. pero como debe ser que p(n+1) = p(n) + 2^n, no puede tener unos coeficientes tan pequeños

Por tanto, no existe el polinomio (si asumimos que sí existen infinitos primos de mersenne).

(no se…)
josejuan | 15 de November de 2010 | 17:02

Bueno, para [2] no creo que haga falta recurrir a los primos de mersenne…
Francisco | 15 de November de 2010 | 17:27

Vaya, por una vez llego cuando el problema no está resuelto. Y naturalmente, ni idea de por dónde meterle mano. Pero… leidas las respuestas anteriores, el problema debe estar en el infinito, en efecto. Es decir, es trivial que para un n_0 dado, sí que existe un polinomio (único si exigimos grado n_0) que verifica que p(n)=2^n-1 si n<n_0 (es un problema de interpolación de toda la vida, vamos).

Se me ocurriría coger la fórmula de interpolación correspondiente y ver qué pasa si la n tiende a infinito, pero no sé qué se podría sacar de ahí…
Francisco | 15 de November de 2010 | 17:30

Eliminado, me salté una condición. Sorry.
orlin | 15 de November de 2010 | 17:44

Eliminado
Dani | 15 de November de 2010 | 22:07

Bueno, tenemos un numero arbitrario de ecuaciones de la forma
$c_1a_0 + c_1a_1 + c_1 a_2 + \cdots + c_1 a_N = 2 -1$
$c_2a_0 + (2c_2) a_1 + (2^2c_2) a_2 + \cdots + (2^Nc_2)a_N = 2^2 -1$
$c_3a_0 + (3c_3) a_1 + (3^2c_3) a_2 + \cdots + (3^Nc_3)a_N = 2^3 -1$
$\vdots$
$c_ka_0 + (kc_k) a_1 + (k^2c_k) a_2 + \cdots + (k^Nc_k)a_N = 2^k -1$
$\vdots$
Pienso que no seria demasiado dificil manipular estas ecuaciones algebricamente para demostrar que para ninguna sucesion $\{c_n\}_{n \in \mathbb{N}}$ existe una solucion $(a_0,a_1,\ldots, a_N )$ (en plan operaciones filas/columnas, quizas reduciendo modulo algo, o cualquier cosa del estilo), pero sinceramente no parece demasiado estimulante hacer el calculo. Puede que haya alguna manera mas elegante de hacerlo.
Dani | 15 de November de 2010 | 22:08

(ninguna solucion excepto la trivial, claro)
M | 15 de November de 2010 | 23:07

Por cierto, si se me permite la gracia, he encontrado otro polinomio que resuelve el problema: $p(x)=-1$ !! Ahora sí que no hay más…
JuanPablo | 16 de November de 2010 | 00:38

Dani, qué rápido crecería ese polinomio, verdad?
Octavio | 16 de November de 2010 | 01:07

Encontré otro: $p(x)= 1+\prod (i-x)$ ( $i$ está en los naturales, sólo que no supe cómo ponerlo).
Éste cumple porque $p(n)=1$ para todo $n$ . De hecho $p(x)= \pm1\pm \prod (i-x)$ cumple con lo que se busca.
Dani | 16 de November de 2010 | 07:29

El crecimiento del polinomio no es claro si no conocemos la descomposicion de $2^n -1$ en primos para $n$ grande, y este es un problema abierto. Por otra parte, Octavio, el “polinomio” que propones no es un polinomio porque tiene infinitos terminos, y solo llamamos polinomio a una expresion del tipo $p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots + a_1x + a_0$ . M, ves una manera facil de resolver esto y te estas callando para dar una oportunidad a los pobres mortales , o tampoco lo ves tu?
josejuan | 16 de November de 2010 | 09:59

“…no existe polinomio que crezca tan rápido…”

¿uh?, alguna otra restricción habrá que meter (como que tiene infinitos términos y que debe converger), porque sino, un polinomio puede crecer tan rápido como se quiera.
Gulliver | 16 de November de 2010 | 11:50

Borro lo que he puesto, que no me convence.
Omar-P | 16 de November de 2010 | 13:38

Recordemos que los números primos de Mersenne son de la forma 2^p – 1, donde p es primo. La sucesión comienza con: 3, 7, 31, 127, 8191, 131071, 524287…
Antonio QD | 16 de November de 2010 | 14:14

Borrado por el autor.
mimetist | 16 de November de 2010 | 14:24

Madre mía, no había visto tantos comentarios borrados en ningún otro post xD

Nos está costando ¿eh?
Antonio QD | 16 de November de 2010 | 15:06

Buenos Días

Si existe el polinomio pedido, las raices de este polinomio $p(n)$ deben ser también raices de $2^n -1$ .

Las raices de $2^n - 1$ son del tipo $\frac {2 \pi k \i} {\log 2}$ donde $k \in \mathbb{Z}$ . Los posibles factores de $p(n)$ son entonces $(n-1)$ y $(n^2 - \frac {4 \pi^2 k^2} {(\log 2)^2})$ . Si $p(n) \in \mathbb{Z}[n]$ , entonces es necesario que su termino independiente, que es de la forma $\pm \frac {4^l \pi^{2l}k^{2l}}{(\log 2)^{2l}}$ pertenezca a $\mathbb{Z}$ . Esto para todo $l \ne 0$ significa que $\frac{\pi}{\log 2}$ debería ser algebraico. Si podemos demostrar que $\frac{\pi}{\log 2}$ es transcendente, entonces el único posible polinomio que divide a $2^n - 1$ es de la forma $(n-1)^s$ donde $s \in \mathbb{N}$ y por una cuestión de paridad este único polinomio es posible cuando $s=0$ .

¿Quién se atreve a demostrar que $\frac{\pi}{\log 2}$ es transcendente?

Un Saludo
Manzano | 16 de November de 2010 | 15:55

Bueno, aquí va mi intento (en lo que sigue, el cero se excluye de los números naturales).

Usaremos la siguiente propiedades:

1) Dado un polinomio $P(x)$ con coeficientes enteros y dados $a,b\in\mathbb{Z}$ distintos, se cumple que $b-a$ divide a $P(b)-P(a)$ (es muy fácil de probar puesto que $b-a$ divide a $P(b)-P(a)$ como polinomio de dos variables).

2) Dados números naturales $c$ y $d$ , $2^c-1$ divide a $2^{cd}-1$ (también es fácil de probar factorizando el polinomio $x^d-1=(x-1)P(x)$ para cierto polinomio $P(x)$ y haciendo $x=2^c$ .

Una vez visto esto, supongamos que $P(x)$ cumple las condiciones del enunciado y lleguemos a que ha de ser constante. Para ello, consideremos $m,n\in\mathbb{N}$ dos números naturales y observemos que, en vista de (1), $mn-n$ divide a $P(mn)-P(n)$ y, según (2) y la propiedad del enunciado, si $P(mn)-P(n)$ es distinto de cero, entonces divide a $2^{mn}-1$ . Hemos probado así la siguiente propiedad:

3) Si $P(x)$ cumple la propiedad del enunciado, dados $m,n\in\mathbb{N}$ tales que $P(mn)-P(n)\neq 0$ , se cumple que $mn-n$ divide a $2^{mn}-1$ .

Ahora bien, si $P(x)$ es constante, es obvio que ha de ser $P(x)=1$ o bien $P(x)=-1$ , como se ha comentado en otros posts. Si $P(x)$ no es constante, entonces existirá un $x_0$ tal que $P(x)$ es una función estrictamente monótona (creciente o decreciente) para $x\geq x_0$ . Por tanto, tomando $n\in\mathbb{N}$ con $n\geq n_0$ y $m=2$ en (3), tendremos que $P(2n)-P(n)$ no se anula y, por tanto, $mn-n=n$ divide a $2^{2n}-1$ para $n\geq x_0$ y esto es una contradicción ya que no se cumple (por ejemplo) para $n$ par.

Hemos demostrado (si no hay ningún error) que los únicos polinomios que cumplen la propiedad son los constantes $\pm 1$ .
Omar-P | 16 de November de 2010 | 16:22

La sucesión de números naturales comienza con 1, 2, 3, 4…
La sucesión que comienza con 0, 1, 2, 3, 4… se denomina “enteros nonegativos”.
Andor | 16 de November de 2010 | 16:38

Lo de que los Naturales empiecen con el 0 o con el 1 depende del autor, para mi maestra de Álgebra los Naturales empezaban con el 0.
M | 16 de November de 2010 | 17:56

Hola Manzano, no veo clara la propiedad (3). ¿Podrías explicarlo con más detalle?

Lo que no veo es cuando indicas “y, según (2) y la propiedad del enunciado, si $P(mn)-P(n)$ es distinto de cero, entonces divide a $2^{mn}-1$ .”

No sé si has razonado del siguiente modo:

$P(mn)$ divide a $2^{mn}-1$ ;

$P(n)$ divide a $2^{n}-1$ , que a su vez divide a $2^{mn}-1$ ;

Finalmente, $P(mn)-P(n)$ divide a $2^{mn}-1$ (lo cual no es cierto en general: toma por ejemplo $3|15$ , $5|15$ ).
Manzano | 16 de November de 2010 | 18:08

Hola M, efectivamente ha sido un lapsus mental. Gracias por detectarlo, mi demostración no es correcta. Si tengo otro rato, intentaré pensar más el problema.
gaussianos | 17 de November de 2010 | 00:22

Vaya, por fin nos encontramos con un problema cuya solución no aparece en las primeras 3 o 4 horas de su publicación . Ánimo gente, no desesperéis.
Gulliver | 17 de November de 2010 | 16:07

Creo que tengo una demostración de que los únicos polinomios que cumplen las condiciones son p(x) = 1 y p(x) = -1, pero es algo larga y no me extrañaría que se hubiesen colado errores en algún paso. Seguro que hay alguna otra demostración más corta y bonita, pero no he dado con ella. Voy a ir poniéndola poco a poco.

Para empezar observar que si p(x) es solución, -p(x) también lo es. Bastará con encontrar uno de ellos, el que es positivo para x suficientemente grande, y el otro saldrá por simetría.

El método que he encontrado consiste en demostrar que todos los enteros no negativos son raíces de p(x) – 1. El único polinomio que tiene infinitas raíces es el polinomio nulo p(x) – 1 = 0, así sale la solución p(x) = 1. La otra sale haciendo la transformación p(x) -> -p(x).
Gulliver | 17 de November de 2010 | 16:37

Empiezo demostrando que x=0 es raíz de p(x) – 1. Supondré que p(x) cumple que siempre es positivo para x suficientemente grande, porque si no siempre podría coger -p(x) que lo cumpliría.

Si n es primo, los divisores primos $q$ de $2^n-1$ cumplen $q \equiv 1$ módulo n. Ver teorema 3. Los divisores positivos no primos de $2^n-1$ son producto de potencias de divisores primos, luego también serán congruentes con 1 módulo n.

Si $p(x) = a_k x^k + \dots + a_1 x + a_0$ y $n$ es un número primo mayor que $a_0$ y suficientemente grande para que $p(n)$ sea positivo, $p(n)$ es divisor de $2^n-1$ , de modo que $a_0 \equiv p(n) \equiv 1$ módulo n, y al ser $n > a_0$ , $a_0 = 1$ .

$x = 0$ es raíz de $p(x) - 1 = a_k x^k + \dots + a_1 x$ .
Gulliver | 17 de November de 2010 | 17:03

Como $x=0$ es raíz de $p(x) - 1$ , $x$ divide como polinomio a $p(x) - 1$ .

Para $x=1$ , $p(1)$ divide a 1, luego $p(1)$ solo puede ser 1 o -1.

Si p(1) = 1, $x=1$ es raíz de $p(x) - 1$ y $x-1$ divide como polinomio a $p(x) - 1$ .

Si p(1) = -1, $x=1$ es raíz de $- p(x) - 1$ y $x-1$ divide como polinomio a $- p(x) - 1$ .

O bien $x-1$ divide a $p(x) - 1$ , o bien $x-1$ divide a $- p(x) - 1$ , pero solo uno de los dos es verdadero y voy a comprobar cual de los dos es.

Para $x=7$ , $p(7)$ divide a 127, luego $p(7)$ solo puede ser -127, -1, 1 o 127.

$x$ divide a $p(x) - 1$ . Para $x=7$ , los únicos valores de $p(x) - 1$ múltiplos de 7 son 0 y 126, los demás los podemos descartar. Estos dos valores son incompatibles con los valores para los que $6$ divide a $- p(x) - 1$ , así que queda demostrado que la única posibilidad es que $x-1$ divide a $p(x) - 1$ y por tanto $x=1$ es raíz de $p(x) - 1$ .

Ahora sabemos que $x (x-1)$ divide a $p(x) - 1$ .
Gulliver | 17 de November de 2010 | 17:19

Lo que sigue es bastante rutinario, simplemente comprobar los casos particulares de $x=5$ , $x=7$ , $x=2$ , $x=3$ , $x=4$ y $x=6$ , por este orden, y ver que también son raíces de $p(x) - 1$ . Los monomios que dividen al polinomio $p(x) - 1$ se irán acumulando.

Creo que no merece la pena que lo detalle porque es muy simple.

Por ejemplo para $x=5$ , $p(5)$ divide a 31. Por otro lado $x (x-1)$ divide a $p(x) - 1$ , luego 20 divide a $p(5) - 1$ . El único valor posible para p(5) es 1, $x = 5$ es raíz de $p(x) - 1$ y $x (x-1) (x-5)$ divide a $p(x) - 1$ .

El resto de valores sigue la misma lógica de comprobar valores y acumular monomios.
Gulliver | 17 de November de 2010 | 18:06

Con estos casos particulares se demuestra que $\displaystyle \prod_{k=0}^7 (x-k)$ divide a $p(x) - 1$ .

Para el resto de valores no negativos se puede demostar por inducción que $\displaystyle \prod_{k=0}^n (x-k)$ divide a $p(x) - 1$ . Para $n$ entre 0 y 7 ya está demostrado, y lo demostraré para $n \ge 8$ .

Por hipótesis de inducción $\displaystyle \prod_{k=0}^{n-1} (x-k)$ divide a $p(x) - 1$ , luego todos los enteros entre 2 y $n$ son divisores de $p(n) - 1$ . También es divisor $m(n)$ , mínimo común múltiplo de todos los enteros entre 2 y $n$ . $p(n) = m(n) g + 1$ para algún entero $g$ .

$p(n)$ divide a $2^n - 1$ . $2^n - 1 = h ( m(n) g+1)$ para algún entero $h$ .

Hay una bonita demostración de que $m(n) > 2^{n-2}$ para $n \ge 2$ que detallaré más adelante. De momento esto sirve para ver que no puede ser $g h \ge 4$ porque entonces $h ( m(n) g+1) > 2^n - 1$ .

Después habría que estudiar casos particulares para descartar otros valores de $g$ y $h$ . En particular los valores a descartar para $g$ y $g$ son 1, 2 y 3 en combinaciones en que su producto es positivo y menor que 4. Se comprueba haciendo aritmética módulo 8 en la expresión $2^n - 1 = h ( m(n) g+1)$ , sabiendo que $m(n) \equiv 0$ módulo 8 para $n \ge 8$ .

El único valor posible para g es cero, con lo que $p(n) = 1$ , $n$ es raíz de $p(n) - 1$ y $\displaystyle \prod_{k=0}^n (x-k)$ divide a $p(x) - 1$ .
Gulliver | 17 de November de 2010 | 18:14

Me falta demostrar que $m(n) \ge 2^{n-2}$ . La demostración la he visto en Algorithmic Number Theory: Efficient algorithms, escrito por Eric Bach,Jeffrey Outlaw Shallit
lema 8.2.3 en página 208.

Si tengo tiempo más tarde escribiré aquí la demostración.
Gulliver | 17 de November de 2010 | 20:36

Hay una parte de la parrafada de las 18.06 que no es correcta. Voy a corregirla aquí.

$p(n) = g \cdot m(n) + 1$ para algún entero $g$ , pero podré demostrar que $g=0$ . Para ello supondré que $g \ne 0$ y llegaré a una contradicción.

Para $n$ entero mayor que 8, $2^n-1 = h \cdot p(n) = h [ g \cdot m(n) + 1]$ para algún entero $h$ y $m(n)$ es el mínimo común múltiplo de los enteros entre 2 y $n$ .

Si $g \ne 0$ , $h \cdot g$ es positivo. Antes se ha demostrado que $h \cdot g < 4$ .

$m(n) \equiv 0 \pmod{8}$ para $n \ge 8$ . Haciendo aritmética módulo 8, se llega a $h \equiv -1 \pmod{8}$ . Si $h \cdot g < 4$ , $h = -1$ .

Queda $2^n = g \cdot m(n)$ que es imposible por la definición de $m(n)$ y esta es la contradicción que demuestra $g = 0$ .
Gulliver | 17 de November de 2010 | 21:14

Ahora tengo tiempo para poner la demostración de que $m(n)$ el mínimo común múltiplo de los enteros entre 2 y n es mayor que $2^{n-2}$ para $n \ge 2$ .

Hay que considerar la integral $\displaystyle I = \int_0^1 x^m (1-x)^m dx$ para $m \ge 1$ entero. Haciendo la expansión binomial de $(1-x)^m$ se obtiene $I = \displaystyle \sum_{k=0}^m \binom n k \frac {(-1)^{m-k}} {2 m - k + 1}$ . Es una suma de fracciones en la que los denominadores no son mayores que $2 m + 1$ , de modo que $I \cdot m(2m + 1)$ es entero mayor que 1. $m(2m+1) \ge I^{-1}$ .

Por otra parte $x^m ( 1-x)^m \le 4^{-m}$ para $x$ entre 0 y 1, y para algunos x es estrictamente menor. Por tanto I es menor que $4^{-m}$ y $m(2m+1) > 2^{2m}$ .

Si $n = 2 m + 1$ , $m(n) > 2^{n-1} > 2^{n-2}$ .

Si $n = 2 m + 2$ , $m(n) \ge m(2m+1) > 2^{n-2}$ .

Si $n=2$ , $m(2) = 2 > 2^0$ .
M | 17 de November de 2010 | 23:37

Hola Gulliver, estoy mirando tu argumento.

En tu segundo comentario de “17 de November de 2010 | 16:37″ hay un detalle que no me queda claro, y es cuando indicas “de modo que $a_0 \equiv p(n) \equiv 1$ módulo $n$ , y al ser $n > a_0 , a_0 = 1$ .”

En concreto, me parece que estás asumiendo que $a_0>0$ , cosa que en principio no tiene porqué darse, ya que de antemano lo que haces es fijar el signo del polinomio “en el infinito”. Es decir, que lo que debe deducirse es $a_0=1-k\cdot n$ , con $k$ entero negativo.

No digo que la propiedad $x|p(x)-1$ no pueda ser cierta, pero ese detalle creo que hay que solventarlo, ya que luego se usa esta última propiedad para deducir que cada factor $x-a$ ( $a\in\mathbb{Z}$ ) divide a $p(x)-1$ .
Gulliver | 18 de November de 2010 | 01:35

Es cierto que el argumento no es correcto, pero espero que la conclusión sí.

Corrijo el argumento. La primera parte no la cambio, aunque la voy a hacer más explicita. Para $n$ primo, todos los divisores positivos de $2^n - 1$ son congruentes con 1 módulo $n$ . $p(n)$ , que es divisor de $2^n - 1$ , puede ser positivo o negativo, pero puedo elegir $p(n)$ de manera que sea positivo para todo $n$ mayor que algún $n_0$ . Para los primos $n$ mayores que esta cota $n_0$ , $p(n) \equiv 1 \pmod{n}$ . Además para $a_0$ , el término independiente del polinomio, $a_0 \equiv 1 \pmod{n}$ .

Tenemos que $a_0 - 1 \equiv 0 \pmod{n}$ para todo $n$ primo con $n > n_0$ , o lo que es lo mismo, todos los números primos suficientemente grandes dividen a $a_0 - 1$ . De aquí se deduce que $a_0 - 1 = 0$ .
Manzano | 18 de November de 2010 | 12:38

Un nuevo intento, quizás más sintético que el de Gulliver.

Dado $n\in\mathbb{N}$ , supongamos que $P(n)$ es distinto de $\pm 1$ . Entonces, existe un número primo $p>2$ tal que $p$ divide a $P(n)$ que, a su vez, divide a $2^n-1$ . En particular, $p$ divide a $2^n-1$ .

Ahora bien, $p$ divide a $P(n+p)-P(n)$ (es la propiedad 1 que puse en mi post anterior) y, como divide a $P(n)$ , también divide a $P(n+p)$ que, a su vez, divide a $2^{n+p}-1$ , esto es, $2^{n+p}\equiv 1$ módulo $p$ . Como quiera que $2^{p-1}\equiv 1$ módulo $p$ por el teorema pequeño de Fermat, se sigue que $2^{n+1}\equiv 1$ módulo $p$ , es decir, $p$ divide a $2^{n+1}-1$ .

Hemos probado así que $p$ divide a $\rm{mcd}(2^n-1,2^{n+1}-1)$ , pero este máximo común divisor es igual a $1$ ya que $2^{n+1}-1=2(2^n-1)+1$ . Esto conduce a que $p=1$ , lo cual es la contradicción buscada.

De esta forma, hemos probado que $P(n)$ es siempre igual a $\pm 1$ , pero entonces toma infinitas veces uno de los dos valores y, por tanto, es constante $1$ o bien $-1$ .

En fin, espero que esta vez no haya error.
M | 18 de November de 2010 | 15:06

Muy buena, manzano. Así de simple

Si existiera $n$ tal que $|p(n)|\neq 1$ , existirá un primo $q$ tal que $q|p(n)$ . Además, $q|p(n+kq)$ , para todo $k\geq 0$ . Luego para $k=0,1$ tendremos por la propiedad del enunciado que $2^n\equiv 1 \;(q)$ y $2^{n+q}\equiv 1 \;(q)$ . Pero como, por el pequeño teorema de Fermat $2^q\equiv 2\;(q)$ , se tendría que $2\equiv 1\;(q)$ . Lo cual implicaría que $q|1$ siendo primo.
Manzano | 18 de November de 2010 | 15:30

Efectivamente, M. Gracias por la simplificación.

Lo más interesante del problema es el contrarrecíproco a algunas de las afirmaciones que se han hecho anteriormente: si existiera un tal polinomio no constante, entonces habría un número finito de primos de Mersenne.

Claro que como no existe el polinomio, la afirmación anterior no demuestra nada. Pero es un buen intento para acercarse al problema de la infinitud de los primos de Mersenne.
Gulliver | 18 de November de 2010 | 19:07

Muy buena demostración, Manzano. Lo simple es más bello que lo retorcido.
JuanPablo | 19 de November de 2010 | 04:30

Ya que tenemos una, comento brevemente otra:

a) $P(x)+1$ tiende a infinito (supongamos el coeficiente principal positivo), con lo cual a partir de cierto N, es monótono creciente.

b) Pero entonces $P(n)+1$ debe ser una potencia de 2, y en cada natural mayor a N, es una potencia distinta.

c) De ahí se deduce que $P(x)+1$ crece al menos exponencialmente, pero no puede ser (es un polinomio!)
josejuan | 19 de November de 2010 | 10:05

JuanPablo, creo que tu demostración sólo es válida para un polinomio de grado finito.
JuanPablo | 19 de November de 2010 | 16:18

josejuan, todo polinomio tiene grado finito…
Vayapordios | 19 de November de 2010 | 23:05

JuanPablo, siguiendo tu idea lo que habría que probar más bien es que los divisores crecen exponencialmente.
JuanPablo | 20 de November de 2010 | 02:34

vayapordios, los divisores crecen exponencialmente (son potencias de 2, y estrictamente crecientes)
Vayapordios | 20 de November de 2010 | 11:24

No lo veo nada claro. Matizando. Los divisores de la expresión que queremos estudiar (que no es la exponencial) no crecen TODOS indefinidamente, el 1 está siempre presente. No está claro que los divisores diferentes de 1 de la expresión que vayan apareciendo según crece n, crezcan exponencialmente también.
a | 20 de November de 2010 | 13:06

No todos los divisores de 2^n-1 son de la forma 2^m-1 con m<n (por ejemplo, 2^11-1=23*89). Y, por otra parte, todo primo (excepto el 2) divide a infinitos números de la forma 2^n-1. De modo que no veo el razonamiento de Juan Pablo.
Omar-P | 20 de November de 2010 | 14:29

La belleza oculta de los números perfectos aparece ante nuestros ojos
si se representan sus divisores en cierta forma.
Veamos por ejemplo la estructura de divisores
del número 33550336 (El quinto número perfecto)
———————————————————————————————————
n . . . . . . Divisor . . Formula . . . . . . . Divisor escrito en base 2
———————————————————————————————————
1 . . . . . . . . . . . 1 = 2^0 . . . . . . . . . . 1 . . . La unidad
2 . . . . . . . . . . . 2 = 2^1 . . . . . . . . . . 10
3 . . . . . . . . . . . 4 = 2^2 . . . . . . . . . . 100
4 . . . . . . . . . . . 8 = 2^3 . . . . . . . . . . 1000
5 . . . . . . . . . . 16 = 2^4 . . . . . . . . . . 10000
6 . . . . . . . . . . 32 = 2^5 . . . . . . . . . . 100000
7 . . . . . . . . . . 64 = 2^6 . . . . . . . . . . 1000000
8 . . . . . . . . . 128 = 2^7 . . . . . . . . . . 10000000
9 . . . . . . . . . 256 = 2^8 . . . . . . . . . . 100000000
10 . . . . . . . . 512 = 2^9 . . . . . . . . . . 1000000000
11 . . . . . . . 1024 = 2^10 . . . . . . . . . 10000000000
12 . . . . . . . 2048 = 2^11 . . . . . . . . . 100000000000
13 . . . . . . . 4096 = 2^12 . . . . . . . . . 1000000000000 . . . Quinto número superperfecto
14 . . . . . . . 8191 = 2^13 – 2^0 . . . . 1111111111111 . . . Quinto primo de Mersenne
15 . . . . . . 16382 = 2^14 – 2^1 . . . . 11111111111110
16 . . . . . . 32764 = 2^15 – 2^2 . . . . 111111111111100
17 . . . . . . 65528 = 2^16 – 2^3 . . . . 1111111111111000
18 . . . . . 131056 = 2^17 – 2^4 . . . . 11111111111110000
19 . . . . . 262112 = 2^18 – 2^5 . . . . 111111111111100000
20 . . . . . 524224 = 2^19 – 2^6 . . . . 1111111111111000000
21 . . . . 1048448 = 2^20 – 2^7 . . . . 11111111111110000000
22 . . . . 2096896 = 2^21 – 2^8 . . . . 111111111111100000000
23 . . . . 4193792 = 2^22 – 2^9 . . . . 1111111111111000000000
24 . . . . 8387584 = 2^23 – 2^10 . . . 11111111111110000000000
25 . . . 16775168 = 2^24 – 2^11 . . . 111111111111100000000000
26 . . . 33550336 = 2^25 – 2^12 . . . 1111111111111000000000000 . . . Quinto Nro. perfecto
JuanPablo | 20 de November de 2010 | 15:40

Lamento que no lo vean, aclaro la cuenta. El paso clave es que si $P(n)$ divide a $2^n-1$ , yo miro el polinomio $P(x)+1$ , y debe ser $P(n)+1$ una potencia de 2…

$P(n)+1$ divide a $2^n$ (pasé el 1 al otro lado)

$P(x)+1$ es monónoto creciente (por lo tanto inyectivo) a partir de cierto $N$ (podemos tomarlo natural).

Entonces, $P(N)+1 = 2^k$ , con $k<N$ , y a partir de ahí, en cada natural, $P(N+j)+1$ es una potencia de 2 y distinta a las anteriores. Luego,

$P(N+j)+1 \ge 2^{k+j}.$

Como $P$ es un polinomio, de cierto grado $d$ , tenemos que

$1 \ge [2^{k+j}] / [a_d (N+j)^d+ ...+a_0 +1]$

Ahora, tomando límite en la expresión de la derecha cuando $j\to \infty$ , vemos que da infinito, pero suponemos que está acotado por 1, absurdo.
Francisco | 20 de November de 2010 | 16:58

Pero es que si P(n) divide a 2^n-1, eso no implica que P(n)+1 divida a 2^n, ¿no? Por ejemplo, 5 divide a 15 y sin embargo 6 no divide a 16…
a | 20 de November de 2010 | 18:13

¿Por qué P(n)+1 debe ser una potencia de 2?
josejuan | 20 de November de 2010 | 20:09

“…josejuan, todo polinomio tiene grado finito…”

Nunca había leído una definición de polinomio en la que explícitamente se indicara que debe tener grado finito. Así, siempre había considerado las series de potencias como polinomios.

Si se asume como cierta la hipótesis de que existen infinitos primos de mersenne entonces la demostración es trivial (el polinomio no trivial tendría que tener infinitas raíces, lo cual no es posible por definición).

Por otra parte JuanPablo, pasar el -1 al otro lado no mantiene la divisibilidad. El ejemplo de Francisco sería

Para que P(4) divida a 2^4 – 1 = 15 son posibles 1, 3, 5 y/o 15, pero si el polinomio SOLUCION toma la alternativa P(4)=5, entonces P(4)+1 no es potencia de 2.

Si forzamos (para que sea válida tu demostración) que deben tomarse aquellos divisores que cumplen tu propiedad, quedaría una amplísima familia de polinomios por revisar (y tu demostración quedaría incompleta).

Otra forma de demostrar que sólo el polinomio trivial P(n)=+/-1 es solución, sería demostrar que, tomados dos a dos todos los 2^n-1, no existe un conjunto finito de divisores comunes (exceptuando +/- 1) ¿alguna idea?.
josejuan | 20 de November de 2010 | 20:14

Offtopic

Al hilo de lo de que el grado de un polinomio es finito por definición, si yo preguntara cual es la definición formal de tal o cual objeto matemático, en general, no habría consenso (ej. la inclusión del 0 en los naturales).

Así, siendo las matematicas la reina del formalismo, ¡no hay consenso en las definiciones! (paradojicamente sí lo hay en las conclusiones una vez fijadas las definiciones, ja, ja, …).

Esta cuestión parece bastante importante (por ejemplo para interpretar adecuadamente un problema) y estoy seguro (aunque ignorante) de que muchas personas se han preocupado por esta cuestión.

¿Cómo está el tema?

Gracias.
M | 20 de November de 2010 | 20:54

Josejuan, como veo que insistes en ello, y para evitar confusiones, hay que dejar claro que por definición un polinomio es suma finita de monomios (por ejemplo, ver wikipedia en español, línea 3). Dicha suma finita da lugar al concepto de grado (finito) del polinomio.

Tu idea de trabajar con infinitos sumandos se relaciona con las series de potencias formales; sin embargo, la asignación de valores (reales o complejos, por ejemplo) a una serie formal requiere hablar de convergencia (cosa que en general no ocurrirá para todos los valores de las variables).
Omar-P | 20 de November de 2010 | 22:45

Si uno desea evitar confusiones entonces a la sucesión 1, 2, 3, 4, 5, … la llamará enteros positivos y a la sucesión 0, 1, 2, 3, 4, 5,… la llamará enteros nonegativos.
JuanPablo | 21 de November de 2010 | 07:15

estoy revisando la cuenta y soy un imbécil!! tienen razón, Francisco, a…, no sé en qué estaba pensando cuando la hice!!
JuanPablo | 21 de November de 2010 | 07:21

josejuan, no me limité a pasar el -1 para el otro lado, tampoco soy tan idiota… es un poco más compleja la cuenta que había hecho, pero lamentablemente, llego a que hay un factor $2^{j_n}$ que divide a $p(n)+1$ , y vía subsucesiones lo puedo asumir creciente. El problema está en realidad en la velocidad entre cómo crece el $j_n$ y la subsucesión (por ese error sí me merezco el Título Oficial de Idiota! si Gaussianos se decide a entregarlo, me postulo con mi \\’solución\\’).

Sobre los polinomios, nunca ví nadie que los considerara de grado infinito. Esas son las series de potencias, y como tales, no suelen estar definidas en toda la recta (por ejemplo, una serie de potencias con coeficientes enteros no puede converger muy lejos de cero…)
josejuan | 21 de November de 2010 | 17:08

@M, no quise cuestionar la finitud de los monomios de un polinomio, acepté la réplica de JuanPablo (de ahí, que hablara en pretérito perfecto).

Y mi off, era para saber si hay algún tipo de “RAE” más o menos aceptado en la comunidad matemática.

Siento la confusión.