[Gonzalobrama]

Editado
En una ficha de sistemas que tengo de clase, se propone este sistema a resolver:
\( x {\equiv 4(18)}, x \equiv{7(25)} \)
He intentado resolver el sistema con el método que usamos en clase, se supone que tras hacer el mcd y verificar que los módulos son coprimos hallo el valor \( u_2=7 \) y a partir de la fórmula \( 1= u_1\cdot{m_1}+u_2\cdot{m_2} \)(siendo m el módulo) sacar \( u_1 \) pero el valor de \( u_1 \) no resulta un número entero. en este método después de esto se usaráa \( x=u_2*m_1*a_1 + u_1*m_2*a_2 \) (siendo a los coeficientes). Agradecería si alguien pudiese decirme si este sistema se puede resolver, y de ser así, por lo menos decirme en qué me he equivocado. El problema es de un examen de primero de ingeniería informática de la asignatura de matemática discreta. Muchas gracias.

[Gonzalobrama]

Acabo de hacerlo por vez 200000, he dado el valor 7 a \( u_1 \) en vez de darselo a \( u_2 \), para mi hacer esto no tiene sentido(sinceramente, tampoco lo tenia darselo a u_2 porque, aunque se de donde viene, no se por que se le da a \( u_2 \) y no a \( u_1 \)) Pero haciendolo asi, el resultado es un numero entero. ¿Estoy siguiendo el proceso correcto o es solo producto de la desesperacion?

[soneu]

Para poder garantizar la existencia de solución debe ser \( \mathrm{mcd}(18,25)=1. \) El siguiente paso es buscar \( u,v \) tales que \( 18\cdot u+25\cdot v=1. \) ¿Qué quieres decir con darle el valor 7 a uno u otro? Se trata de buscar una solución que no tiene porqué coincidir con ninguno de los restos, aunque en este caso lo haga.

Saludos

[Gonzalobrama]

Para poder garantizar la existencia de solución debe ser \( \mathrm{mcd}(18,25)=1. \) El siguiente paso es buscar \( u,v \) tales que \( 18\cdot u+25\cdot v=1. \) ¿Qué quieres decir con darle el valor 7 a uno u otro? Se trata de buscar una solución que no tiene porque coincidir con ninguno de los restos, aunque en este caso lo haga.

Saludos

No entiendo por que pero el foro se me vuelve loco. He escrito una respuesta que parece haberse perdido en el limbo, pero la repito. Para empezar muchisimas gracias por contestar.no entiendo muy bien a que te refieres con buscar \( u,v \), pero supongo que es lo mismo que voy a decir ahora con otra nomenclatura. adjunto varias imagenes, tanto de la explicacion del metodo como de su puesta en practica, en el ejemplo de las imagenes el se da considera -29 extraido de la tabla como  \( u_2 \) y supongo que, usando ese metodo, el problema del post tendria 7(valor extraido de la respectiva tabla de euclides) como  \( u_1 \) y no  \( u_2 \) pero no entiendo por qué. Como digo, al usar la formula subrayada en las imagenes para obtener  \( u_1 \) teniendo 7 como  \( u_2 \) resulta un numero no entero, pero siendo 7  \( u_1 \) el valor de  \( u_2 \) es un numero entero, de ahi que suponga que, con este metodo, 7 sea  \( u_1 \). Repito, muchas gracias.

[soneu]

La verdad es que no me aclaro mucho con las transparencias beamer. En la segunda dice "vamos a poner los valores ..." Obviamente los ha obtenido primero. Cuando tienes dos números coprimos, pongamos 15 y 8, existen números enteros \( u_1,u_2 \) tales que \( 1=\mathrm{mcd}(8,15)=15u_1+8u_2. \) Se trata de encontrar los valores de \( u_1,u_2. \) Olvídate, por un momento, que estás resolviendo un problema de congruencias. ¿Serías capaz de hacerlo con este ejemplo?

Saludos

[Fallen Angel]

Para encontrar esos coeficientes no tienes más que aplicar el algoritmo de Euclides:

25=18(1)+7
18=7(2)+4
7=4(1)+3
4=3(1)+1

Ahí ya tienes el 1 que es el mcd de 25 y 18.
Despejando:

1=4-3(1)
1=4-(7-4)
1=(18-7(2))-(7-(18-7(2)))
1=(18-2(25-18))-((25-18)-(18-2(25-18)))

Y ahora agrupas

1=7(18)-5(25)

Trata de terminar el ejercicio  

Un saludo!

[Gonzalobrama]

La verdad es que no me aclaro mucho con las transparencias beamer. En la segunda dice "vamos a poner los valores ..." Obviamente los ha obtenido primero. Cuando tienes dos números coprimos, pongamos 15 y 8, existen números enteros \( u_1,u_2 \) tales que \( 1=\mathrm{mcd}(8,15)=15u_1+8u_2. \) Se trata de encontrar los valores de \( u_1,u_2. \) Olvídate, por un momento, que estás resolviendo un problema de congruencias. ¿Serías capaz de hacerlo con este ejemplo?

Saludos

Editado
Esos valores en las transparencias se obtienen de la siguiente transparencia, el primero directamente de la tabla y el segundo de aplicar la fórmula. haciendo Euclides y sustituyendo, como dice la siguiente respuesta del post, se obtienen ambos valores, ahora por lo menos entiendo la tabla, si no me equivoco, lo mismo que hace Fallen Angel, se puede obtener de la tabla, pues se supone que es lo mismo, y supongo que la fórmula es una forma reducida, lo he hecho como decís por otros apuntes que vi por internet( a mi parecer mejores que estos) pero no sé hasta qué punto el profesor evaluará igual si lo hago de una manera distinta. Haciéndolo con el método de las transparencias y viendo todo esto, he intentado resolverla y lo adjunto como imagen, si no me equivoco hago lo que decir pero a partir de la tabla, no estoy seguro de si está bien. Repito, aunque suene pesado, os lo agradezco mucho.

[soneu]

El método de Fallen Angel es el mismo de la tabla que usas, sólo que escrito de manera diferente, y que debería ayudarte a entender lo que significa cada elemento de la tabla.

No veo muy bien la segunda linea. ¿Escribes \( a=18,b=7,r=4? \) Si no entiendo mal como se hace la tabla hay un error, aunque el resultado me parece correcto. ¿Podrías revisar esa parte?

Saludos

[Gonzalobrama]

El método de Fallen Angel es el mismo de la tabla que usas, sólo que escrito de manera diferente, y que debería ayudarte a entender lo que significa cada elemento de la tabla.

No veo muy bien la segunda linea. ¿Escribes \( a=18,b=7,r=4? \) Si no entiendo mal como se hace la tabla hay un error, aunque el resultado me parece correcto. ¿Podrías revisar esa parte?

Saludos

en la segunda linea de la tabla he puesto "a=18, b=7 y r=4" no entiendo el error, el metodo para hacer la tabla es: 1. dividir a/b, poner en r el resto de la division, en la siguiente linea se desplazan lo valores de forma que a sea el valor de b,b el valor de r,v el valor de t y t el resultado de \( v-t*q \). es decir, en esa linea el resto de la primera es b y b de la primera es a. No se si me explico...

[soneu]

Tienes razón, es correcto. Perdón por el lapsus aritmético.