21/06/2018, 04:51:15 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Demostración sobre algoritmo y solución óptima.  (Leído 5382 veces)
0 Usuarios y 1 Visitante están viendo este tema.
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« : 31/10/2016, 02:00:56 pm »

Sea [texx]m, e \in{} \mathbb{N}[/texx], y supongamos que m no divide a e. Probar que el siguiente algoritmo encuentra un a tal que a | m y mcd(a, e)=1. ¿Es el mayor posible?

ALGORITMO: [texx]g_0 := m; h_0 := mcd(m,e). \forall{} i \geq{} 1: g_i := g_{i-1} / h_{i-1}; h_i := (g_i, h_{i-1})[/texx] hasta [texx]h_l = 1[/texx]. Entonces [texx]a:=g_l[/texx].
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.008


Ver Perfil
« Respuesta #1 : 31/10/2016, 03:31:33 pm »

Hola

Sea [texx]m, e \in{} \mathbb{N}[/texx], y supongamos que m no divide a e. Probar que el siguiente algoritmo encuentra un a tal que a | m y mcd(a, e)=1. ¿Es la solución encontrada con el algoritmo dado la mayor posible?

ALGORITMO: [texx]g_0 := m; h_0 := mcd(m,e). \forall{} i \geq{} 1: g_i := g_{i-1} / h_{i-1}; h_i := (g_i, h_{i-1})[/texx] hasta [texx]h_l = 1[/texx]. Entonces [texx]a:=g_l[/texx]. (Indicación: probar que en cada etapa: [texx]\displaystyle\prod_{k=0}^{k=i-1}{}h_k * g_i = m [/texx].

He intentado probar lo que te indican por inducción, pero no he sido capaz. ¿Alguna indicación más?

El paso inductivo:

[texx]\displaystyle\prod_{k=0}^{k=i-1}{}h_k * g_i=\displaystyle\prod_{k=0}^{k=i-2}{}h_k * g_{i-1}\cdot \dfrac{1}{g_{i-1}}\cdot h_{i-1}g_i
[/texx]

Por hipótesis inductiva:

[texx]\displaystyle\prod_{k=0}^{k=i-2}{}h_k * g_{i-1}=m
[/texx]

y por construcción:

[texx]g_i=\dfrac{g_{i-1}}{h_{i-1}}\quad \Rightarrow{}\quad \dfrac{1}{g_{i-1}}\cdot h_{i-1}g_i=1.[/texx]

Cita
PD: [texx]g_(i-1), h_(i-1)[/texx] son subíndices, pero no sé cómo ponerlos bien en latex.

Tienes que poner los subíndices entre llaves:


[tex]g_{i-1}[/tex] para obtener [texx]g_{i-1}[/texx]

Saludos.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #2 : 01/11/2016, 12:02:20 pm »

Muchas gracias, ¿cómo podría concluir que la solución encontrada es la mayor posible?
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.878



Ver Perfil
« Respuesta #3 : 01/11/2016, 05:28:29 pm »

Hola JorgeFC.

 Supongamos que [texx]a|m[/texx] y que [texx](a,e)=1.[/texx] Tenemos que mostrar que [texx]a\leq g_{l},[/texx] donde [texx]g_{l}[/texx] es el número obtenido por el algoritmo que describe el problema.

 Bien, tenemos que [texx]m=h_{0}h_{1}\dots h_{l-1}g_{l}.[/texx] Por construcción [texx]h_{0}|e[/texx] y cada [texx]h_{i}|h_{i-1}.[/texx] En particular [texx]h_{i}|e[/texx] para todo [texx]i=0,1,\dots,l-1.[/texx] Esto quiere decir que si algún primo [texx]p[/texx] divide a [texx]a,[/texx] entonces [texx]p\not|h_{i}[/texx] para todo [texx]i=0,1,\dots,l-1.[/texx] Como [texx]a|m[/texx] se deduce que [texx]p|g_{l}.[/texx]

 A partir de lo anterior trata de probar que [texx]a|g_{l}.[/texx] En particular [texx]a\leq g_{l}.[/texx] Si tienes dudas, pregunta.

Saludos,

Enrique.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #4 : 02/11/2016, 03:01:32 pm »

Hola JorgeFC.

 Supongamos que [texx]a|m[/texx] y que [texx](a,e)=1.[/texx] Tenemos que mostrar que [texx]a\leq g_{l},[/texx] donde [texx]g_{l}[/texx] es el número obtenido por el algoritmo que describe el problema.

 Bien, tenemos que [texx]m=h_{0}h_{1}\dots h_{l-1}g_{l}.[/texx] Por construcción [texx]h_{0}|e[/texx] y cada [texx]h_{i}|h_{i-1}.[/texx] En particular [texx]h_{i}|e[/texx] para todo [texx]i=0,1,\dots,l-1.[/texx] Esto quiere decir que si algún primo [texx]p[/texx] divide a [texx]a,[/texx] entonces [texx]p\not|h_{i}[/texx] para todo [texx]i=0,1,\dots,l-1.[/texx] Como [texx]a|m[/texx] se deduce que [texx]p|g_{l}.[/texx]

 A partir de lo anterior trata de probar que [texx]a|g_{l}.[/texx] En particular [texx]a\leq g_{l}.[/texx] Si tienes dudas, pregunta.

Saludos,

Enrique.

Como existe una única factorización en números primos, [texx]a = p_1 * p_2 * ... * p_n[/texx].
Por lo anterior, [texx]p_i | g_l \forall{} i=1,...,n[/texx].

Ahora, por reducción al absurdo, supongamos que [texx]a > g_l \Rightarrow{} \exists{} i=1,...n / p_i|a[/texx], pero [texx]p_i[/texx] no divide a [texx]g_l[/texx]. Lo cual es absurdo. Por lo cual, podemos concluir que [texx]a \leq{} g_l[/texx].

¿Es este razonamiento correcto?
Muchas gracias por la indicación.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.008


Ver Perfil
« Respuesta #5 : 03/11/2016, 05:59:32 am »

Hola

 No está del todo bien explicado.

Como existe una única factorización en números primos, [texx]a = p_1 * p_2 * ... * p_n[/texx].
Por lo anterior, [texx]p_i | g_l \forall{} i=1,...,n[/texx].

Tal como lo has escrito los primos pueden ser repetetidos, es decir, podría ocurrir por ejemplo que p_1=p_2; es no está mal, pero invalida lo que razonas después. Lo usual cuando uno escribe la factorización en primos es poner:

[texx]a=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}[/texx]

