Positive solutions of $893x - 2432y = 19$

Question

I am trying to find a solution to $893x - 2432y = 19$ where both $x$ and $y$ are positive integers. When I apply the extended Euclidean algorithm I get a solution where both integers are negative $(-49,-18)$, but in my book the solutions are described as $(79,29)$.

My first step of the algorithm looks like $r=-b - 2a$, where $b = -2432$ and $a = 893$, and then I move on from there, with the initial $r = 646$.

Answer 1

The gcd of $a=893$ and $b=-2432$ is $d=19$. Define $u = a/d = 47$ and $v = b/d = -128$.

Then $(−49-v,−18+u) = (79,29)$ is also a solution. Check it.

Moreover, $(−49+kv,−18-ku)$ is a solution for any integer $k$.

Further still, if you have any solution $(x_0,y_0)$ of a linear Diophantine equation $ax+by=c$, then $(x_0+kv,y_0-ku)$ is also a solution for any integer $k$. Here $u = a/d$, $v=b/d$, and $d = \text{gcd}(a,b)$.

For a proof, see: http://en.wikipedia.org/wiki/Diophantine_equation#Linear_Diophantine_equations

So to get a positive solution, you just need to choose an appropriate $k$. Choosing $k=-1$ did the trick in your case.

Answer 2

Once you have one solution, you have them all: If there are $x_0, y_0$ with $$47x_0 -130y_0=1 $$ You know this has a solution since $gcd(47,130)=1$, then the Euclidean algorithm gives you a constructive solution.

(our equation after dividing through by the common factor $19$) $$47(x_0 +k130)-130(y_0 + k47)= 47x_0+k(47)(130)-130y_0 -k(130)(47)=47x_0+130y_0 =1 $$ , where k is an integer.

Answer 3

$$ 893x−2432y=19 $$ is of type $a X + b Y = c$. Then $d = \gcd(a,b) = \gcd(893,-2432) = 19$ and $d=19 \vert c = 19$, so we have infinite many solutions.

We set $m=c/d=1$ and use the extended Euclidean algorithm to solve $sa + tb = d$, which gives $s = -49$, $t = -18$ and we get $x_0 = ms = -49$, $y_0 = mt = -18$.

The general solution is derived from the solutions of the reduced Diophantine equation $a' = a/d = 893/19 = 47$, $b' = b/d = -2432/19 = -128$, $c' = c/d = 1$: $$ (x_k, y_k) = (x_0 + b' k, y_0 - a' k) = (-49 -128 k, -18 - 47 k) \quad (k \in \mathbb{Z}) $$ Thus $$ (x, y) \in \{ (-49,-18), (-177,-65), (79,29), \ldots \} $$ Here is a visualisation of part of the solution space:

The upper right point is for $k = -5$, the lower left is for $k = 4$.