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$?
Posted by Unknown at 11:06 a.m.
Labels: ,

11 comentarios:

Flavio dijo...

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

17 de enero de 2011, 2:59 p.m.
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.

17 de enero de 2011, 3:33 p.m.
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

17 de enero de 2011, 3:35 p.m.
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.

17 de enero de 2011, 4:10 p.m.
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

17 de enero de 2011, 4:11 p.m.
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)

17 de enero de 2011, 5:57 p.m.
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.

17 de enero de 2011, 6:18 p.m.
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.

17 de enero de 2011, 11:13 p.m.
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

18 de enero de 2011, 7:54 a.m.
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]$

18 de enero de 2011, 8:54 a.m.
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

18 de enero de 2011, 7:29 p.m.

Publicar un comentario

Suscribirse a: Comentarios de la entrada (Atom)