Loading [MathJax]/jax/element/mml/optable/MathOperators.js

domingo, 7 de octubre de 2012

Problema del día. Teoría de Números (7 de Octubre)

Determina el máximo común divisor de los números:
333,555,777,,201120112011
(Nota: Son los impares)

27 comentarios:

  1. en la sucesion son todos los impares o todos los primos?

    ResponderBorrar
    Respuestas
    1. Este comentario ha sido eliminado por el autor.

      Borrar
    2. Veo primero que el menor numero de la secuencia es 333=24 entonces a lo mas el mcd de todos los términos es 24. Demostrare que precisamente es el 24.Primero me fijo que 24=83. Entonces vere la congruencia modulo 8 y modulo 3.
      Primero para modulo 3 hay 3 casos:
      Si (2n+1)0(mod3) entonces (2n+1)2n+1(2n+1)0(mod3).
      Si (2n+1)1(mod3) entonces (2n+1)2n+1(2n+1)110(mod3).
      Si (2n+1)2(mod3) entonces (2n+1)2n+1(2n+1)(1)2n+1+11+10(mod3).
      Luego vere modulo 8 y me fijo que (2n+1)2n+1(2n+1)=(2n+1)((2n+1)2n1)=(2n+1)(((2n+1)n+1)((2n+1)n1)).Luego fijandome en ((2n+1)n+1)((2n+1)n1) me fijo que ambos terminos son pares entonces las distintas posibles congruencias modulo 8 son (2,4),(4,6),(6,0),(0,2) y viceversa. Entonces como ambas congruencias siempre se multiplican en todos los casos daria al final congruencia 0 modulo 8, entonces todos los terminos de la sucesion son multiplos de 3 y de 8, entonces el mcd de todos los terminos es 24

      Borrar
  2. 333=273=24=3(23)
    Entonces el máximo común divisor no puede tener ningún factor fuera de 3,23.
    (2n+1)2n+1(2n+1)=(2n+1)((2n+1)2n1)=(2n+1)((2n+1)n+1)((2n+1)n1)
    (2n+1)n es impar, entonces (2n+1)n+1,(2n+1)n1 son pares, y como la diferencia es 2, alguno es múltiplo de 4 (porque al ser pares tienen congruencia 2,0 mod 4 y no pueden ser ambos 2) entonces es múltiplo de 2(4)=8
    Si x1,1(mod3), entonces x2k1(mod3), entonces si 2n+1 no es múltiplo de 3, (2n+1)2n1 lo será y si 2n+1 es o no múltiplo de 3, (2n+1)((2n+1)2n1) lo será.
    (2n+1)2n+1(2n+1) es múltiplo de 8 y de 3, entonces es múltiplo de 3(23).
    Por lo tanto el máximo común divisor de todos es 24 (independientemente de si son impares o primos, porque son de la forma 2n+1).

    ResponderBorrar
  3. Por ser diferencia de impares nos damos cuenta que a todos los numeros los divide el 2, despues vemos los tres posibles casos de cada numero congruente a 0,1,2 mod 3 entonces en el caso donde x0mod3 oviamente xxx0mod3, cuando x1mod3 entonces nos damos cuenta que 1 y 3 son primos relativos por lo tanto podemos multiplicar entonces
    x2xmod3 esto se puede si x es primo relativo con el tres y sabemos que es sierto entonces xxx1x10mod3 cumple ahora para x2mod3 sabemos que son primos relativos y podemos multiplicar entonces x2x12mod3 entonces
    x2x1x220mod3 por lo tanto tambien funciona el 3

    ResponderBorrar
    Respuestas
    1. Esa parte es correcta, pero, ¿cuántas veces los divide el 2? ¿cuántas veces los divide el 3? ¿son los únicos?

      Borrar
  4. Primero vemos que sin importar si la secuencia es de impares o primos, todos los números se pueden expresar como 2n+1 porque si fueran primos, el 2 no está.
    Expandimos el término (2n+1)2n+1(2n+1) :
    (2n+1)((2n+1)2n1)=(2n+1)((2n+1)n+1)((2n+1)n1)
    Sabemos que el mcd que buscamos sera menor o igual al menor término de la secuencia, es decir 333=273=24=3(23)
    Sabemos que (2n+1) es impar, entonces (2n+1)n es impar. Y entonces (2n+1)n+1 y (2n+1)n1) son pares.
    Sabemos que al multiplicar dos pares consecutivos, el resultado será múltiplo de 8, es decir 23 .
    Por lo tanto ((2n+1)n+1)((2n+1)n1))=8x
    Entonces (2n+1)2n+1(2n+1) es múltiplo de 23 .
    Digamos que (2n+1)=k .
    Vemos las diferencias congruencias módulo 3 :
    k0(mod3)
    kk0(mod3)
    kkk0(mod3)
    k1(mod3)
    kk1(mod3)
    kkk0(mod3)
    k2(mod3)
    kk2(mod3)
    kkk0(mod3)
    Por lo tanto (2n+1)2n+1(2n+1) es múltiplo de 3 .
    El \text{mcd} de todos los términos de la secuencia es 24.

    ResponderBorrar
  5. En la sucesión, son todos los impares.

    ResponderBorrar
  6. tenemos que el menor es 3^3-3=24 entonces el minimo comun multiplo es 24 a lo mas entonces tienes que todos los numeros impares son asi 2n+1 y tienes que seria 2n+1(((2n+1)^2n)-1 y lo expandes y te queda que es (2n+1)(((2n+1)^n)+1)(((2n+1)^n)-1) y tienes que 2n-1 es impar por lo tanto ((2n+1)^n) es impar por lo tanto si le sumas o le restas uno te queda que son pares y por casillas uno es multiplo de 4 y el otro de 2 por lo tanto es multiplo de 8 y tienes que si n es 2n+1\equiv1,2(mod3) entonces si es uno entonces ((2n+1)^n)-1) es multiplo de 3 y si es dos entonces igual pasari que ((2n+1)^n)-1) es multiplo de 3 entonces es multiplo de (8)3=24 por lo tanto el minimo comun multiplo de todos es 24

    ResponderBorrar
    Respuestas
    1. Correcto.
      Pero faflta explicar mejor el caso del modulo 3:
      -Falta el caso en el que 2n+1\equiv0(mod3)
      -Falta explicar mejor el caso 2n+1\equiv2(mod3) (¿por qué es múltiplo de 3?)

      Borrar
  7. \text{Sea }m\text{ el numero que buscamos.}
    \text{Vemos que }3^3-3=24
    \text{Luego }m\le 24

    \text{Luego vemos que todo termino de la forma }(2k+1)^{2k+1}-2k+1)
    \text{se puede descomponer de la forma }(2k+1)((2k+1)^{2k}-1)

    \text{Nos fijamos en }(2k+1)((2k+1)^{2k}-1)\mod{3}

    \text{Si }2k+1\equiv 0 \mod{3}
    \Rightarrow 3|2k+1

    \text{Si }2k+1\equiv 1,2 \mod{3}
    \Rightarrow (2k+1)^{2k}\equiv 1 \mod{3}
    \Rightarrow (2k+1)^{2k}-1\equiv 0 \mod{3}
    \Rightarrow 3|(2k+1)^{2k}-1

    \Rightarrow \forall k\; 3|(2k+1)((2k+1)^{2k}-1)


    \text{Ahora vemos }(2k+1)((2k+1)^{2k}-1)\mod{8}
    \(2k+1)\equiv 1,3,5,7 \mod{8}
    \Rightarrow (2k+1)^{2k}\equiv 1\mod{8}
    \Rightarrow (2k+1)^{2k}-1\equiv 0\mod{8}

    \Rightarrow \forall k\; 8|(2k+1)((2k+1)^{2k}-1)

    \text{Luego, como }(8,3)=1\Rightarrow 24|(2k+1)((2k+1)^{2k}-1)
    \Rightarrow m/ge 24\text{ pero }m\le 24\Rightarrow m=24

    \therefore\boxed{\text{El maximo comun divisor es }24.}

    ResponderBorrar
  8. primero me fijo que a o mas el mcd es 24 por lo de 3^3-3=24 entonces me fijo en las congruencias de los exponentes a modulo 8
    caso 1: congruencias a 1 modulo 8
    entonces a cualquier exponente la congruencia va a ser siempre congruente a 1 modulo 8 entoncessi le restamos el numero n es como si a la congruencia le restasemos 1 y nos quesaria que seria congruente a 0 modulo 8.
    caso2: n \equiv 3(mod 8)
    entonces el patron de la congruencia modulo 8 del exponente de n
    seria asi: 3,1,3,1,3.... y nos fijamos que va a ser congruente a 3 solo cuando el exponente sea impar entonces cuando el exponente sea impara y le restamos n va a pasar lo mismo que con el caso anterior , va a ser como si a la congruencia le restasemos 3 y nos quedaria congruente a 0 mod 8.
    en genral para cualquier numero impar n va a ser asi :
    n \equiv k (mod 8) con k un entero impar ya que si es para entonces n seria par y savemos q no se puede. y luego el patron de congruencias seria k,1,k,1,k,1,k... y la congruencia a k solo se dARIA CUANDO EL EXPONENT SEA IMPAR entonces despues le restariamos n que seria como restarle k a la congruencia y nos quedaria que si seria multiplo de 8.
    ahora cuando n\equiv 0 (mod3)
    entonces en cualquier exponente va a ser multiplo de 3 y si le restamos n va a seguir siendo multiplo de 3 ya que tambien n es multiplo de 3
    ahora cuando n\equiv 1(mod 3) entonces el patron de congruencias seria siempre 1 entonces si le restamos n es como si le restasemos 1 a la congruencia y nos quedaria qe seria congruente a 0 mod 3
    ahora cuando n \equiv 2(mod3)
    vemos que el patron de congruencias seria 2,1,2,1,2.... y el 2 solo apareceria cuando el exponente es impar entonces si le respamos n es como si le restasemos 2 a la congruencia y nos quedaria que si seria multiplo de 3.
    entonces como ya checamos todos los caso y nos dio que en todos los caso siempre va a ser multiplo de 3 y de 8 entonces siempre va aser multiplo de 24 entonces el MCD es 24

    ResponderBorrar
  9. Este comentario ha sido eliminado por el autor.

    ResponderBorrar
  10. Intento.-
    Vi los casos chicos:
    mcd(3(3^{2}-1), 5(5^{4}-1))=3(3^{2}-1=24
    mcd(24, 7(7^{6}-1))=24
    Por lo que he intentado demostrar que:
    mcd(3(3^{2}-1), 5(5^{4}-1), \cdots 2011(2011^{2010}-1))=24
    Podemos afirmar que será al menos 2 pues tenemos impares elevados a distintas potencias y a cada uno le restamos uno, por lo que todos los términos son pares.

    ResponderBorrar
    Respuestas
    1. Solución completa.-
      Sabemos que el mcd es a lo más 24 y debe dividir a 24 pues 3^{3}-3=24=3*8 entonces probamos ambos módulos:
      P.D. (2k+1)^{2k+1}-(2k+1)\equiv{0}\pmod{3}
      Caso k\equiv{0}\pmod{3}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{1^{2k+1}-1}\equiv{0}\pmod{3}
      Caso k\equiv{1}\pmod{3}\Rightarrow 2k+1\equiv{0}\pmod{3}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{0}\pmod{3}
      Caso k\equiv{2}\pmod{3}\Rightarrow (2k+1)^{2k+1}-(2k+1)=2k+1((2k+1)^{2k}-1)\equiv{2((2^{2k})-1)}=2^{2k+1}-2\pmod{3}
      Vemos que toda potencia de 2 elevada a un número impar es congruente a 2 modulo 3, por lo tanto en este caso: (2k+1)^{2k+1}-(2k+1)\equiv{0}\pmod{3}
      Con todos los casos tenemos que 3 divide a todos los números.
      Ahora vemos módulo 8:
      P.D. (2k+1)^{2k+1}-(2k+1)\equiv{0}\pmod{8}
      k\equiv{0}\pmod{8}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{1^{2k+1}-1=0}\pmod{8}
      k\equiv{1}\pmod{8}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{3^{2k+1}-3=3(3^{2k}-1) vemos que toda potencia de 3 par es congruente a 1 módulo 8, entonces 3(3^{2k}-1)\equiv{3(0)}=0\pmod{8}
      k\equiv{2}\pmod{8}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{5^{2k+1}-5=5(5^{2k}-1) vemos que toda potencia de 5 par es congruente a 1 módulo 8, entonces 5(5^{2k}-1)\equiv{5(0)}=0\pmod{8}
      k\equiv{3}\pmod{8}\Rightarrow (2k+1)^{2k+1}-(2k+1)\equiv{7^{2k+1}-7=7(7^{2k}-1) vemos que toda potencia de 7 par es congruente a 1 módulo 8, entonces 7(7^{2k}-1)\equiv{7(0)}=0\pmod{8}
      k\equiv{4, 5, 6, 7}\pmod{8} son análogos al los casos k\equiv{0, 1, 2, 3}\pmod{8} respectivamente, tenemos que para todos lo casos cumple al igual que con módulo 3, entonces \boxed{mcd=24}

      Borrar
  11. Este comentario ha sido eliminado por el autor.

    ResponderBorrar
  12. Primero busque cual era el valor del numero mas chico. Teniendo eso, sabre que es lo maximo que puede llegar a ser el m.c.d. El numero mas chico era 3^3-3 y esto es igual a 24. 24=3*8. Luego me di cuenta de que todos esos numeros se podian expresar de la forma (2n+1)((2n+1)^2^n-1)

    Luego, busque la congruencia de (2n+1)((2n+1)^2^n-1) en (mod 3)

    SI 2n+1\equiv 0 (mod 3) Entonces 3|(2n+1) Entonces 3|(2n+1)((2n+1)^2^n-1)

    Si2n+1\equiv 1,2 (mod 3) Entonces (2n+1)^2^n\equiv 1 (mod 3)
    (2n+1)^2^n-1\equiv 0 (mod 3) Entonces 3|(2n+1)((2n+1)^2^n-1)

    Luego me fijo en ello en (mod 8)

    2n+1\equiv 1,3,5,7 (mod 8)
    Entonces (2n+1)^2^n\ equiv 1 (mod 8)
    Entonces (2n+1)^2^n-1\equiv 0 (mod 8)
    Entonces 8|(2n+1)((2n+1)^2^n-1)

    Por lo tanto el m.c.d. es 24

    ResponderBorrar
  13. http://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view&current=CAM001461.jpg

    ResponderBorrar