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

2 answers:

7 0

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.