Question

Find the number of positive integers not exceeding 1000 that are not divisible by 3, 17, or 35.

Answer 1

Count the multiples of 3, 17, and 35 in the given range.

We have

1000 = 999 + 1 = 3•333 + 1

so there are 333 multiples of 3;

1000 = 986 + 14 = 17•58 + 14

so there are 58 multiples of 17; and

1000 = 980 + 20 = 35•28 + 20

so there are 28 multiples of 35.

Now count the multiples of 3 and 17, 3 and 35, and 17 and 35.

Since LCM(3, 17) = 51, we have

1000 = 969 + 31 = 51•19 + 31

so there are 19 multiples of 51.

LCM(3, 35) = 105, and

1000 = 945 + 55 = 105•9 + 55

so there are 9 multiples of 105.

LCM(17, 35) = 595, and

1000 = 595 + 405

so there is only 1 multiple of 595.

Also count the multiples of 3 and 17 and 35 together.

LCM(3, 17, 35) = 1785 which exceed 1000, so there are no more multiples.

Now use the inclusion/exclusion principle to count the multiples of 3 or 17 or 35 or any combination of them.

333 + 58 + 28 - (19 + 9 + 1) = 390

Then there are 1000 - 390 = 610 positive integers in the range that are not divisible by 3, 17, or 35.