¿Gcd (a, b) = c implica ax + by = c o ax + by = c implica gcd (a, b) = c?

Answer 1

1. Si gcd (a, b) = c, implica que podemos encontrar x e y, que son enteros, de modo que ax + by = c.

2. Si ax + by = c, para algunos x e y, entonces gcd (a, b) <= c porque gdb (a, b) es la menor c que se puede formar a partir de todos ax + by.

3. Además, ax + by = c implica que gdb (a, b) divide c. La prueba sigue,
gdb (a, b) <= min (a, b), sencillo. Deje gdb (a, b) = g.
Deje, g no dividir c. Entonces, como gcd (g, c) <= gy no puede ser gcd (g, c) = g, ya que eso no estaría de acuerdo con nuestra suposición.
Por lo tanto, mcd (g, c) <g.
Lo que significa cx + gy = g` para algunas x e y donde g` <g. … .. (1)
g = ax` + by` para algunas x` e y` también. … (2)
c = ax “+ by” para algunas x “e y”, ya que es donde comenzamos. … (2)
poniendo (2) y (3) en (1), obtenemos
a (x “x + x`y) + b (y“ x + y`y) = g`. Tomando x “x + x`y = x“ `e y“ x + y`y = y “`
ax “` + by “` = g`, donde g` <g, lo que implica que g no es el menor número posible, por lo que no es el mcd (a, b) lo que nos deja con una contradicción.

Si necesita una prueba de 1. o 2., deje un comentario.

Answer 2

La primera implicación es cierta:
[matemáticas] mcd (a, b) = c \ Flecha derecha \ existe x, y \ in \ mathbb {Z} \ colon ax + by = c [/ math]

La segunda implicación debería ser:
[math] ax + by = c \ Rightarrow mcd (a, b) | c [/ math]

Ese es el mayor divisor común que divide cualquier combinación lineal y es, en sí mismo, la combinación lineal menos positiva que no es cero.