2
$\begingroup$

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$

  • 0
    I just noticed that you said "$a$ and $b$ have a given bound." Did you mean to give us a bound?2012-09-05
  • 0
    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 .2012-09-05

3 Answers 3

1

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.

6

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

  • 3
    $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$.2012-09-05
  • 0
    I mentioned that a,b have bounds2012-09-05
  • 0
    @Karolis: Thanks, I fixed it.2012-09-05
  • 0
    @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.2012-09-05
2

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

  • 0
    actually I want to count all solutions2012-09-05
  • 0
    @LoersAntario: I'll edit my post.2012-09-05
  • 0
    I added a link to the question hope that you can help me with that,, thanks in advance ^^2012-09-05
  • 0
    @LoersAntario: I've added an algorithm. It's a brainless "try everything" algorithm that you can definitely improve upon.2012-09-05
  • 0
    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 do2012-09-05
  • 0
    @LoersAntario: It's a lot, yes, but it's not *impossible*. You could cut it down by a factor of $d$ by finding coprime pairs $(i,j)$ with $i,j \le M/d$ and then taking $a=di,b=dj$. You could probably cut it down even further by considering primes $\le M/d$ and instead of *searching* for coprime pairs, *constructing* them by considering prime factorisations $-$ this would take far fewer operations (at least, for large values of $M$). These are just a few ideas.2012-09-05
  • 0
    You don't even need to consider prime factorisations. You can just write down all of the answers: for each $k$, set $a = kd$ and then set $b = md$ for each $m$ coprime to $k$. (There's some subtlety in generating a list of numbers coprime to some other number, perhaps, but I bet it's both easy and fast if you think about it).2012-09-05
  • 0
    @BenMillwood: How do you always manage to find me? :P2012-09-05
  • 0
    I swear this time it was a coincidence! >_>2012-09-05