Question

Total number of numbers lying in therange of 1331 and 3113 which are neither divisible by 2,3 or 5 (a) 477 (b) 594 (c) 653 (d) none of these

Short answer

Answer: 477

Step-by-step solution

Calculate total numbers in range

To calculate the total number of numbers in the given range, subtract the lower limit (1331) from the upper limit (3113) and add 1. Total numbers in range = (3113 - 1331) + 1 = 1783

Calculate numbers divisible by 2, 3, and 5

For each number (2, 3, and 5): Divide the upper limit (3113) by the number, take the floor of the result, and similarly divide the lower limit (1331) by the number, take the floor of the result, then subtract the two results and add 1 to find the number of multiples in the range. Number of multiples of 2: ⌊3113/2⌋ - ⌊1331/2⌋ + 1 = 1556 - 665 + 1 = 892 Number of multiples of 3: ⌊3113/3⌋ - ⌊1331/3⌋ + 1 = 1037 - 443 + 1 = 595 Number of multiples of 5: ⌊3113/5⌋ - ⌊1331/5⌋ + 1 = 622 - 266 + 1 = 357

Calculate numbers divisible by common multiples

We need to exclude the common multiples (2*3 = 6, 2*5 = 10, 3*5 = 15) to avoid double counting. Number of multiples of 6: ⌊3113/6⌋ - ⌊1331/6⌋ + 1 = 519 - 221 + 1 = 299 Number of multiples of 10: ⌊3113/10⌋ - ⌊1331/10⌋ + 1 = 311 - 133 + 1 = 179 Number of multiples of 15: ⌊3113/15⌋ - ⌊1331/15⌋ + 1 = 207 - 88 + 1 = 120

Calculate numbers divisible by all three numbers (2, 3, and 5)

Find the least common multiple of 2, 3, and 5 (LCM(2, 3, 5) = 30) and count the multiples. Number of multiples of 30: ⌊3113/30⌋ - ⌊1331/30⌋ + 1 = 103 - 44 + 1 = 60

Apply the inclusion-exclusion principle

Now using the inclusion-exclusion principle, subtract the numbers divisible by 2, 3, and 5 and then add back the numbers divisible by their common multiples, and lastly subtract the numbers divisible by all three numbers from the total numbers in range. Not divisible by 2, 3, or 5 = Total numbers - (Multiples of 2 + Multiples of 3 + Multiples of 5) + (Multiples of 6 + Multiples of 10 + Multiples of 15) - Multiples of 30 Not divisible by 2, 3, or 5 = 1783 - (892 + 595 + 357) + (299 + 179 + 120) - 60 = 1783 - 1844 + 598 - 60 = 477 So the total number of numbers lying in the range of 1331 and 3113 which are neither divisible by 2, 3, or 5 is 477. The correct answer is (a) 477.

Key concepts

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a critical concept in number theory and combinatorics, especially when it comes to calculating the number of elements in the union of several sets. Imagine you are trying to find out how many students in a class like apples or bananas. Some might like both, which complicates the count. This principle helps by ensuring we don't count those students twice.When dealing with multiple sets, such as numbers divisible by 2, 3, and 5, we first add the amounts in each individual set. Then we subtract those found in the intersection of every pair of sets because they were counted twice. But in doing this, we also remove those numbers which are in the intersection of all three sets thrice, so we add these back in. Simply put, we include the number of elements in each set, exclude the overlaps, and adjust for those counted in multiple overlaps. This is exactly what we did in the step by step solution to find how many numbers are not divisible by 2, 3, or 5.

Divisibility Rules

Divisibility rules provide us with simple techniques to determine whether a number is divisible by another without performing full division calculations. For instance, a number is divisible by 2 if its last digit is even, by 3 if the sum of its digits is divisible by 3, and so forth.

Quick Checks for Divisibility:

• 2: The number ends with 0, 2, 4, 6, or 8.
• 3: The sum of its digits is divisible by 3.
• 5: The number ends with 0 or 5.

These rules speed up the process when looking for numbers that are multiples of 2, 3, and 5 within a range, as this is precisely what we did in our exercise. Understanding these rules can save significant time on tests and in homework.

Least Common Multiple

The least common multiple (LCM) is the smallest non-zero common multiple of two or more numbers. It's essential when dealing with problems that require common time frames or intervals, such as finding when two events that repeat at different intervals will occur simultaneously.To find the LCM, we often prime factorize the numbers and take the highest powers of all primes that appear. The LCM of 2, 3, and 5, as we saw in the problem solution, is 30 because it's the smallest number that all three can divide into without a remainder. Calculating the LCM allows us to find multiples common to all the given numbers, which helps in solving problems that pertain to scheduling, repeating events, and in this case, applying the inclusion-exclusion principle in complicated divisibility contexts.