Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
add comment

3 Answers 3

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|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
show 4 more comments

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|improve this answer
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$. –  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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.