# 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 http://www.spoj.pl/problems/PGCD/ and reversing GCD is the first Idea that came to my mind since a,b limit are <10^7

-
I just noticed that you said "$a$ and $b$ have a given bound." Did you mean to give us a bound? –  Trevor Wilson Sep 5 '12 at 17:36
take any bound u would like on any prime number result I just want to know if there is a general systematic way of solving this . –  Loers Antario Sep 5 '12 at 18:05

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$.

-
actually I want to count all solutions –  Loers Antario Sep 5 '12 at 18:14
@LoersAntario: I'll edit my post. –  Clive Newstead Sep 5 '12 at 18:22
I added a link to the question hope that you can help me with that,, thanks in advance ^^ –  Loers Antario Sep 5 '12 at 18:25
@LoersAntario: I've added an algorithm. It's a brainless "try everything" algorithm that you can definitely improve upon. –  Clive Newstead Sep 5 '12 at 18:28
I thought of that but imagine doing that for a,b <10^7 that is (10^14) times .. and even best optimization for that is finding half of the table which will give (10^14)/2 which still alot to do –  Loers Antario Sep 5 '12 at 18:32

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$.

-
$gcd(21, 3*14) = 21$. Rather, you should have said that since there are infinitely many coprime integers and $gcd(a, b) = 1 \implies gcd(7a, 7b) = 7$ there are infinitely many pairs for any $n$. –  Karolis Juodelė Sep 5 '12 at 17:42
I mentioned that a,b have bounds –  Loers Antario Sep 5 '12 at 18:02
@Karolis: Thanks, I fixed it. –  Trevor Wilson Sep 5 '12 at 19:56
@Loers: Ok, but the GCD function is not one-to-one even when restricted to pairs $(a,b)$ satisfying the bound $a \le b < 10^7$ that you added. –  Trevor Wilson Sep 5 '12 at 20:00

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.

-