Factores primos

Os dejo el problema de esta semana:

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

Es divisible por el primo de Fermat $F_4=2^{2^4}+1$ , y

Es divisible por al menos otros cuatro números primos distintos aparte de $F_4$ .

A por él.

Sin comentarios

Trackback | 17 Nov, 2009

Bitacoras.com
Manzano | 17 de November de 2009 | 10:08

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.
otro | 17 de November de 2009 | 13:21

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.
otro | 17 de November de 2009 | 13:24

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.
Uno que suele leer en la sombra. | 17 de November de 2009 | 21:50

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!
M | 17 de November de 2009 | 23:10

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…
M | 19 de November de 2009 | 20:23

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.
amanda | 25 de November de 2009 | 01:46

porfavor me pueden explicar ‘a que se llama factor primo de un numero y como se saca’
Jonas Castillo Toloza | 30 de November de 2009 | 22:58

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).