Discrete math problem, need some help?

[Rickten]

I've been trying to figure this out for about an hour and a half.

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

Anybody have any idea how I can solve this.

 

[KatLei]

slowly go through all 500 numbers.........

 

[StormRider]

<< slowly go through all 500 numbers.........
>>



That's pretty much the way to do it!

Actually, you can speed it up a little. The only factors of 500 are the numbers 2 and 5. That means no even number is relatively prime with 500 -- so you can get rid of all the even numbers between 1 through 500. You can also get rid of any numbers that are multiples of 5's -- like 5, 10, 15, 20 etc.

The basic approach would be to "count" all the even numbers and all the numbers that are multiple of 5's (avoiding overlap) and subtract from 500.