lunes, 17 de enero de 2011

Problema del 17 de Enero

¿Para cuáles $n\in \mathbb{N}$ el polinomio $x^n+x-1$ es divisible entre

(a) $x^2-x+1$
(b) $x^3-x+1$?

11 comentarios:

Flavio dijo...

a) n = 6k+5
b) ninguna n

Unknown dijo...

Caso a.
para n=1,2 no cumple.
con x=2, da 3|2^n+1 y eso es sii n=2k+1

x^2-x+1|x^(2k+1)+x-1 sii
x^2-x+1|x^(2k+1)+x^2 y como(x^2,x^2-x+1)=1 entonces sii
x^2-x+1|x^(2k-1)+1 sii
(-x)^2-(-x)+1|(-x)^(2k-1)+1 sii
x^2+x+1|x^(2k-1)-1. sii
x-cis(2pi/3)|x^(2k-1)-1 y
x-cis(4pi/3)|x^(2k-1)-1 sii
(cis(2pi/3))^(2k-1)=(cis(4pi/3))^(2k-1)=1 sii
cis(2(2k-1)pi/3)=cis(4(2k-1)pi/3)=1 sii
2(2k-1)pi/3 y 4(2k-1)pi/3 son multiplos enteros de 2pi sii
(2k-1)/3 y 2(2k-1)/3 son enteros sii
3|2k-1 sii
3|n-2.
Entonces x^2-x+1|x^n+x-1 sii n==2 mod 3 y 1 mod 2 entonces cumple para todo n==5 mod 6.

Unknown dijo...

Caso b.
n=1,2 no cumple. con x=2 da 7|2^n+1. Pero 2^n es congruente solo con 1,2,4 modulo 7, entonces no hay n que cumpla

Manuel Alejandro dijo...

El caso a, es mediante una inducción la forma en que se demuestra que es para todo $n\equiv5(mod6)$.
En el b) solamente observas que si (x^{3}-x+1)|(x^{n}+x-1), entonces (x^{3}-x+1)|((x^{n}+x-1)+(x^{3}-x+1), entonces (x^{3}-x+1)|(x^{3}(x^{n-3}+1)) pero (x{}^{3}-x+1,x^{3})=1, entonces (x^{3}-x+1)|(x^{n-3}+1). Ahora sustituimos x por 2. Entonces $7|2^{n-3}+1$, pero los residuos de potencias de 2 son 1, 2 y 4, por lo cual es absurdo. Entonces no se puede.

Manuel Alejandro dijo...

Olvidé poner el signo para el latex XD
El caso a, es mediante una inducción la forma en que se demuestra que es para todo .
En el b) solamente observas que si $(x^{3}-x+1)|(x^{n}+x-1)$, entonces $(x^{3}-x+1)|((x^{n}+x-1)+(x^{3}-x+1)$, entonces $(x^{3}-x+1)|(x^{3}(x^{n-3}+1))$ pero $(x{}^{3}-x+1,x^{3})=1$, entonces $(x^{3}-x+1)|(x^{n-3}+1)$. Ahora sustituimos x por 2. Entonces , pero los residuos de potencias de 2 son 1, 2 y 4, por lo cual es absurdo. Entonces no se puede

Unknown dijo...

Está bien el inciso (b), pero que hace falta que expliquen un poco mejor el por qué su argumento con módulo 7 funciona, recuerden que el problema trata divisibilidad de polinomios y no de enteros. Digan por qué no se puede que $x^n+x-1$ se exprese como $x^3-x+1$ por algún otro polinomio con coeficientes raros. Si eso pasara tal vez al evaluar ese polinomio en 2 no sea entero... (por eso no podrían usar la divisibilidad de enteros)

Flavio dijo...

caso a)
$x^2-x+1 | x^n+x-1$
$ \rightleftarrow$
$ x^2-x+1 | x^n+x^2 $
$ \rightleftarrow$
$ x^2-x+1 | x^{n-2}+1 $
pero las raices de $P(x)=x^2-x+1$ son z=cos60 + i sen60
y su conjugado z' para que P(x) divida a $x^{n-2}+1$ basta que $z^{n-2}+1=0$ y $z'^{n-2}+1=0$, esto se ve que ocurre si y solo si n-2 es multiplo de 3 pero no de 2, dando como resultado n= 6k+5 (todo eso usando que z y z' esta en el circulo unitario y su angulo es 60 y se quiere 60*(n-2) divisible por 180 pero no por 360).
caso b)
tenemos que sea $Q(x)=x^3-x+1$. tenemos que si un complejo es raiz de Q entonces su conjugado es raiz, entonces necesariamente Q tiene al menos una raiz real. si $Q(x) | x^n-x+1$ si y solo si $Q(x) | x^n + x^3$ si y solo si
$Q(x) | x^{n-3} + 1$, y si eso sucediera, entonces $r^{n-3}+1=0$, donde r es alguna raiz real de Q ( que sabemos que hay al menos una). Pero eso obliga a que $r^{n-3}=-1$, entonces r=-1, entonces Q(-1)=0, los cual no es cierto, entonces no hay solucion.

