Factores primos

Os dejo el problema de esta semana:

Demuestra que el número 19^{1976}+76^{1976}:

  1. Es divisible por el primo de Fermat F_4=2^{2^4}+1, y
  2. Es divisible por al menos otros cuatro números primos distintos aparte de F_4.

A por él.

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.

8 Comentarios

  1. Llamemos N al número en cuestión. Por un lado tenemos que, sacando factor común, N=19^{1976}(1+2^{3952}) luego 19 es un factor primo de N y los demás factores primos lo serán del número 1+2^{3952}. Ahora bien, vamos a usar que para cualesquiera enteros x, y y cualquier natural impar n se cumple que x+y divide a x^n+y^n lo que se deduce de la identidad algebraica

    x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+x^{n-3}y^2-\ldots+y^{n-1})

    Por tanto, como 3952=2^4\cdot 13\cdot 19, tenemos que 1+2^{3952} es divisible por F_4=1+2^{16} sin más que tomar x=1, y=2^{16} y n=247 en el razonamiento anterior y el apartado (1) está probado.

    Publica una respuesta
  2. Falta demostrar que hay otros 4 primos distintos que dividen N=19^{1976} \cdot k, donde k=1+2^{3952}=2^{16 \cdot 13 \cdot 19}. No he podido demostrarlo, pero doy aquí una idea a partir de la identidad que ha proporcionado Manzano en el comentario anterior.

    Por una parte, k=1+2^{(16 \cdot 13) \cdot 19}=(1+2^{16 \cdot 13})(1-2^{16 \cdot 13}+2^{16 \cdot 13 \cdot 2}- \dots +2^{16 \cdot 13 \cdot 18})=
    =(1+2^{16})(1-2^{16}+2^{16 \cdot 2}- \dots +2^{16 \cdot 12})(1-2^{16 \cdot 13}+2^{16 \cdot 13 \cdot 2}- \dots +2^{16 \cdot 13 \cdot 18})=
    =F_4 \cdot a_{16,12} \cdot a_{208,18}

    (lo de a_{i,j} es una notación que acabo de crear ad hoc para abreviar la expresión 1-2^i+2^{2i}- \dots -2^{i(j-1)}+2^{ij})

    Por otra parte, k=1+2^{(16 \cdot 19) \cdot 13}=(1+2^{16 \cdot 19})(1-2^{16 \cdot 19}+2^{16 \cdot 19 \cdot 2}- \dots +2^{16 \cdot 19 \cdot 12})=
    =(1+2^{16})(1-2^{16}+2^{16 \cdot 2}- \dots +2^{16 \cdot 18})(1-2^{16 \cdot 19}+2^{16 \cdot 19 \cdot 2}- \dots +2^{16 \cdot 19 \cdot 12})=
    =F_4 \cdot a_{16,18} \cdot a_{304,12}

    Si los a_{i,j} son primos dos a dos, queda claro que cada uno de ellos tiene al menos un factor primo que no tiene ninguno de los otros; como hay cuatro a_{i,j}, habrá al menos cuatro factores primos que dividen N aparte de los que ya conocemos, F_4 y 19.

    Sin embargo, esa última parte no he podido probarla. Me he quedado en que a_{16,13} y a_{16,19} sí son primos entre sí utilizando el algoritmo de Euclides con boli y papel. Las otras comprobaciones, a falta de otro método más eficaz, me resultarían extremadamente tediosas (no dispongo de programa informático que me pueda ayudar) aunque sí sospecho que estoy en la buena pista.

    Publica una respuesta
  3. Perdón, en el comentario anterior está claro que me he liado de alguna forma. Si quieres, bórralo, Diamond, que hoy no he estado lúcido.

    Es obvio que los aes no pueden ser primos dos a dos y que lo que estoy haciendo básicamente es factorizar N=xbc=xde, y que todos los factores de b y c deben estar en d y e.

    Publica una respuesta
  4. Hola:
    Creo que siguiendo la idea de Manzano (muy buena por cierto) se puede probar del mismo modo que es divisible por F_n con n=1,2,3 todos números primos. Junto con el 19 ya tienes los cuatro del apartado (2).

    Un saludo y ¡enhorabuena por el blog!

    Publica una respuesta
  5. Muy buena Manzano.

    En relación al comentario anterior, lamentablemente hay que decir que F_0, F_1, F_2, F_3 no dividen al número en cuestión. Tomando congruencias se ve que el número del enunciado es congruente con 2, módulo 3, 5, 17 y 257.

    Por otro lado, se sabe que si 2^m+1 es primo, entonces m debe ser potencia de dos. Más aún, si un número m tiene un factor impar: m=(2k+1)\cdot r, entonces 2^r+1 divide a 2^m+1. Esto nos dice que 1+2^{2^4\cdot 13} y 1+2^{2^4\cdot 19} dividen a 1+2^{3952} (y a su vez F_4 divide a estos dos números).

    Como además mcd(1+2^{2^4\cdot 13},1+2^{2^4\cdot 19})=1+2^{2^4} (pues (x^19+1)/(x+1) y (x^13+1)/(x+1) son primos relativos), resulta que deben existir dos primos diferentes (entre sí, de 1+2^{2^4} y de 19) que dividan respectivamente a cada uno de estos números, y a 1+2^{3952}.

    A ver si aparece el cuarto…

    Publica una respuesta
  6. Comento por encima una prueba de (2):

    Teníamos la factorización N=19^{1976}(1+x^{19\cdot 13}) con x=2^{2^4}.

    1) Notar que 19 no divide a 1+x^{19\cdot 13}, pues por el pequeño teorema de Fermat

    1+x^{19\cdot 13}\equiv 1+x^{13}=1+2^{(10\cdot19+18)}\equiv 1+2^{10}=18\;(mod\;19).

    2) Por otro lado, independientemente del valor x, mcd\left(\frac{x^{19}+1}{x+1},\frac{x^{13}+1}{x+1}\right)=1 (ya que \frac{x^{19}+1}{x+1}\cdot x(1+x^6)+\frac{x^{13}+1}{x+1}(1-x^7(1+x^6))=1) y mcd\left(\frac{x^{19\cdot 13}+1}{x^{19}+1},\frac{x^{13}+1}{x+1}\right)=\frac{x^{13}+1}{x+1}. Así tenemos que

    \frac{x^{13\cdot 19}+1}{x+1}=\frac{x^{19}+1}{x+1}\cdot \frac{x^{13}+1}{x+1}\cdot f(x) \hfill (EQ)

    donde f(x) verifica f(x)=mcd(\frac{x^{13\cdot 19}+1}{x^{19}+1},\frac{x^{13\cdot 19}+1}{x^{13}+1}).

    3) Los cuatro polinomios f(x), x+1, \frac{x^{13}+1}{x+1} y \frac{x^{19}+1}{x+1} son primos dos a dos.

    4) Por tanto, para x=2^{2^4}, el producto de tres factores que aparece a la derecha en (EQ) debe contener al menos tres primos diferentes, y diferentes de 1+x=F_4, que dividen al número original. Por lo dicho en 1), estos primos son distintos de 19.

    Publica una respuesta
  7. porfavor me pueden explicar ‘a que se llama factor primo de un numero y como se saca’

    Publica una respuesta
  8. Ayyyyy… la embarré
    ^DiAmOnD^ por favor borra mi anterrior comentario.
    Trataré de enmendar

    (1) 2^3952 + 1 = (2^304)^13 + 1
    entonces (2^304 + 1) es un factor de (2^3952 +1).
    Por congruencias comprobamos que 65537 divide a (2^304 +1),
    entonces (2^304 + 1)/65537 es un factor posiblemente primo de (19^1976 + 76^1976)

    (2) 2^3952 + 1 = (2^208)^19 + 1
    entonces(2^208 + 1) es un factor de (2^3952 + 1).
    Por congruencias comprobamos que 65537 divide a (2^208 + 1)
    entonces (2^208 + 1)/65537 es un factor posiblemente primo de(19^1976 + 76^1976).

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Os dejo el problema de esta semana: Demuestra que el número : Es divisible…

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 *