donde ahora los [texx]p_i[/texx] son distintos y las posibles repeticiones quedan reflejadas en el exponente.

Cita
Ahora, por reducción al absurdo, supongamos que [texx]a > g_l \Rightarrow{} \exists{} i=1,...n / p_i|a[/texx], pero [texx]p_i[/texx] no divide a [texx]g_l[/texx]. Lo cual es absurdo. Por lo cual, podemos concluir que [texx]a \leq{} g_l[/texx].

Fíjate que ese argumento es falso. Por ejemplo [texx]a=3\cdot 3>g_l=3[/texx], pero no existe en la descomposición de [texx]a[/texx] ningúin primo que no divida a [texx]g_l[/texx].

Entonces el argumento es más sencillo.

De manera idéntica a como ha razonado EnRiquE se deduce que si [texx]p^k[/texx], con [texx]p[/texx] primo, divide a a entonces [texx]p^k[/texx] divide a [texx]g_l[/texx].

De ahi se deduce inmediatamente que a divide a [texx]g_l[/texx] es decir [texx]g_l=ba[/texx] con [texx]b[/texx] natural y por tanto [texx]g_l=ba\geq a[/texx].

Saludos.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #6 : 05/11/2016, 08:55:02 am »

Me chirriaba un poco mi argumento, la verdad. Muchísimas gracias a los dos.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #7 : 07/11/2016, 12:10:36 pm »

Siento el doble post, pero me ha surgido una nueva duda. Revisando el ejercicio me he dado cuenta de que no he probado que [texx]mcd(g_l, e)=1[/texx].
He pensado que si probase que [texx]mcd(g_i, e)=h_i[/texx] lo tendría del todo. Nuevamente lo he intentado hacer por inducción como la indicación, pero sigo teniendo problemas.

Lo único que tengo claro es que por construcción, [texx]h_i | g_i, h_i | e[/texx].
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.878



Ver Perfil
« Respuesta #8 : 07/11/2016, 06:08:02 pm »

Hola JorgeFC.

 Tenemos que [texx]m=h_{0}h_{1}\dots h_{i-1}g_{i}[/texx] para todo [texx]i\in\{0,\dots,l\}[/texx], de esto deduce que [texx]g_{l}|g_{i}[/texx] para todo [texx]i\in\{0,\dots,l\},[/texx] luego

[texx]1=(g_{l},h_{l-1})=\big(g_{l},(g_{l-1},h_{l-2})\big)=(g_{l},g_{l-1},h_{l-2})=(g_{l},h_{l-2}).[/texx]

En la última igualdad hemos usado que si [texx]a|b,[/texx] entonces [texx](a,b,c)=(a,c).[/texx] Repitiendo el mismo procedimiento obtenemos [texx]1=(g_{l},h_{l-2})=(g_{l},h_{l-3})=\dots=(g_{l},h_{0})=(g_{l},m,e)=(g_{l},e),[/texx] pues [texx]g_{l}|m.[/texx]

 Si tienes alguna duda, pregunta.

Saludos,

Enrique.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #9 : 30/11/2016, 12:08:22 pm »

¿Cómo podría calcular la complejidad del algoritmo? (No sé si preguntarlo aquí o abrir un nuevo tema).

Como en cada paso hay que hacer una división y un mcd, había pensado en calcular la complejidad de la división y la complejidad del mcd, y sumarlas. No sé si esto será correcto.
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.878



Ver Perfil
« Respuesta #10 : 30/11/2016, 06:39:44 pm »

Hola JorgeFC.

 Yo no se del tema, creo que se tiene que contar las operaciones involucradas en el algoritmo y tal vez haya que tener en cuenta otras cosas. Tal vez si describes el algoritmo en el subforo de Matemática Discreta y Algoritmos alguien pueda resolver tu duda.

Saludos,

Enrique.
En línea
JorgeFC
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 168


Ver Perfil
« Respuesta #11 : 01/12/2016, 05:52:32 pm »

Hola JorgeFC.

 Yo no se del tema, creo que se tiene que contar las operaciones involucradas en el algoritmo y tal vez haya que tener en cuenta otras cosas. Tal vez si describes el algoritmo en el subforo de Matemática Discreta y Algoritmos alguien pueda resolver tu duda.

Saludos,

Enrique.

Muchas gracias por la idea, no sabía dónde ponerlo.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!