How to Calculate inverse of GCD? How to Calculate inverse of GCD ?
for example if we have GCD(a,b) = 7 
how do we determine the values of a,b .
note : a,b have given bound and the given result of the GCD is always a prime.
am actually trying to solve this problem and reversing GCD is the first Idea that came to my mind since a,b limit are <$10^7$
 A: You don't, because it doesn't have an inverse.  For example, there are infinitely many pairs $(a,b)$ with GCD$(a,b) = 1$ (these numbers are called "relatively prime" or "co-prime".)
EDIT: Perhaps more to the point, there are infinitely many pairs $(a,b)$ with GCD$(a,b) = 7$.  For example, $(7a, 7b)$ for every pair of co-prime integers $a$ and $b$.
A: In general, $\text{gcd}(a,b) = d$ (with $d \in \mathbb{Z}^+$) if and only if there exist $x,y \in \mathbb{Z}$ which are coprime and such that $ax+by=d$. So take any coprime $x,y \in \mathbb{Z}$, then we can calculate $a,b \in \mathbb{Z}$ such that $ax+by=d$ using the some kind of algorithm, such as the reverse-Euclidean algorithm. However, $a,b$ are highly non-unique.
If you just want a solution (rather than all solutions), given $d$ and a bound, then since $\left| a \right|$ and $\left| b \right|$ must be $\ge d$, you could just take $a=b=d$ (unless the bound is $<d$, in which case no solutions exist). This is the solution corresponding to $x=1, y=-1$ above.

Edit: Here's an algorithm for finding all $a,b$ with gcd $d$ given a bound $M>0$.
Let $S=\varnothing$. For each $-M \le a \le M$ and $-M \le b \le M$, calculate $\text{gcd}(a,b)$ (using, say, the Euclidean algorithm). If $\text{gcd}(a,b) = d$, append $(a,b)$ to $S$; if not, discard it. The resulting set $S$ contains all pairs $(a,b)$ within the given bound such that $\text{gcd}(a,b)=d$.
A: Hint $\rm\ (a,b) = c\!\iff\! c\:|\:a,b\,$ and $\rm\,(a/c,b/c) = 1.\:$ So $\rm\:(a,b) = c\!\iff\! a = c\,j,\ b = ck,\,$ $\rm\, (j,k)=1.\:$  Choosing $\rm\: j=k+1,\,\ k\in \Bbb N\:$ shows that there are infinitely many solutions.
