Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of positive divisiors with gcd condition

  1. Oct 25, 2012 #1
    Let n be a positive integer and a be a positive divisor of n. Is there any general formula to find the number of positive divisors b of n such that (a,b)=1 ?.
  2. jcsd
  3. Oct 25, 2012 #2
    No. That would be a formula to factor a number but there isn't any.
  4. Oct 25, 2012 #3
    Yes. There is a general formula. First, you should understand the well known formula d(n)=∏(ri+1) for the number of divisors of n, where n=∏piri is the prime factorization of n. See for example wikipedia or OEIS.

    In your case, it is the same product as for d(n), except you dont run it over all primes, but exclude the primes dividing a.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook