Tengo una duda con la ecuacion lineal ax ≡ 1 (mod m)

por ejemplo cuando el modulo es muy grande

81≡1 (mod 256)

como lo aplico Xo y Yo.

81Xo + 256 Yo = 1

la verdad no entiendo bien a que te referis con la ecuacion lineal, que yo sepa, po rej 81≡1(256) es lo mismo que 256 divide a 81-1

Pero en casos que el modulo sea demasiado grande como en este caso que es 256 se suele usar algoritmo de euclides pero con la formula con Xo y Yo, que no entiendo.

me la podrias pasar para ver si yo la capto?

Para obtener x0 e y0 tenés que aplicar el algoritmo de euclides extendido, no el tradicional que es el de las divisiones reiteradas. De todas maneras en la cátedra no lo enseñan porque no se toman ejercicios de ese estilo, la x se calcula por tanteo, te dan números chicos, o bien si a y m son grandes no son coprimos, por lo que podés simplificar toda la ecuación y, como dije antes, obtener x por tanteo.

Te doy un ejemplo con un ejercicio de parcial: 15x≡6 (mod 21), por tanteo tendrías que probar valores de 1 a 20, cosa medio tediosa, pero como d=mcd(15,21)=3 podés dividir toda la ecuación por este valor y te queda el equivalente 5x≡2 (mod 7), ahora los posibles resultados están entre 1 y 6, se puede sacar por tanteo fácil, x=6. La solución general seria x=7k+6. Como d=3 la ecuacion tiene 3 soluciones que serían: x=7*0+6, x=7*1+6, x=7*2+6; entonces la solución particular es 6, 13, 20.
En este caso b es divisible por d (6 es divisible por 3) pero de no haberlo sido la ecuación no tiene solución y ahí termina el ejercicio.

Supongo que esta duda te surgió por leer el libro de Schaum, no te conviene guiarte del libro, abarca más temas de los que vemos en clases, guiate con los ejercicios de parciales y aprendé a hacerlos usando el libro, no estudies todo lo que dice el libro o te volvés loco

Si bien no contesté exactamente lo que preguntaste espero que te sirva mi respuesta. Suerte.

(06-08-2013 22:33)m68540534 escribió:  Para obtener x0 e y0 tenés que aplicar el algoritmo de euclides extendido, no el tradicional que es el de las divisiones reiteradas. De todas maneras en la cátedra no lo enseñan porque no se toman ejercicios de ese estilo, la x se calcula por tanteo, te dan números chicos, o bien si a y m son grandes no son coprimos, por lo que podés simplificar toda la ecuación y, como dije antes, obtener x por tanteo.

Te doy un ejemplo con un ejercicio de parcial: 15x≡6 (mod 21), por tanteo tendrías que probar valores de 1 a 20, cosa medio tediosa, pero como d=mcd(15,21)=3 podés dividir toda la ecuación por este valor y te queda el equivalente 5x≡2 (mod 7), ahora los posibles resultados están entre 1 y 6, se puede sacar por tanteo fácil, x=6. La solución general seria x=7k+6. Como d=3 la ecuacion tiene 3 soluciones que serían: x=7*0+6, x=7*1+6, x=7*2+6; entonces la solución particular es 6, 13, 20.
En este caso b es divisible por d (6 es divisible por 3) pero de no haberlo sido la ecuación no tiene solución y ahí termina el ejercicio.

Supongo que esta duda te surgió por leer el libro de Schaum, no te conviene guiarte del libro, abarca más temas de los que vemos en clases, guiate con los ejercicios de parciales y aprendé a hacerlos usando el libro, no estudies todo lo que dice el libro o te volvés loco

Si bien no contesté exactamente lo que preguntaste espero que te sirva mi respuesta. Suerte.

Igual para esa ecuacion que dio no te sirve ese metodo porque (81:256) = 1 no te cambia nada dividir por el mcd

No, obvio que en este caso no sirve, pero por eso dije que no toman ejercicios con esos valores, si buscás los parciales que tomaron nunca dieron valores grandes que sean coprimos, precisamente la simplificación se usa solo cuando no son coprimos. Y si mirás en el libro de la cátedra no explican ningún método para hallar x0 e y0, supongo que no les interesa que lo sepamos porque en la práctica por computadora podés averiguar el valor por tanteo, aunque fueran valores grandes, en un tiempo despreciable