Calculemos el máximo común divisor

Hay nuevos comentarios sin leer

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.

15 comentarios

Trackback | 2 Mar, 2010

Bitacoras.com
Ñbrevu | 2 de March de 2010 | 16:47

¿No es $2^{2009}+1$ ? Desde luego ambos números son múltiplos de dicha cifra, dado que 2009 es impar.
Ñbrevu | 2 de March de 2010 | 16:53

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…
Ñbrevu | 2 de March de 2010 | 17:05

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?
Rafael de Barcelona | 2 de March de 2010 | 18:34

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.
Ñbrevu | 2 de March de 2010 | 20:56

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?
Anuska | 2 de March de 2010 | 21:31

Ñ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$
Anuska | 2 de March de 2010 | 21:37

Perdón, el sumatorio $\sum_{n=0}^{2008} 2^{2009n} (-1)^{n}$
Antonio QD | 2 de March de 2010 | 22:52

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
Ñbrevu | 3 de March de 2010 | 00:01

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.
Ñbrevu | 3 de March de 2010 | 00:03

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 .
Rafael de Barcelona | 3 de March de 2010 | 13:06

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)
Antonio QD | 3 de March de 2010 | 14:26

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
gaussianos | 7 de March de 2010 | 00:56

Por cierto, el problema está sacado de la UGR. En este pdf podéis ver la solución que dan.
JOSELITO | 3 de April de 2010 | 21:54

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