Cómo encontrar soluciones lineales Diophantine ax + by = c?

Question

Quiero encontrar un conjunto de enteros soluciones de la ecuación de Diophantine: $ax + by = c$, y al parecer, $\gcd(a,b)|c$. Entonces ¿por qué fórmula se puede utilizar para encontrar $x$ y $y$ ?

Traté de jugar con esto:
$x = (c)/$, por lo tanto $a|(c)$.

$a$, $c$ y $b$ son conocidos. Así que para obtener entero solución para $a$, entonces $c = ak$, y he perdido desde aquí, porque $y = (c - ak)/b$. Yo no paraba de repetir esta rutina y no podía encontrar una manera de deshacerse de él? Cualquier sugerencia?

Gracias,
Chan

Answer 1

La ecuación de diophantine $ax+by = c$ tiene soluciones si y sólo si $\gcd(a,b)|c$. Si es así, tiene una infinidad de soluciones, y cualquier solución puede ser utilizada para generar todos los otros.

Para ver esto, observe que el máximo común divisor de $a$ y $b$ divide a $ax$ y $$, por lo tanto divide a $c$ si hay una solución. Esto le da a la necesidad de la condición (hacia atrás). (corregido en ediciones)

Lo contrario es en realidad un constructiva de la prueba, que se puede encontrar en casi todos los elementales de la teoría de números curso o un libro, y que es esencialmente el mismo como yunone la respuesta anterior (pero sin dividir a través de la primera).

Desde el Algoritmo de Euclides Extendido, dado cualquier enteros de $a$ y $b$ usted puede encontrar los números enteros $s$ y $t$ tal que $as+bt = \gcd(a,b)$; los números $s$ y $t$ no son únicos, pero sólo necesita un par. Una vez que usted encontrar $s$ y $t$, ya que estamos suponiendo que $\gcd(a,b)$ divide a $c$, existe un entero $k$ tal que $\gcd(a,b)k = c$. Multiplicando $as+bt=\gcd(a,b)$ por $k$ que usted consigue $$a(sk) + b(tk) = \gcd(a,b)k = c.$$

Así que esto le da una solución, con $x=sk$ y $y=tk$.

Ahora supongamos que $ax_1 + by_1 = c$ es una solución, y $ax+by=c$ es alguna otra solución. Tomando la diferencia entre los dos, conseguimos $$(x_1-x) + b(y_1-y) = 0.$$ Por lo tanto, $(x_1-x) = b(y-y_1)$. Eso significa que $a$ divide a $b(y-y_1)$ y por tanto $\frac{a}{\gcd(a,b)}$ divide a $y-y_1$. Por lo tanto, y = y_1 + r\frac{a}{\gcd(a,b)}$para algún entero$r$. Sustituyendo en la ecuación$(x_1-x) = b(y-y_1)$da$$(x_1 - x) = rb\left(\frac{a}{\gcd(a,b)}\right)$$que los rendimientos de$$\gcd(a,b)un(x_1-x) = rba$$o$x = x_1 - r\frac{b}{\gcd(a,b)}$.

Por lo tanto, si $ax_1+by_1 = c$ es ninguna solución, entonces todas las soluciones son de la forma $$x = x_1 - r\frac{b}{\gcd(a,b)},\qquad y = y_1 + r\frac{a}{\gcd(a,b)}$$ exactamente como yunone dijo.

---

Para dar un ejemplo de esto en acción, supongamos que queremos encontrar todos los enteros soluciones a $$258x + 147y = 369.$$

En primer lugar, utilizamos el Algoritmo de Euclides para encontrar $\gcd(147,258)$; el paréntesis de la ecuación en el extremo derecho es cómo vamos a utilizar esta igualdad después de que se hacen con la computación. $$\begin{align*} 258 &= 147(1) + 111 &\quad&\mbox{(equivalentemente,, $111=258 - 147$)}\\ 147 &= 111(1) + 36&&\mbox{(equivalentemente,, $36 = 147 - 111$)}\\ 111 &= 36(3) + 3&&\mbox{(equivalentemente,, $3 = 111-3(36)$)}\\ 36 y= 3(12). \end{align*}$$ Por lo que $\gcd(147,258)=3$. Desde $3/369$, la ecuación tiene soluciones integrales.

A continuación, nos encontramos con una manera de escribir $3$ como una combinación lineal de $147$ y $258$, utilizando el algoritmo de Euclides cálculo anterior, y la igualdad en el extremo derecho. Tenemos: $$\begin{align*} 3 &= 111 - 3(36)\\ &= 111 - 3(147 - 111) = 4(111) - 3(147)\\ &= 4(258 - 147) - 3(147)\\ &= 4(258) -7(147). \end{align*}$$ Entonces, tomamos $258(4) + 147(-7)=3$, y multiplicar por $123$; ¿por qué $123$? Porque $3\times 123 = 369$. Obtenemos: $$258(492) + 147(-861) = 369.$$ Así que una solución es $x=492$ y $y=-861$. Todas las demás soluciones de la forma $$\begin{align*} x &= 492 - \frac{147r}{3} = 492 - 49r,\\ y &= -861 + \frac{258r}{3} =86r - 861, &\qquad&r\in\mathbb{Z}. \end{align*}$$ Usted puede reducir los constantes haciendo un simple cambio de variable. Por ejemplo, si dejamos a $r=t+10$, entonces $$\begin{align*} x &= 492 - 49(t+10) = 2 - 49t,\\ y &= 86(t+10) - 861 = 86t - 1,&\qquad&t\in\mathbb{Z}. \end{align*}$$

Answer 2

Como otros han mencionado que uno puede emplear el algoritmo de Euclides extendido. Se merece ser mejor conocido que esto es más fácil de realizar a través de la fila-la reducción en un matriz ampliada - de forma análoga a los métodos utilizados en álgebra lineal. Ver este extracto de uno de mis viejos sci.matemáticas puestos:

For example, to solve  mx + ny = gcd(x,y) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

                      in equation form   | in row form
                    ---------------------+------------
                    80 =   1(80) + 0(62) | 80   1   0
                    62 =   0(80) + 1(62) | 62   0   1
 row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
 row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
 row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
 row4 - 4 row5  ->   0 = -31(80) -40(62) |  0 -31  40

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
               |    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

       [  7 -9] [ 80  1  0]  =  [2   7  -9]
       [-31 40] [ 62  0  1]     [0 -31  40]

The 1st row is the particular  solution: 2 =   7(80) -  9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

       n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field, 
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form, 
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

Answer 3

Qué quieres decir $\gcd(a,b)$ divide a $c$? Si es así, usted puede dividir ambos lados de la ecuación para obtener $$\frac{a}{g}x+\frac{b}{g}y=\frac{c}{g}$$ donde $g=\gcd(a,b)$.

Pero desde $\gcd(a/g,b/g)=1$, se puede utilizar el algoritmo de Euclides extendido para encontrar una solución $(x_0,y_0)$ a de la ecuación $$\frac{a}{g}x+\frac{b}{g}y=1.$$

Una vez que tienes eso, la solución $(X,Y)=(\frac{c}{g}\cdot x_0,\frac{c}{g}\cdot y_0)$ es una solución a la ecuación original. Además, los valores $$x=X + \frac{b}{g} t\quad y=y - \frac{a}{g} t$$ dar todas las soluciones cuando $t$ rangos de más de $\mathbb{Z}$, creo.