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

  • 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
    I swear this time it was a coincidence! >_>2012-09-05