Olympiad Maths Prep

Track / Stage 3 / 112 of 260 #112 of 2000

Problem 112

AMC 10/12, early questions
Number theory Difficulty 3.5 Find the answer

The number of positive integers less than 10001000 divisible by neither 55 nor 77 is:
(A) 688(B) 686(C) 684(D) 658(E) 630\text{(A) } 688 \quad \text{(B) } 686 \quad \text{(C) } 684 \quad \text{(D) } 658 \quad \text{(E) } 630

Official solution

The number of positive integers under 10001000 that are divisible by 55 is 9995=199\lfloor\frac{999}{5}\rfloor=199. The number of positive integers under 10001000 that are divisible by 77 is 10007=142\lfloor\frac{1000}{7}\rfloor=142. Adding them together, we get 341341. However, we have over counted the numbers which are divisible by 3535. There are 99935=28\lfloor\frac{999}{35}\rfloor=28 of these. So, the number of positive integers divisible be 77 or 55 under 10001000 is 34128=313341-28=313. We can conclude that the number of positive integers divisible by neither 55 or 77 is 999313=686999-313=686 or answer choice B\fbox{B}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.