20030731, 18:18  #1 
Sep 2002
2^{2}·3·5 Posts 
Relatively Prime
I need a fast function which determines whether 3 numbers are relatively prime. I'm thinking of doing 3 GCF's, but that seems slow.

20030801, 02:27  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
16024_{8} Posts 
Just 2 GCDs, right? gcd ( gcd ( A, B ), C )
I've seen library GCDs that took more than two arguments, but the question would be whether anyone's coded a really fast one. [Edit: Oh, swiss! I just realized that I got it backward, but find that hyh1048576 has already pointed that out, so I can't save face by sneaking in a silent edit. Ya know, as ya get older yer subconscious gets wiser but also gets slower.] 
20030801, 05:46  #3  
Jun 2003
2^{6} Posts 
Quote:
If gcd(A,B)>1, they are not relatively primes. So when A,B,C are relatively primes, gcd(A,B)=1, so gcd ( gcd ( A, B ), C )=gcd(1,C) must be equal to 1 ......That means it's useless in the determination :( And for example, A=p1p2, B=p3p4, C=p2p3, p1,p2,p3,p4 are primes.The two gcd are both equal to 1, but they are not relatively primes. My method is A,B,C are relatively primes iff gcd(A,B) and gcd(AB,C) are both equal to 1 :) 

20030801, 15:37  #4 
Sep 2002
2^{2}·3·5 Posts 
Thanks for your help, I'll see how it goes.

20030801, 16:35  #5 
∂^{2}ω=0
Sep 2002
República de California
2×3×11×149 Posts 
There is no reason one needs to restrict the GCD to 2 inputs, i.e. N numbers x_1, ..., x_N are relatively prime iff GCD(x_1, ..., x_N) = 1. Of course if the GCD implementation one is using only allows for 2 inputs, one would have to do N1 pairwise GCDs, but that has the advantage that if any one of these gives a result > 1, one can stop right there.

20030801, 17:33  #6 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
it seems to me that there should be some way to short circuit this to just look for relatively prime or not, instead of finding out the greatest common divisor.
doing GCD's seems like factoring a number to see if it is prime .. Any thoughts? 
20030801, 18:13  #7 
Feb 2003
251_{8} Posts 
Ernst 
Why don't we need N choose 2 gcd's. Or are we not talking about pairwise relatively prime numbers? 
20030801, 23:53  #8  
∂^{2}ω=0
Sep 2002
República de California
2·3·11·149 Posts 
Quote:
Quote:
Quote:
The Gnu MP package has fast GCD algorithms of various kinds (and both regular and "extended" GCDs  the latter are handy for finding modular inverses). 

20030802, 02:00  #9 
Cranksta Rap Ayatollah
Jul 2003
1010000001_{2} Posts 
Forest. Trees.
I'm not talking about the algorithmic details, I know that finding the GCD and factoring are very different, I meant that finding the GCD in the context of testing integers to be RP is akin to factoring a number to prove primality. The definition of a prime number is a number that has only itself and 1 as factors, but that doesn't mean you have to check every number between 1 and p and see if it is a factor, or even factor p to find out it is prime .. what I'm saying is that if you find GCD(36,45) you get 9, but if you just wanted to know if 36 and 45 are relatively prime, getting 9 is extraneous information .. all you need is one bit of information,where RP(36,45) = false Perhaps the algorithms for GCD are so fast that this isn't a practical issue, but it still might provide some interest. (Finding a polynomialtime primality proving algorithm is of interest, despite the fact that there are more optimized algorithms out there, again, I'm speaking conceptually) 
20030802, 02:57  #10 
Feb 2003
13^{2} Posts 
IIRC the Euclidean Algorithm for computing GCD is O(n*lg n) in the size of the input, so you are not likely to get much faster than that.

20030802, 04:41  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
Quote:
The situation for relatively prime numbers is not analogous. For a given number, the property of being relatively prime to another number is a less fundamental property than the property of being prime itself. So AFAIK no one has found any method of distinguishing relatively prime numbers from relatively nonprime numbers that is simpler than calculating the GCD and comparing that to 1. Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!  dabaichi  News  571  20201026 11:02 
Twin Prime Days, Prime Day Clusters  cuBerBruce  Puzzles  3  20141201 18:15 
disk died, prime work lost forever? where to put prime? on SSD or HDD?  emily  PrimeNet  3  20130301 05:49 
Prime Cullen Prime, Rest in Peace  hhh  Prime Cullen Prime  4  20070921 16:34 
The 40th known Mersenne prime, 2209960111 is not PRIME!  illmanq  Miscellaneous Math  33  20040919 05:02 