Factores primos

Publicado por ^DiAmOnD^ | 17 noviembre, 2009 | Juegos | 8 |

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.

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉

0 0 votes

Article Rating

Comparte:

Sobre el Autor

^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes encontrarme también en Twitter, en Instagram, en Geogebra.org y en Facebook.

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.

Name*

Email*

Website

Name*

Email*

Website

8 Comments

más antiguo

más reciente más votado

Bitacoras.com

17/11/2009 08:00

Información Bitacoras.com…

Valora en Bitacoras.com: Os dejo el problema de esta semana: Demuestra que el número : Es divisible por el primo de Fermat , y Es divisible por al menos otros cuatro números primos distintos aparte de . A por él….

Responde

Manzano

17/11/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/11/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.

Responde

otro

17/11/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.

Responde

Uno que suele leer en la sombra.

17/11/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!

Responde

17/11/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…

Responde

19/11/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.

Responde

amanda

25/11/2009 01:46

porfavor me pueden explicar ‘a que se llama factor primo de un numero y como se saca’

Responde

Jonas Castillo Toloza

30/11/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).

Responde

Buscar

Premio Prisma 2018

Suscríbete por mail

Si quieres recibir los artículos de Gaussianos en tu mail, haz click en la imagen.

Últimas entradas

Últimos comentarios

Gaussianos en Facebook

Yo construí el poliedro de Császár

Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.

Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.