Vamos con el problema de esta semana:
Encontrar todos los polinomios
con coeficientes enteros que verifican que
divide a
, para todo
.
A por él.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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.
[…] This post was mentioned on Twitter by gaussianos, 3lena.. 3lena. said: RT @gaussianos: Gaussianos.com: Encuentra los polinomios http://bit.ly/bSMtoW […]
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…
(Comentario eliminado por el autor; argumento erróneo).
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 tal que divide a entonces, en concreto, P(n) debe dividir a todos los primos de la secuencia (los primos de Mersenne) Obviamente los números primos no son divisibles más que por 1 y por si mismos, luego: o bien (el caso trivial), o bien (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… Lee más »
Información Bitacoras.com…
Valora en Bitacoras.com: Vamos con el problema de esta semana: Encontrar todos los polinomios con coeficientes enteros que verifican que divide a , para todo . A por él. Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, co……
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.
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?
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).… Lee más »
Bueno, para [2] no creo que haga falta recurrir a los primos de mersenne…
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í…
Eliminado, me salté una condición. Sorry.
Eliminado
Bueno, tenemos un numero arbitrario de ecuaciones de la forma






existe una solucion
(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.
Pienso que no seria demasiado dificil manipular estas ecuaciones algebricamente para demostrar que para ninguna sucesion
(ninguna solucion excepto la trivial, claro)
Por cierto, si se me permite la gracia, he encontrado otro polinomio que resuelve el problema:
!! 🙂 Ahora sí que no hay más…
Dani, qué rápido crecería ese polinomio, verdad?
Encontré otro:
(
está en los naturales, sólo que no supe cómo ponerlo).
para todo
. De hecho
cumple con lo que se busca.
Éste cumple porque
El crecimiento del polinomio no es claro si no conocemos la descomposicion de
en primos para
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
. 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?
«…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.
Borro lo que he puesto, que no me convence.
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…
Borrado por el autor.
Madre mía, no había visto tantos comentarios borrados en ningún otro post xD
Nos está costando ¿eh?
Buenos Días Si existe el polinomio pedido, las raices de este polinomio deben ser también raices de . Las raices de son del tipo donde . Los posibles factores de son entonces y . Si , entonces es necesario que su termino independiente, que es de la forma pertenezca a . Esto para todo significa que debería ser algebraico. Si podemos demostrar que es transcendente, entonces el único posible polinomio que divide a es de la forma donde y por una cuestión de paridad este único polinomio es posible cuando . ¿Quién se atreve a demostrar que es transcendente? Un… Lee más »
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 con coeficientes enteros y dados distintos, se cumple que divide a (es muy fácil de probar puesto que divide a como polinomio de dos variables). 2) Dados números naturales y , divide a (también es fácil de probar factorizando el polinomio para cierto polinomio y haciendo . Una vez visto esto, supongamos que cumple las condiciones del enunciado y lleguemos a que ha de ser constante. Para ello, consideremos dos números naturales y observemos que,… Lee más »
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».
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.
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
es distinto de cero, entonces divide a
.»
No sé si has razonado del siguiente modo:
Finalmente,
divide a
(lo cual no es cierto en general: toma por ejemplo
,
).
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.
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.
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… Lee más »
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
de
cumplen
módulo n. Ver teorema 3. Los divisores positivos no primos de
son producto de potencias de divisores primos, luego también serán congruentes con 1 módulo n.
Si
y
es un número primo mayor que
y suficientemente grande para que
sea positivo,
es divisor de
, de modo que
módulo n, y al ser
,
.
Como es raíz de , divide como polinomio a . Para , divide a 1, luego solo puede ser 1 o -1. Si p(1) = 1, es raíz de y divide como polinomio a . Si p(1) = -1, es raíz de y divide como polinomio a . O bien divide a , o bien divide a , pero solo uno de los dos es verdadero y voy a comprobar cual de los dos es. Para , divide a 127, luego solo puede ser -127, -1, 1 o 127. divide a . Para , los únicos valores de múltiplos de… Lee más »
Lo que sigue es bastante rutinario, simplemente comprobar los casos particulares de
,
,
,
,
y
, por este orden, y ver que también son raíces de
. Los monomios que dividen al polinomio
se irán acumulando.
Creo que no merece la pena que lo detalle porque es muy simple.
Por ejemplo para
,
divide a 31. Por otro lado
divide a
, luego 20 divide a
. El único valor posible para p(5) es 1,
es raíz de
y
divide a
.
El resto de valores sigue la misma lógica de comprobar valores y acumular monomios.
Con estos casos particulares se demuestra que divide a . Para el resto de valores no negativos se puede demostar por inducción que divide a . Para entre 0 y 7 ya está demostrado, y lo demostraré para . Por hipótesis de inducción divide a , luego todos los enteros entre 2 y son divisores de . También es divisor , mínimo común múltiplo de todos los enteros entre 2 y . para algún entero . divide a . para algún entero . Hay una bonita demostración de que para que detallaré más adelante. De momento esto sirve para ver… Lee más »
Me falta demostrar que
. 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.
Hay una parte de la parrafada de las 18.06 que no es correcta. Voy a corregirla aquí.
Para
entero mayor que 8,
para algún entero
y
es el mínimo común múltiplo de los enteros entre 2 y
.
Si
,
es positivo. Antes se ha demostrado que
.
Queda
que es imposible por la definición de
y esta es la contradicción que demuestra
.
Ahora tengo tiempo para poner la demostración de que
el mínimo común múltiplo de los enteros entre 2 y n es mayor que
para
.
Hay que considerar la integral
para
entero. Haciendo la expansión binomial de
se obtiene
. Es una suma de fracciones en la que los denominadores no son mayores que
, de modo que
es entero mayor que 1.
.
Por otra parte
para
entre 0 y 1, y para algunos x es estrictamente menor. Por tanto I es menor que
y
.
Si
,
.
Si
,
.
Si
,
.
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 módulo , y al ser .» En concreto, me parece que estás asumiendo que , 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 , con entero negativo. No digo que la propiedad no pueda ser cierta, pero ese detalle creo que hay que… Lee más »
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 primo, todos los divisores positivos de son congruentes con 1 módulo . , que es divisor de , puede ser positivo o negativo, pero puedo elegir de manera que sea positivo para todo mayor que algún . Para los primos mayores que esta cota , . Además para , el término independiente del polinomio, . Tenemos que para todo primo con , o lo que es lo mismo, todos… Lee más »
Un nuevo intento, quizás más sintético que el de Gulliver. Dado , supongamos que es distinto de . Entonces, existe un número primo tal que divide a que, a su vez, divide a . En particular, divide a . Ahora bien, divide a (es la propiedad 1 que puse en mi post anterior) y, como divide a , también divide a que, a su vez, divide a , esto es, módulo . Como quiera que módulo por el teorema pequeño de Fermat, se sigue que módulo , es decir, divide a . Hemos probado así que divide a , pero… Lee más »
Muy buena, manzano. Así de simple 🙂
Si existiera
tal que
, existirá un primo
tal que
. Además,
, para todo
. Luego para
tendremos por la propiedad del enunciado que
y
. Pero como, por el pequeño teorema de Fermat
, se tendría que
. Lo cual implicaría que
siendo primo.
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.
Muy buena demostración, Manzano. Lo simple es más bello que lo retorcido.
Ya que tenemos una, comento brevemente otra:
a)
tiende a infinito (supongamos el coeficiente principal positivo), con lo cual a partir de cierto N, es monótono creciente.
b) Pero entonces
debe ser una potencia de 2, y en cada natural mayor a N, es una potencia distinta.
c) De ahí se deduce que
crece al menos exponencialmente, pero no puede ser (es un polinomio!)
JuanPablo, creo que tu demostración sólo es válida para un polinomio de grado finito.
josejuan, todo polinomio tiene grado finito…
JuanPablo, siguiendo tu idea lo que habría que probar más bien es que los divisores crecen exponencialmente.
vayapordios, los divisores crecen exponencialmente (son potencias de 2, y estrictamente crecientes)
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.