[JorgeFC]

Sea \( m, e \in{} \mathbb{N} \), 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: \( 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}) \) hasta \( h_l = 1 \). Entonces \( a:=g_l \).

[Luis Fuentes]

Hola

Sea \( m, e \in{} \mathbb{N} \), 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: \( 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}) \) hasta \( h_l = 1 \). Entonces \( a:=g_l \). (Indicación: probar que en cada etapa: \( \displaystyle\prod_{k=0}^{k=i-1}{}h_k * g_i = m  \).

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

El paso inductivo:

\( \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
 \)

Por hipótesis inductiva:

\( \displaystyle\prod_{k=0}^{k=i-2}{}h_k * g_{i-1}=m
 \)

y por construcción:

\( g_i=\dfrac{g_{i-1}}{h_{i-1}}\quad \Rightarrow{}\quad \dfrac{1}{g_{i-1}}\cdot h_{i-1}g_i=1. \)

PD: \( g_(i-1), h_(i-1) \) 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 \( g_{i-1} \)

Saludos.

[JorgeFC]

Muchas gracias, ¿cómo podría concluir que la solución encontrada es la mayor posible?

[EnRlquE]

Hola JorgeFC.

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

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

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

Saludos,

Enrique.

[JorgeFC]

Hola JorgeFC.

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

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

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

Saludos,

Enrique.

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

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

¿Es este razonamiento correcto?
Muchas gracias por la indicación.

[Luis Fuentes]

Hola

 No está del todo bien explicado.

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

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:

\( a=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n} \)

donde ahora los \( p_i \) son distintos y las posibles repeticiones quedan reflejadas en el exponente.

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

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

Entonces el argumento es más sencillo.

De manera idéntica a como ha razonado EnRiquE se deduce que si \( p^k \), con \( p \) primo, divide a a entonces \( p^k \) divide a \( g_l \).

De ahi se deduce inmediatamente que a divide a \( g_l \) es decir \( g_l=ba \) con \( b \) natural y por tanto \( g_l=ba\geq a \).

Saludos.

[JorgeFC]

Me chirriaba un poco mi argumento, la verdad. Muchísimas gracias a los dos.

[JorgeFC]

Siento el doble post, pero me ha surgido una nueva duda. Revisando el ejercicio me he dado cuenta de que no he probado que \( mcd(g_l, e)=1 \).
He pensado que si probase que \( mcd(g_i, e)=h_i \) 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, \( h_i | g_i, h_i | e \).

[EnRlquE]

Hola JorgeFC.

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

\( 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}). \)

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

 Si tienes alguna duda, pregunta.

Saludos,

Enrique.

[JorgeFC]

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