Calculemos el máximo común divisor

A la vista del título del post está bastante claro la temática del problema de esta semana, ¿verdad? Ahí va:

Calcula el máximo común divisor siguiente:

mcd \left ( (2^{2009}+1)^{2009},2^{{2009}^{2009}}+1 \right )

Suerte.

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.

14 Comentarios

  1. Faltaría demostrar que \sum_{n=0}^{2008}2^{2009n}\left(-1\right)^n (el segundo número dividido por mi hipotético mcd) no es múltiplo de ningún divisor de 2^{2009}+1, cosa que no sé si es cierta…

    Publica una respuesta
  2. Los miembros pares del sumatorio son congruentes con 1 (módulo 2^{2009}+1), y los impares también… luego el sumatorio es congruente con \sum_{n=0}^{2008}1=2009. Sólo falta demostrar que 2^{2009}+1 no es múltiplo de 7 ni de 41 (ya que 2009=7^2\cdot41).

    Tengo prisa y no puedo hacerlo, pero ése es el camino, ¿no?

    Publica una respuesta
  3. 2^2009+1 no es múltiplo ni de 7 ni de 41.
    Por la función Euler, 7 es 6 y 41 es 40,
    Como 2009 respecto a 6 tiene como resto 5 y respecto a 40 el resto es 9, tenemos
    2^5+1 es congruente con 5 modulo 7 y
    2^9+1 es congruente con 21 módulo 41, luego,
    como los congruentes son distintos a cero, queda demostrado de que 2^2009+1 no es divisible ni por 7 ni por 41.
    ¿Es lo que te faltaba, Ñbrevu?
    Perdonar por no utilizar LaTex.

    Publica una respuesta
  4. Gracias, sabía más o menos lo que tenía que hacer pero en ese momento no tenía tiempo.

    Pues entonces el mcd buscado es 2^{2009}+1, ¿no? He sido muy poco formal con mis demostraciones pero creo que más o menos son correctas. ¿Alguien tiene una segunda opinión?

    Publica una respuesta
  5. Ñbreu, yo creo que tu sumatorio (el cociente)
    \sum_{n00}^2008 2^{2009n} (-1)^{n}, tendría que llegar no hasta 2008, sino hasta 2009^{2008}-1

    Publica una respuesta
  6. Buenos Días

    Ofrezco mi desarrollo, que no deja de ser una puesta en limpio de ideas que ya otros han citado.

    2^{2009^{2009}}+1 = (2^{2009})^{2009^{2008}} +1 = ((2^{2009}+1)-1)^{2009^{2008}} +1 =

    \sum_{n=0}^{2009^{2008}}{{2009^{2008}\choose n}(2^{2009}+1)^{2009^{2008}-n}(-1)^n}+1=

    \sum_{n=0}^{2009^{2008}-1}{{2009^{2008}\choose n}(2^{2009}+1)^{2009^{2008}-n}(-1)^n}=

    (2^{2009}+1)\sum_{n=0}^{2009^{2008}-1}{{2009^{2008}\choose n}(2^{2009}+1)^{2009^{2008}-1-n}(-1)^n}=

    (2^{2009}+1)(p(2^{2009}+1)+ 2009^{2008})

    donde p es un número entero.

    El máximo común divisor buscado ha de estar a la fuerza formado por el producto de potencias de los divisores primos de (2^{2009}+1); si podemos demostrar que (2^{2009}+1) y 2009 son primos entre si habremos demostrado que el factor (p(2^{2009}+1)+ 2009^{2008}) es primo con (2^{2009}+1), y que por tanto el máximo común divisor es (2^{2009}+1).

    Vayamos pues a la tarea. La factorización de 2009
    es 7^2\cdot41.

    Por lo que usando aritmética de congruencias y en algún que otro momento el Pequeño Teorema de Fermat

    2^{2009} \equiv (2^{7^2})^{41} \equiv 2^{7^2} \equiv 2^{49} \equiv 2^9 \equiv 512 \equiv 20 \bmod 41

    2^{2009} \equiv (2^{41})^{7^2} \equiv 2^{41} \equiv 2^5 \equiv 32 \equiv 5 \bmod 7

    Por lo que

    2^{2009} + 1  \equiv 21 \bmod 41

    2^{2009} + 1 \equiv 6 \bmod 7

    Y acabamos de demostrar que 2009 y (2^{2009} + 1) no tienen factores comunes y por lo tanto son primos entre si.

    Por lo que como ya se había apuntado en otro post el máximo común divisor buscado es (2^{2009} + 1).

    Un Saludo

    Publica una respuesta
  7. Anuska, míralo así: vamos a llamar z a 2^{2009}. Entonces la primera cifra es \left(z+1\right)^{2009}, mientras que la segunda es z^{2009}+1. Claramente z+1 es una raíz de este último polinomio (y más claramente todavía lo es del primero ;)). Por otra parte tenemos \dfrac{z^{2009}+1}{z+1}=z^{2008}-z^{2007}+z^{2006}-\ldots+z^2-z+1, que es el sumatorio \sum_{n=0}^{2008}z^n\left(-1\right)^n. Si ahora sustituimos z por su valor, tenemos el sumatorio que escribí antes.

    De paso, continúo con la demostración, ahora de manera más formal, ya que tengo un poco de tiempo.

    El primer polinomio se convierte en \left(z+1\right)\cdot\left(z+1\right)^{2008}, mientras que el segundo pasa a ser \left(z+1\right)\sum_{n=0}^{2008}z^n\left(-1\right)^n. Habida cuenta de que z\in\mathbb{Z}, está claro que el mcd de estos dos polinomios será igual a \left(z+1\right)\cdot\textrm{mcd}\left(\left(z+1\right)^{2008},\sum_{n=0}^{2008}\left(-z\right)^n\right).

    Por otro lado, tenemos que \left(-z\right)^n\equiv\left(-z+z+1\right)^n\equiv1^n\equiv1 \left(\textrm{mod} \left(z+1\right)\right), de donde obtenemos \sum_{n=0}^{2008}\left(-z\right)^n\equiv\sum_{n=0}^{2008}1\equiv2009 \left(\textrm{mod} \left(z+1\right)\right). Sustituyendo z por su valor, obtenemos \sum_{n=0}^{2008}2^{2009n}\left(-1\right)^n\equiv2009 \left(\textrm{mod} \left(2^{2009}+1\right)\right), lo que significa que, si demostramos que 2009 y 2^{2009}+1 son coprimos, entonces \sum_{n=0}^{2008}2^{2009n} y 2^{2009}+1 también lo serán. Esta demostración está más arriba :).

    Consecuentemente, \textrm{mcd}\left(\left(z+1\right)^{2008},\sum_{n=0}^{2008}\left(-z\right)^n\right)=1, y así, \textrm{mcd}\left(\left(2^{2009}+1\right)^{2009},2^{2009^{2009}}+1\right)=2^{2009+1}, QED.

    Publica una respuesta
  8. Y ahora veo que el problema podía referirse a 2^{\left(2009^{2009}\right)}, y no a \left(2^{2009}\right)^{2009}, que es lo que he hecho yo…

    Pero en todo caso Antonio QD ha resuelto la otra interpretación posible :).

    Publica una respuesta
  9. Antonio QD
    2^2009+1==21 mód. 41 es correcto
    2^2009+1==5 mód. 7 es correcto (no es 6, es 5)

    Publica una respuesta
  10. Buenos Días

    Evidentemente cometí un error en la una de las congruencias.

    Realmente es 32 \equiv 4 \bmod 7

    Perdónenme por el error. Afortunadamente, no afecta al desarrollo.

    Un Saludo

    Publica una respuesta
  11. Hola necesito una mano con la prueba de:  si (a, b) = d entonces (a^2, b^2) = d^2

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: A la vista del título del post está bastante claro la temática del problema…

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 *