Anónimo dijo...

Inciso a)
n=1 no funciona y n=2 tampoco puesto que los polinomios deberían ser idénticos y no lo son. Si n = 3 tampoco se puede puesto que debería existir una a t.q.
(x-a)(x^2 - x + 1)= x^3 + x - 1 y para que los términos que poseen a x^0 sean iguales en ambos lados, a= 1 y entonces
x^3 - x^2 + x - x ^2 + x - 1 = x ^3 - 2 x^2 + 2x - 1 = x^3 + x - 1
lo cual es una contradicción.

n>=4:
x^2 - x + 1 | x^n + x -1
x^2 - x + 1 | x^n + x^2
x^2 - x + 1 | x^(n-2) + 1

Entonces debe existir un polinomio Q(x) de grado n-4 t.q. Q(x)(x^2 - x + 1) = x^(n-2) + 1 entonces cuando (x ^2 - x + 1)=0 también debe ocurrir que:
x^(n-2) + 1 =0

Como las raíces de x^2 - x + 1 obtenidas por la fórmula general son e^(pi/3)i y e ^-(pi/3)i sabemos que al sustituir sus valores en x^(n-2) + 1 también nos debe dar 0 y para empezar, como 1 es real, x ^(n-2) también debe ser real, y como ésto sólo sucede si en a forma polar del complejo tenemos r(e^(pi*k)i) entonces:
n-2 debe ser múltiplo de 3, pero como no sólo queremos que sea real, sino que sea -1, entonces en realidad esto sólo se cumple si el complejo es de la forma e^(pi*(2s+1))i lo cual ocurre cuando n-2 = 3 (mod 6) entonces n=5(mod6) y entonces funciona cuando n es de la forma 6m + 5.

Mientras que en el inciso b)

n=1,2,3 no funciona,

x^3 -x + 1|x^n + x - 1
x^3 -x + 1|x^n + x^3
x^3 -x + 1|x^(n-3) + 1

por lo que n=4,5,6 tampoco funciona.

Ahora vemos que como x^3 -x + 1 es de grado impar, tiene cuando menos una raíz real, por lo que si se cumple lo de arriba, entonces, ambos polinomios comparten esa raíz eso significa que si x-a|x^3 -x + 1 siendo a la raíz, entonces
x-a|x^(n-3) + 1
y por lo mismo a^(n-3) + 1 = 0 por lo que a^(n-3)=-1
y como a tiene que ser real, n tiene que ser impar y entonces a=(-1)^(1/(n-3))
y a = -1 pero (-1)^3 - (-1) + 1= -1 por lo que a no era raíz de x^3 -x + 1
contradiciendo nuestra hipótesis.

Unknown dijo...

Tenemos que si $x^n+x-1=P(x)=(x^3-x+1)Q(x)=(x^3-x+1)(x^{n-3}+a_{n-4}x^{n-4}+...+a_1x+a_0).$ entonecs tenemos que $a_{n-4} \in Z, a_{n-5}+f_{n-5}(a_{n-4})\in Z, a_{n-6}+f_{n-6}(a_{n-4},a_{n-5})\in Z,...,a_0+f_1(a_1,...,a_{n-4})\in Z$ donde $f_i(x)\in Z\left[ x\right]$. Esto es obvio multiplicando, asi que si x^3-x+1 divide a x^n+x-1 entonces Q(x) esta en Z[x]. Publicare despues un resultado más general

Unknown dijo...

En general si $Q(x)R(x)=P(x)$, $Q(x)$ es monico y $P(x),Q(x)\in \matbb{Z}\left[ x \right]$, entonces $R(x)\in \matbb{Z}\left[ x \right]$

Karina =) dijo...

Para el inciso a, hacemos algunos casos pequeños y notamos que n=6k+1, entonces queremos demostrar por inducción.

Para caso base k=0

x^2-x+1 divide a (x^2-x+1)(-x^2) y a (x^2-x+1)(x^3-1), por lo tanto divide a la resta que es x^5+x-1

Ahora suponemos que se cumple hasta cierta k de manera que x^2-x+1 divide a x^(6k+5)+x-1

Sabemos que x^2-x+1 divide a (x^2-x+1)(x^5) y a [x^(6k+5)+x-1][x^6] y a si resta x^(6k+5+6)+x-1 que es el caso que sigue así que todas las k enteros no negativos cumplen.

y para el otro caso yo había valuado x=2 y vi que no se podía, pero ahora el comentario de Irving me hizo dudar así que mejor reviso y veo que pasa xD

Publicar un comentario