Autor Tema: Algoritmo extendido de Euclides

0 Usuarios y 1 Visitante están viendo este tema.

12 Octubre, 2020, 09:29 pm
Respuesta #10

Quarkbite

  • $$\Large \color{red}\pi$$
  • Mensajes: 4
  • País: es
  • Karma: +0/-0
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?.

13 Octubre, 2020, 11:48 am
Respuesta #11

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,539
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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.