Autor Tema: Demostración número primo

0 Usuarios y 1 Visitante están viendo este tema.

24 Enero, 2010, 07:53 pm
Leído 1988 veces

sanmath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 630
  • Karma: +0/-0
  • Sexo: Masculino
Hola necesito ayuda con este ejercicio
Demuestre que si \( 2^n - 1 \) es un número primo entonces \( n  \)tambíén es primo, con \( n \in \mathbb{N} \)
Hint: Hágalo por contradicción
Saludos
1301215

24 Enero, 2010, 08:32 pm
Respuesta #1

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Tienes que usar el caso de factorizacion que implica la diferencia de dos potencias con el mismo exponente:

\( a^m - b^m = (a-b)(a^{m-1}+a^{m-2}b+\cdots) \)

En este caso si supones que \( n \) no es primo puedes escribir \( n = k j \), y tomando \( a = 2^j,\ b =1,\ m=k \), en la expresión de arriba puedes factorizar tu numero.

Actualizado: cambiando n por m en la primer ecuación para no confundirla con la segunda n.
.

24 Enero, 2010, 10:07 pm
Respuesta #2

sanmath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 630
  • Karma: +0/-0
  • Sexo: Masculino
Siguiendo la sugerencia dada tengo:
\( 2^{kj}-1 = (2^{k} - 1)( 2^{kj - 1}+2^{kj-2}+ 2^{kj-3}+\ldots1) \)
 pero ahi que puedo aplicar la verdad no lo veo como puedo llegar a una contradicción desde ese punto? resoliviendo con tu sugerencia llegué hasta esta parte.

Como se supone que \( n  \)  no es primo, existen \( k,j \in \mathbb{N} \) tal que \( n=kj \), ahora bien con la descomposición anterior y sabiendo que  \( 2^{kj}-1 \) es primo por hipótesis se tiene que este la factorización anterior es un producto de primos es decir \( (2^{k} - 1) \) es primo. De aqui ya no sé que mas puedo aplicar.


Saludos
1301215

24 Enero, 2010, 11:23 pm
Respuesta #3

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Como \( 2^n-1 \) es primo entonces sus unicos factores son 1 y si mismo.

Suponiendo que n es compuesto (n=kj con k,j>1) entonces tiene una factorizacion  \( 2^n-1 = (2^k - 1)(2^{j-1}+2^{j-2}+ 2^{j-3}+\cdots 1) \).

Spoiler
Luego tiene que ser \( 2^k - 1 = 2^n  -1 \) o \( 2^{k} - 1=1 \).

El primero implica k=n, j=1, absurdo pues suponiamos que k,j>1.

El segundo caso implica \( 2^k = 2 \), k=1,j=n, absurdo por el mismo argumento que antes.
[cerrar]

Tienes mal la factorizacion deberías chequear que realmente entiendes lo que estas haciendo.
.

25 Enero, 2010, 12:05 am
Respuesta #4

sanmath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 630
  • Karma: +0/-0
  • Sexo: Masculino
No te equivocaste en la operación \( 2^4 = 16 \) no \( 18 \)
1301215

25 Enero, 2010, 12:07 am
Respuesta #5

sanmath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 630
  • Karma: +0/-0
  • Sexo: Masculino
Como \( 2^n-1 \) es primo entonces sus unicos factores son 1 y si mismo.

Suponiendo que n es compuesto (n=kj con k,j>1) entonces tiene una factorizacion  \( 2^n-1 = (2^k - 1)(2^{j-1}+2^{j-2}+ 2^{j-3}+\cdots 1) \).


Luego tiene que ser \( 2^k - 1 = 2^n  -1 \) o \( 2^{k} - 1=1 \).

El primero implica k=n, j=1, absurdo pues suponiamos que k,j>1.

El segundo caso implica \( 2^k = 2 \), k=1,j=n, absurdo por el mismo argumento que antes.
[/spoiler]



Hola disculpa la insistencia pero no tengo muy claro porque solo basta verificar \( 2^k - 1 = 2^n  -1 \) o \( 2^{k} - 1=1 \),  que pasa con el otro factor?

Saludos
1301215

25 Enero, 2010, 12:20 am
Respuesta #6

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Perdón borre el post anterior porque sumé en lugar de restar, en fin, una auténtica burrada.

Podemos demostrar que si p no es primo, \( 2^p-1 \) no es primo.
Sea \( p=rs \) con \( r,s\in\mathbb{N} \) con \( r>1\; y\; s>1 \)

\(
\begin{eqnarray}
2^p-1&=& 2^{rs}-1\\
&=& \left(2^r\right)^s-1\\
&=& \left(2^r-1\right)\left(\left(2^r\right)^{s-1}+\left(2^r\right)^{s-2}+\ldots+1\right)
\end{eqnarray}
 \)
como \( r>1 \), se tiene \( 2^r-1>1 \), por lo tanto \( 2^p-1 \) es compuesto.

Saludos.
Eram quod es, eris quod sum.

25 Enero, 2010, 12:37 am
Respuesta #7

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Hola disculpa la insistencia pero no tengo muy claro porque solo basta verificar \( 2^k - 1 = 2^n  -1 \) o \( 2^{k} - 1=1 \),  que pasa con el otro factor?

Saludos

Tienes que ver cuidadosamente lo que esta pasando si suponemos que p = rs.

Por el TFA (Teorema Fundamental de la Aritmética) [salvo signo] todo numero se descompone de una única manera como producto de primos.

Ahora por ser p primo tiene que ser:
1) r = p y s = 1
2) r = 1 y s = p

Como todas los números involucrados son positivos estas son los únicos casos posibles.

Como los casos son conjunciones (r=p Y s=1) solo hace falta probar que uno de los dos es falso para que todo la expresión sea falsa.

En vez de probar solo la primer parte también se podría probar la segunda s=1 y que s=p, pero a mi me parece que es mas difícil hacerlo ;)
.