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

Counting (Again)

  1. Apr 1, 2004 #1
    Having a lot of trouble with this problem as well:

    How many integers less than 500 are relatively prime to 500?

    I know that when two numbers are relatively prime, that means that the greatest common divisor of those two numbers is 1. But I can't figure out a formula that uses sets in order to calculate this.

    If someone could point me in the right direction with this, then it would be greatly appreciated.
  2. jcsd
  3. Apr 1, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    A number is relatively prime with 500 iff it is not divisibel by 5 or 2. You can count the number that are divisible by two, those divislbe by 5, but you've over counted those divisible by 10. this is the inclusion exclusion principle. if you like probability it is the same as saying P(AuB) = P(A) + P(B) - P(AnB)
  4. Apr 1, 2004 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Also, there's a function for this very purpose; the Euler-totient (aka Euler-phi or simply phi) function. The answer you're looking for would then be φ(500).

    Information on this function can be found at http://mathworld.wolfram.com/TotientFunction.html
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook