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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

15 Comentarios

  1. 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 😛

    Un saludo!

    Publica una respuesta
  2. 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…

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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).

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. 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

    Publica una respuesta
  7. 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.

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

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. 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)

    Publica una respuesta
  11. hola, podrian ayudarme con el problemilla que tengo y que ya habria expresado unos mensajes atras por favor

    gracias

    Publica una respuesta
  12. 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).

    Publica una respuesta

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.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *