[Quarkbite]

Si, no me explique bien, me referia a un limite superior de esos dos primeros valores calculados, de los valores dados por el algoritmo extendido de euclides. En una ecuacion Ax+By=C, x e y ¿son siempre menores a A y B respectivamente?,¿Depende de C?, ¿Depende de m.c.d?.

[Luis Fuentes]

Hola

Si, no me explique bien, me referia a un limite superior de esos dos primeros valores calculados, de los valores dados por el algoritmo extendido de euclides. En una ecuacion Ax+By=C, x e y ¿son siempre menores a A y B respectivamente?,¿Depende de C?, ¿Depende de m.c.d?.

En primer lugar para que la ecuación \( Ax+By=C \) tenga solución, \( C \) debe de ser múltiplo del mcd de \( C \).

Por otra parte si \( |A|\neq |B| \) y \( C=mcd(A,B) \) siempre podemos conseguir una solución con \( |x|<|B| \) e \( |y|<|A| \).

Spoiler

Sin pérdida de generalidad suponemos \( C<|B| \).

Basta tener en cuenta que la solución general es de la forma \( (x,y)=(x_0,y_0)+k(B,-A) \). De ahí \( x=x_0+kB \) y podemos escoger \( k \) tal que \( |x|<|B| \). Entonces:

\( |y|=\dfrac{1}{|B|}|C-Ax|\leq \dfrac{1}{|B|})(|C|+|A||x|)\leq \dfrac{1}{B}|A||x|<|A| \)

[cerrar]

Saludos.

[Quarkbite]

El algoritmo extendido de euclides nos da \( d,x,y \).  ¿Existen más métodos para conseguir lo mismo?, ¿al valor de x, si no lo he entendido mal, también se le llama inverso multiplicativo?.

[Luis Fuentes]

Hola

El algoritmo extendido de euclides nos da \( d,x,y \).  ¿Existen más métodos para conseguir lo mismo?, ¿al valor de x, si no lo he entendido mal, también se le llama inverso multiplicativo?.

Si \( d=1 \) y por tanto tenemos \( ax+by=d \), entonces \( x \) sería el inverso multiplicativo de \( a \) módulo \( b \).

Si \( d\neq 1 \), no es el inverso multiplicativo.

Saludo.

[Quarkbite]

Por tanto si a y b son primos entre si, el algoritmo siempre te dara el inverso multiplicativo, ¿es asi?.

[Luis Fuentes]

Hola

Por tanto si a y b son primos entre si, el algoritmo siempre te dara el inverso multiplicativo, ¿es asi?.

Si, de manera precisa si \( a \) y \( b \) son primos entre si y obtenemos \( x,y \) cumpliendo \( ax+by=1 \) entonces \( x \) es el inverso multiplicativo de \( a \) módulo \( b \).

Saludos.

[feriva]

Por tanto si a y b son primos entre si, el algoritmo siempre te dara el inverso multiplicativo, ¿es asi?.

El inverso multiplicativo es tal que si se tiene un número “x” (o la letra que sea) existe (a veces) otro número “a” tal que \( ax\equiv1
  \) para el módulo que se esté considerando; es decir, tal que "ax" dividido del módulo deja resto 1.

Este hilo está “conectado” con este otro (también de Luis):

https://foro.rinconmatematico.com/index.php?topic=26781.0

Si el mcd existe y no es uno en la ecuación \( ax+by=d
  \), se puede dividir por el mcd a los dos lados de forma que quede otra ecuación, equivalente, en la que sí lo sea: \( \dfrac{ax}{d}+\dfrac{by}{d}=1
  \); y la puedes reescribir con las letras que quieras \( ax_{0}+by_{0}=1
  \).

Esa igualdad existe por el teorema de Bézout.

Entonces, en módulo “b” (o módulo “y sub cero”, las letras dan igual, son letras) al dividir \( by_{0}
  \) por “b” da resto cero, con lo que al dividir \( ax_{0}
  \) por b tiene que dar resto 1, necesariamente, para que se cumpla la ecuación.

(ya ha contestado Luis)

Saludos.