miércoles, 19 de enero de 2011

Problema TST USA

Un problema para entretenerse para antes de llegar al entrenamiento.

Sea P un polinomio con coeficientes enteros tal que P(0)=0 y
\[ \mcd(P(0), P(1), P(2),\ldots ) = 1. \]

Muestra que hay infinitas n tal que n
\[ \mcd(P(n)-P(0), P(n+1)-P(1), P(n+2)-P(2),\ldots) = n. \]

2 comentarios:

Diego627 dijo...

Nota, (a_1,a_2,a_3,...) es el maximo comun divisor del conjunto {a_1,a_2,...}

Georges dijo...

Sea P(x)=(a_k)x^k+...+(a_1)x

Consideremos el polinomio Q(r)=(a_k)(k)(r^k-1)+...+(a_2)2(r)+(a_1)1. Si esto polinomio es 0 para todos los naturales r, significa que tiene que ser el polinomio 0, pero claramente no cumple las condiciones del problema, por lo tanto existe una r tal que el polinomio no es 0. Digamos que ese numero es t, entonces como Q(t) es distinto de 0 existen infinitos primos que no dividen a Q(t). Esos primos van a ser los n del problema. Probaremos que cumplen.

Es conocido que si P es un polinomio con coeficientes enteros entonces a-b divide a P(a)-P(b) por lo tanto n=(n+r)-r divide a P(n+r)-P(r) por lo tanto el mcd de (P(n+r)-P(r)...) para toda r es un multiplo de n.

Veamos que n es la maxima potencia de n que divide al mcd de los numeros de la forma P(n+r)-P(r). Supongamos que no es cierto entonces n^2 tiene que dividir a P(n+r)-P(r) que mod n^2 se puede ver como n(Q(r)) por lo tanto n divide a Q(r) para toda r pero eso no es cierto por que n no divide a Q(t). Por lo tanto la maxima potencia de n que divide al mcd de lo que queremos es n.

Ahora si un primo q distinto de n cumple que q divide al mcd de los numeros de la P(n+r)-P(r) entonces divide a todos los numeros de esa forma, en particular P(n),P(2n),...,P(n(q-1)) pero q tambien divide a todos los numeros de la forma P(q+r)-P(r) para toda r, entonces es facil ver que como n,2n, ..., n(q-1) forman un sistema completo de residuos mod q entonces como podemos sumarle q o restarle por que q divide a P(q+r)-P(r) entonces q divide a todos los numeros de la forma P(i) lo cual contradice la hipotesis de que su mcd es 1.

Por lo tanto ningun primo q distinto de n divide el mcd de lo que queremos, y la maxima potencia de n que lo divide es n, por lo tanto el mcd es n y eso es para infinitas n.

Publicar un comentario