noticias y última hora

Máximo común divisor para polinomios

Un problema que me comentaron el otro día:

Demostrar que \mbox{mcd}(x^m-1,x^n-1)=x^d-1, siendo d=\mbox{mcd}(m,n)

Este es difícil. A ver si alguien lo consigue.

Posts aleatorios

Autor: ^DiAmOnD^ |  Publicado el 18 de September de 2007
Envia este post a Twitter
Categorías: Juegos |  Imprime este post Imprime este post

Sin comentarios

  1. Keryon | 18 de September de 2007 | 16:43

    Ya esta.

    Formula does not parse = Formula does not parse

    C.q.d

    Ya bromas aparte, me sale eso, aunque antes vi el problema y me salia bien, a ver si lo arreglan pronto :P

    Un saludo!

  2. ^DiAmOnD^ | 18 de September de 2007 | 16:53

    Pues no sé qué ha pasado, pero a mí se me ve perfectamente ahora. Échale un ojo.

  3. Asier | 18 de September de 2007 | 17:58

    Es cierto que no se veían las fórmulas, igual era porque el servidor de wordpress.com, de donde se obtienen las imágenes, se había caido.

    Por cierto, esto hace que todo el contenido acabe dependiendo de un servidor externo…

  4. ^DiAmOnD^ | 18 de September de 2007 | 18:21

    Probablemente Asier. Y sí, tienes razón. La suerte es que al menos es de confianza, pero vamos, estoy abierto a cualquier otra posibilidad mejor. Esperemos que la cosa siga como hasta ahora ya que en líneas generales la cosa ha ido bastante bien.

  5. Domingo HA | 18 de September de 2007 | 21:28

    Bueno , a ver que os parece ésto:

    1) Las n raíces de p_n(x):=x^n-1 son simples, para todo n\geq 1.

    Esto es fácil de ver pues las raíces son las raíces enésimas de la unidad (que ya sabemos que son todas distintas), o bien, si nos ponemos rigurosos, ya que mcd(p_n(x),p_n^{\prime}(x))=mcd(x^n-1,n\cdot x^{n-1})=1. Esto nos dice que las raíces de p_n(x) son simples, porque el polinomio y su derivado no tienen factores comunes.

    2) Si d=mcd(m,n) entonces las raíces de p_d son exactamente las raíces comunes de p_m y p_n. En efecto,

    \bullet si \psi es raíz de p_d entonces \psi^d=1; y puesto que d divide a m y n entonces también se tiene obviamente que \psi^m=\psi^n=1. Es decir que \psi es raíz de ambos polinomios p_m,\;p_n.

    \bullet si \psi es raíz común de p_m,\;p_n entonces \psi^m=\psi^n=1. Por la identidad de Bèzout existen enteros a y b tales que d=ma+nb. Con esto sale fácil que \psi^d=1, y en consecuencia \psi es raíz de p_d. Esto concluye la prueba de 2).

    En particular 2) nos dice que p_d divide a ambos polinomios p_m y p_n (ya que todo polinomio en \mathbb{C}[x] se descompone en factores lineales simples).

    3) Veamos que si otro polinomio q(x) divide a ambos p_m y p_n, entonces también debe dividir a p_d. Esto ya implicaría p_d es un mcd de los polinomios p_n y p_m.

    Si q(x) divide a p_m y p_n y q(x) tiene como raíces (posiblemente complejas) q_1,\ldots, q_r, entonces estas raíces son raíces comunes de los dos polinomios p_m y p_n, y por lo probado en 2) también lo son de p_d(x). En definitiva, los factores lineales de q(x) también lo son de p_d(x), y por tanto q(x) divide a p_d(x).

  6. fede | 18 de September de 2007 | 22:06

    Mis primeros pasos en latex

    En el anillo de polinomios en una indeterminada

    $latex \huge\displaystyle
    mcd( x^{q^n} – x, x^{q^d} -x) = x^{q^{mcd(n,d)} } – x $

    Esta identidad es consecuencia, creo, de que la identidad del post no solo se cumple
    cuando consideramos las expresiones como polinomios, sino que también es cierta
    como fórmula para numeros naturales.

  7. otaivin | 19 de September de 2007 | 03:56

    hola muchachos quisiera hacerles una pergunta off-topic es que llevo ya tiempo leyendo este blog de matematicas pero quisiera consultarles si existe un libro o alguna guia para aprender a hacer demostraciones, la verdad es que en no se demostrar y siempre la embarro en los parciales debido a eso no recuerdo haber hecho una demostracion bien en loq ue llevo de mi carrera profesional. Por favor señores gaussianos ayudenme en mi causa. Ah y para no desvirtuar quisiera saber si esta demostracion sale por el algoritmo de la division de euclides. gracias

  8. ^DiAmOnD^ | 19 de September de 2007 | 18:55

    Muy buena Domingo, bastante más sencilla que la que me había encontrado quien me propuso el problema.

    Una pregunta: la demostración que yo tengo en mi poder es válida para cualquier cuerpo y ésta que propones en principio es válida en \mathbb{C}. ¿Habría alguna forma sencilla de generalizar esta demostración a un cuerpo cualquiera?

    Por si te sirve de ayuda en la demostración que yo tengo distigue casos según la característica del cuerpo.

  9. Domingo HA | 19 de September de 2007 | 19:22

    Ok supuse que planteabas los polinomios dentro de \mathbb{C}. Habrá que estudiar con tiempo la cuestión que planteas ahora.

  10. ^DiAmOnD^ | 19 de September de 2007 | 20:01

    Sí, el problema que yo propuse estaba planteado en \mathbb{C}. Pero sí me gustaría que le echaras un ojo a una posible generalización a cualquier cuerpo a partir de esta demostración. Si en unos días no sale pongo la que tengo yo en mi poder.

  11. fede | 20 de September de 2007 | 17:36

    La siguiente demostración aparece en McEliece, “Finite Fields for Computer Scientists and Engineers”, Kluwer 1987.

    Usamos que (1) mcd( s, t) = mcd( s, t-rs)
    y que (2) (t^n -1) - t^{n-m}(t^m - 1) = t^{n-m} - 1.

    Sea t un elemento de cualquier dominio en que existan mcd’s. Entonces, si m y n son enteros positivos, mcd( t^n-1, t^m-1) = t^{mcd(n,m)} -1 .
    La prueba es por inducción sobre max(m,n). Si max(m,n) = 1 o si m = n el resultado es trivial. En otro caso podemos asumir que m < n y que el resultado se cumple si el mayor de los exponentes es menor que n.
    Entonces
    mcd( t^n -1, t^m -1 )= mcd( t^m-1, t^{n-m} -1) por (2) y (1)
    = t^{mcd( m, n-m)} -1 por induccíón
    = t^{mcd(n,m)} - 1 por (1)

  12. Domingo HA | 21 de September de 2007 | 18:14

    sí señor fede…me ha encantado la demostración.

  13. Domingo HA | 22 de September de 2007 | 21:07

    ^DiAmOnD^,¿podrías postear la demostración que conoces? Gracias.

  14. otaivin | 24 de September de 2007 | 22:47

    hola, podrian ayudarme con el problemilla que tengo y que ya habria expresado unos mensajes atras por favor

    gracias

  15. ^DiAmOnD^ | 10 de October de 2007 | 02:28

    Pongo la demostración que me pasó quien me propuso el problema:

    Sea K el cuerpo en cuestión. Dividimos el problema en 3 casos:

    1) caracteristica(K)=0
    2) caracteristica(K)=p (primo evidentemente) y p no divide a m o a n (o a ninguno).
    3) caracteristica(K)=p (primo evidentemente) y p divide a m y a n.

    En los casos 1) y 2) se tiene que p no divide a d y por tanto x^d-1 no tiene raíces múltiples porque su derivada es dx^{d-1} y mcd(x^d-1,dx^{d-1})=1. Por tanto sólo tenemos que probar que las raíces comunes de x^m-1 y x^n-1 son las mismas que las de x^d-1. Sea e una raíz común de x^m-1 y x^n-1. Como d=mcd(m,n) entonces existen enteros s,t tal que d=ms+nt. De aquí e^d=e^{ms+nt}=1 y por tanto e es raíz de x^d-1.

    Para el caso 3), sea m=p^k \cdot u y n=p^r \cdot v, donde p no divide a u ni a v. Tomemos sin pérdida de generalidad k \le r.

    Entonces x^m-1=(x^u-1)^{p^k} y x^n-1=(x^v-1)^{p^r} (recordemos que la característica del cuerpo es p).

    Como k \le r, los factores comunes de x^m-1 y x^n-1 estarán elevados a la p^k-ésima potencia. Pero como p no divide a u ni a v podemos aplicar el caso 2) y decir que mcd(x^u-1,x^v-1)=x^z-1, donde z=mcd(u,v). Entonces mcd(x^m-1,x^n-1)=(x^z-1)^{p^k}=x^{zp^k}-1. Pero es fácil ver que zp^k=mcd(m,n)=d (recordemos las expresiones de m y n). Con esto comcluímos el caso 3).

Comentarios cerrados.