1
$\begingroup$

Let $a$ and $b$ be two numbers whose $\gcd{(a,b)}=ax+by$. How do I find $x$ and $y$?
I did it like this.

There is a $c$ which is a multiple of $\gcd{(a,b)}$ . Then $c=d \gcd{(a,b)}=d(ax+by)$ . Then I used this equation and the above most equation to find $x$ and $y$.

The thing is I have to write an algorithm and code it in c++ to find $x$ and $y$.

  • 2
    See [this answer](http://math.stackexchange.com/a/85841/242) for one convenient method of implementing the extended Euclidean algorithm.2012-11-12
  • 0
    Maybe look at [Wikipedia.](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) It has pseudo-code for a couple of approaches.2012-11-12

1 Answers 1