Thread: Relatively Prime View Single Post
2003-08-02, 04:41   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

Quote:
 Originally Posted by TravisT 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 ..
That's only because it is possible to distinguish primes from composites by methods which do not involve factoring.

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:
 Originally Posted by TravisT 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
... and you get that one bit of information by comparing the 9 to 1, so the 9 is not completely extraneous.