Find algorithm for equation

Question

I need algorithm for this problem: Find $x,y$ from the equation: $c=ax+by$, where a,b,c are given natural numbers and $(a,b)=1$ (the greatest common factor of $a$ and $b$ is $1$).

Answer 1

You have to first solve $ax+by=1$ since $a$ and $b$ are coprime. This is done using the Extended Euclidean Algorithm.

You will get a solution $(x_0,y_0)$.All other solutions are $(x_0+kb,y_0-ka),\ k\in\mathbf Z $. Now the solutions for the original equation is obtained multiplying the former results by $c$.

As an example, the equation $5x+2y=1$ has a trivial solution (needless to deploy the E.E.A. here): $(x_0,y_0)=(1,-2)$ and the general solution has the form: $$(x,y)=(1+2k,-2-5k),\ k\in\mathbf. Z$$

Then the equation $5x+2y=13$ has the solution $(x_0,y_0)=(13,-26)$ and the general solution has the form: $$(x,y)=(13+2k,-26-5k),\ k\in\mathbf. Z$$

Answer 2

Have you heard of Euclid's algorithm?

http://en.wikipedia.org/wiki/Euclidean_algorithm

Answer 3

Consider this elementary transform of the equation:

$$c=ax+by=ax-bx+bx+by=(a-b)x+b(x+y)=a'x'+b'y',$$ where $a'::=a-b,b'::=b,x'::=x,y'::=x+y$.

The equation keeps the same form, but the coefficients have changed.

Now do this repatedly in such a way that you always subtract the small coefficient from the large one.

In the end the small coefficient will be $0$ and the equation will reduce to $$c=a^{(i)}x^{(i)},$$which is immediately solved. Then you backtrack to obtain $x,y$ (using $x=x',y=y'-x'$).

Example: $$7x+3y=15 $$ $$4x'+3y'=15$$ $$x''+3y''=15$$ $$x'''+2y'''=15$$ $$x''''+y''''=15$$ $$x'''''+0y'''''=15$$ Backtracing, the solution is (with $y'''''$ being indeterminate, let $k$): $$x'''''=15,y'''''=k$$ $$x''''=15-k,y''''=k$$ $$x'''=15-2k,y'''=k$$ $$x''=15-3k,y''=k$$ $$x'=15-3k,y'=4k-15$$ $$x=15-3k,y=7k-30$$

This is indeed an algorithm as every step is clearly defined and uses elementary operations. It is also guaranteed to terminate in a finite number of steps because the coefficients decrease on every step.

This forms the basis of the well-known extended Euclidean algorithm, which adds two improvements:

• the backtracking can be done at the same time as the forward steps by clever bookkeeping,
• the subtraction $a=a-b$ can be replaced by a division remainder $a=a\bmod b$ to accelerate the decay.

---

UPDATE: case $5x+2y=13$ $$5x+2y=13$$ $$3x'+2y'=13$$ $$x''+2y''=13$$ $$x'''+y'''=13$$ $$x''''+0y''''=13$$ $$x''''=13,y''''=k$$ $$x'''=13-k,y'''=k$$ $$x''=13-2k,y''=k$$ $$x'=13-2k,y'=3k-13$$ $$x=13-2k,y=5k-26$$