Question

Find the number of integers between 1 and 1000 , including 1 and 1000 , that are not divisible by any of $4,6,7,$ or $10.$

Short answer

There are 713 integers between 1 and 1000 that are not divisible by 4, 6, 7, or 10.

Step-by-step solution

Define the Sets

Define the sets of numbers divisible by each of 4, 6, 7, and 10 within the range 1 to 1000. Each set O_i will represent numbers divisible by respective number i.

Use the Inclusion-Exclusion Principle

The total number of integers divisible by any of these numbers is given by:$$|O_4\cup O_6\cup O_7\cup O_{10}|=|O_4|+|O_6|+|O_7|+|O_{10}|-|O_4\cap O_6|-|O_4\cap O_7|-|O_4\cap O_{10}|$$$$-|O_6\cap O_7|-|O_6\cap O_{10}|-|O_7\cap O_{10}|+|O_4\cap O_6\cap O_7|+|O_4\cap O_6\cap O_{10}|$$$$+|O_4\cap O_7\cap O_{10}|+|O_6\cap O_7\cap O_{10}|-|O_4\cap O_6\cap O_7\cap O_{10}|$$

Calculate Individual Contributions

Calculate each term using floor division by the divisors:$$|O_4|=\lfloor \frac{1000}{4}\rfloor =250$$$$|O_6|=\lfloor \frac{1000}{6}\rfloor =166$$$$|O_7|=\lfloor \frac{1000}{7}\rfloor =142$$$$|O_{10}|=\lfloor \frac{1000}{10}\rfloor =100$$

Calculate Pairwise Contributions

Compute the number of integers divisible by each pair using the Least Common Multiple (LCM):$$|O_4\cap O_6|=\lfloor \frac{1000}{12}\rfloor =83$$$$|O_4\cap O_7|=\lfloor \frac{1000}{28}\rfloor =35$$$$|O_4\cap O_{10}|=\lfloor \frac{1000}{20}\rfloor =50$$$$|O_6\cap O_7|=\lfloor \frac{1000}{42}\rfloor =23$$$$|O_6\cap O_{10}|=\lfloor \frac{1000}{30}\rfloor =33$$$$|O_7\cap O_{10}|=\lfloor \frac{1000}{70}\rfloor =14$$

Calculate Three-way Contributions

Determine three-way intersections using LCM:$$|O_4\cap O_6\cap O_7|=\lfloor \frac{1000}{84}\rfloor =11$$$$|O_4\cap O_6\cap O_{10}|=\lfloor \frac{1000}{60}\rfloor =16$$$$|O_4\cap O_7\cap O_{10}|=\lfloor \frac{1000}{140}\rfloor =7$$$$|O_6\cap O_7\cap O_{10}|=\lfloor \frac{1000}{210}\rfloor =4$$

Calculate Four-way Contribution

Calculate the contribution of the four-way intersection:$$|O_4\cap O_6\cap O_7\cap O_{10}|=\lfloor \frac{1000}{420}\rfloor =2$$

Compute the Total Using Inclusion-Exclusion

Substitute the values into the Inclusion-Exclusion formula:$$|O_4\cup O_6\cup O_7\cup O_{10}|=250+166+142+100$$$$-(83+35+50+23+33+14)+(11+16+7+4)-2=489-238+38-2=287$$

Find Integers Not Divisible by Any

Subtract the number from the total integers between 1 and 1000:$$1000-287=713$$

Conclusion

The number of integers between 1 and 1000 that are not divisible by any of 4, 6, 7, or 10 is 713.

Key concepts

Divisibility

Divisibility is a mathematical concept that helps us determine if a number can be evenly divided by another without leaving a remainder. For instance, a number is divisible by 4 if, when divided by 4, the result is an integer. This is crucial when solving problems like finding the count of numbers within a certain range that are divisible by 4, 6, 7, or 10.
To check divisibility for a number, there are some basic rules and methods:

• A number is divisible by 2 if its last digit is even.
• It is divisible by 3 if the sum of its digits is divisible by 3.
• For divisibility by 4, the last two digits of the number must form a number that's divisible by 4.
• A number is divisible by 9 if the sum of its digits is divisible by 9.
• It is divisible by 10 if it ends in 0.

Understanding divisibility empowers you to identify patterns, make calculations more efficiently, and solve problems involving multiple conditions.

Set Theory

Set theory is a fundamental aspect of mathematics where we deal with collections of elements or numbers. In our context, a set can represent numbers that satisfy a specific condition, such as being divisible by a particular number.
In the exercise given, each set $O_i$ was defined to include numbers divisible by a specific number $i$ (4, 6, 7, or 10). Set operations like unions and intersections help solve complex problems by combining or comparing these sets.

• The union of sets $O_4,O_6,O_7,$ and $O_{10}$, expressed as $|O_4\cup O_6\cup O_7\cup O_{10}|$, represents all numbers divisible by at least one of 4, 6, 7, or 10.
• Intersections, like $|O_4\cap O_6|$, represent numbers divisible by both of these numbers simultaneously.

Set theory is crucial in determining the overlap between different groups and can be efficiently utilized using the Inclusion-Exclusion Principle to handle complex situations involving multiple conditions.

Least Common Multiple

The Least Common Multiple (LCM) helps us find the smallest number that is a multiple of two or more numbers. For solving problems involving sets and inclusions, knowing the LCM is vital.
When using the Inclusion-Exclusion Principle, we need to calculate the intersection of sets, which involves finding numbers divisible by more than one number. This is where the LCM steps in.
The formula to find the LCM of two numbers $a$ and $b$ is:

• $$\text{LCM}(a,b)=\frac{|a\cdot b|}{gcd(a,b)}$$

Where $gcd(a,b)$ is the greatest common divisor of $a$ and $b$. For example, the LCM of 4 and 6, needed to find $|O_4\cap O_6|$, shows how many numbers are divisible by both 4 and 6 simultaneously.
Mastering the LCM is crucial for efficiently determining the size of intersections, a key step in solving set-based problems.