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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

60 Comentarios

  1. 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…

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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?

    Publica una respuesta
  5. 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 existen infinitos primos de mersenne).

    (no se…)

    Publica una respuesta
  6. 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í…

    Publica una respuesta
  7. 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.

    Publica una respuesta
  8. 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…

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. 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?

    Publica una respuesta
  11. “…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.

    Publica una respuesta
  12. 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…

    Publica una respuesta
  13. Madre mía, no había visto tantos comentarios borrados en ningún otro post xD

    Nos está costando ¿eh?

    Publica una respuesta
  14. 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

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. 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”.

    Publica una respuesta
  17. 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.

    Publica una respuesta
  18. 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).

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. 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.

    Publica una respuesta
  21. 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).

    Publica una respuesta
  22. 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  .

    Publica una respuesta
  23. 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 .

    Publica una respuesta
  24. 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.

    Publica una respuesta
  25. 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 .

    Publica una respuesta
  26. 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.

    Publica una respuesta
  27. 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 .

    Publica una respuesta
  28. 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.

    Publica una respuesta
  29. 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.

    Publica una respuesta
  30. 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.

    Publica una respuesta
  31. 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.

    Publica una respuesta
  32. 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.

    Publica una respuesta
  33. Muy buena demostración, Manzano. Lo simple es más bello que lo retorcido.

    Publica una respuesta
  34. 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!)

    Publica una respuesta
  35. JuanPablo, siguiendo tu idea lo que habría que probar más bien es que los divisores crecen exponencialmente.

    Publica una respuesta
  36. 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.

    Publica una respuesta
  37. 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.

    Publica una respuesta
  38. 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

    Publica una respuesta
  39. 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.

    Publica una respuesta
  40. 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…

    Publica una respuesta
  41. “…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?.

    Publica una respuesta
  42. 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.

    Publica una respuesta
  43. 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).

    Publica una respuesta
  44. 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.

    Publica una respuesta
  45. estoy revisando la cuenta y soy un imbécil!! tienen razón, Francisco, a…, no sé en qué estaba pensando cuando la hice!!

    Publica una respuesta
  46. 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…)

    Publica una respuesta
  47. @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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tweets that mention Encuentra los polinomios | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos, 3lena.. 3lena. said: RT @gaussianos: Gaussianos.com: Encuentra los polinomios http://bit.ly/bSMtoW [...]
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema de esta semana: Encontrar todos los polinomios con coeficientes enteros…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *