Counting (Again)

  • Thread starter Caldus
  • Start date
  • #1
106
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
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)
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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
 

Related Threads on Counting (Again)

Replies
3
Views
2K
  • Last Post
2
Replies
29
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
6
Views
2K
Replies
5
Views
725
Top