Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer
$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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.