La ecuación diofántica$ax + by = c$ tiene una solución entera$x_0, y_0$ si y solo si$\gcd(a,b)|c$

Question

Deje $a,b,c$ ser enteros positivos. Compruebe que la ecuación de Diophantine $ax + by = c$ ha entero solución de $x_0, y_0$ si y sólo si $GCD(a,b)|c$.

Intento

Diophantine $ax + by = c$ ha entero solución de $x_0, y_0$ implica $GCD(a,b)|c$. Factorizando $ GCD(a,b)$ a partir de cada lado da $$\frac{1}{GCD(a,b)}(ax + by) = \frac{1}{GCD(a,b)}c$$ which must still have an integer solution as $GCD(a,b)$ obviously divides both $a$ and $b$. If $MCD(a,b)$ does not divide $c$ no hay ningún número entero solución.

Que $GCD(a,b)|c$ implica que el $ax + by = c$ ha entero solución de $x_0, y_0$. Deje $c = GCD(a,b)d$ donde $d$ es un entero.

$ax + by = GCD(a,b)d$; dividir ambos lados por $GCD(a,b)$: Obtenga $mx + ny = d$ con $GCD(m,n) = 1$. Si $d$ es un número entero y $GCD(m,n) = 1$ entonces $x,y$ deben ser números enteros como $mx + ny$ no puede ser dividido de manera uniforme.

o

$ax + by = c$ no tiene solución implica $GCD(a,b)$ no divide a c.
$c = GCD(a,b)(\frac{ax}{GCD(a,b)} + \frac{by}{GCD(a,b)}) + r$

con $GCD(a,b) > 0, 0<r<GCD(a,b)$, r entero

$\frac{c}{GCD(a,b)} = \frac{ax + by}{GCD(a,b)} + \frac{r}{GCD(a,b)}$

Answer 1

Si$(a,b)\mid c$,$\exists t\in \mathbb{Z}$ es tal que$t(a,b)=c$. Como sabemos que existe$x,y \in \mathbb{Z}$ tal que$ax+by=(a,b)$, entonces elija los enteros$x_0=tx$ y$y_0=ty$.

Para probar lo contrario, si$x_0$ y$y_0$ son enteros, entonces$(a,b)\mid x_0a$ y$(a,b)\mid y_0y$ implica$(a,b)\mid (x_0a+y_0b)$.

Answer 2

Vamos a,b,c enteros positivos. Compruebe que Diophantine ecuación ax+by=c tiene entero solución x0,y0) si y sólo si MCD(a,b)|c.

= > : (¿cómo se escribe las flechas?):

Esto era más o menos correcto en mi primer intento. Más claramente:

Si $ax + by = c$ ha entero solución de $x_0,y_0$(existen - ¿cómo puedo dibujar eso?) a continuación,$ax_0 + by_0 = c$. Dividir ambos lados por $gcd(a,b)$. (Véase el primer intento.) Entonces $gcd(a,b)|a, gcd(a,b)|b$ => $gcd(a,b)|(ax_0 + by_0)$ => $gcd(a,b)|c$.

<=:

Esto fue bastante mal en mi primer intento.

Deje $gcd(a,b)|c$

Entonces existe e tal que $c = gcd(a,b)*e$ y existe $x_1,y_1$ con $gcd(a,b) = ax_1 + by_1$

Multiplicar ambos lados por $e$: $gcd(a,b)*e = ax_1e + by_1e$

$a(x_1e) + b(y_1e) = c$, $(x_1e,y_1e)$ solución.

---

Intento probar de las dos formas a la vez:

$ax + by = c$ ha entero solución de $ax_0 + by_0 = c$

Deje $d = gcd(a,b)$; a continuación,$a = md,b = nd$:

$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$

Por lo $d$ divide $c$.

Si bien $ax_0 + by_0 <>($no es igual a$) c$ o $gcd(a,b) $ no divide $ c$

$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$ no sería válido. tipo de un tramo de allí.

Answer 3

Deje $d=GCD(a,b)$ donde $ {a,b,c,d,k_1,k_2,x,y} \in \mathbb Z$

(a) Positivo: $d|c$

$$ d|a \implica d|ax \\ d|b \implica d|por $$

Entonces, por el Teorema de la División de

$$ d|a \implica a/d=k_1\\ x(a/d)=k_1x \implica d|ax \\ d|b \implica b/d=k_2\\ y(b/d)=k_2y \implica d|por $$

Desde $d|ax$ y $d|ax$, $d$ divide ambos lados de la ecuación de $ax + by = c$ e $d|c$.

(b) Contrapositivo: $d\not|c$

Dado $d|a$ $$ d\no|ax \implica x\noen \mathbb Z $$ Asimismo, dado $d|b$ : $$ d\no|por \implica y\noen \mathbb Z $$