How many integers less than 1000 have no factors (other than 1) in common with 1000?

There are 999 integers less than 1000. Immediately, we can eliminate all of the even numbers among those, since we know they share the factor 2 with 1000. This gets rid of 499 integers, leaving us with 500 odd integers. To make our next elimination, we'll have to take a look at 1000 again.

1000's prime factorization is 2³ · 5³, which means that our final filter on the remaining integers should be to eliminate every integer divisible by 5. Any whole number ending in a 0 or a 5 is divisible by 5, but since we've eliminated all even numbers from our list, we've split the amount of those divisible numbers in half. It may be a bit hard to visualize this elimination, so let's figure out how many integers would get eliminated in a bit of a simpler setting first:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Usually we'd be eliminating 4 numbers from this sequence, but in a sequence with all the even numbers eliminated:

1 3 5 7 9 11 13 15 19

We only eliminate half that amoung, or 2.

Here, we'd usually be eliminating 100 of the numbers from our list of 500 (or 1/5 of the list, since we eliminate a number every 5 integers), but here, we're only eliminating half of that amount, or 50. This leaves us with 500 - 50 = 450 integers with no factors in common with 1000.

Note: We also sometimes refer to numbers with this kind of relationship as coprime or relatively prime.

168 numbers beginning with the

2, 3, 7, 11,13 and ending with the 983, 991 and 997