An integer n is called square free if does not have divisor of the form `k^2` where `k in {2,3 ... ,n}. Find the number of square free integers between 1 and 120

Options

A. 45
B. 60
C. 75
D. none of these

Answer

To find the number of square-free integers between 1 and 120, we will follow these steps:

### Step 1: Understand the Definition of Square-Free
An integer \( n \) is square-free if it is not divisible by any perfect square greater than 1. This means it should not have any divisors of the form \( k^2 \) where \( k \) is an integer greater than or equal to 2.

### Step 2: Identify the Relevant Perfect Squares
The perfect squares we need to consider that are less than or equal to 120 are:
- \( 2^2 = 4 \)
- \( 3^2 = 9 \)
- \( 5^2 = 25 \)
- \( 7^2 = 49 \)
- \( 11^2 = 121 \) (not included since it's greater than 120)

So, we will consider \( 4, 9, 25, \) and \( 49 \).

### Step 3: Use Inclusion-Exclusion Principle
Let \( A_p \) be the set of integers between 1 and 120 that are divisible by \( p^2 \). We need to find the size of the union of these sets for \( p = 2, 3, 5, 7 \).

### Step 4: Calculate Each Set Size
1. **For \( p = 2 \)**:
\[ |A_2| = \left\lfloor \frac{120}{4} \right\rfloor = 30 \]
2. **For \( p = 3 \)**:
\[ |A_3| = \left\lfloor \frac{120}{9} \right\rfloor = 13 \]
3. **For \( p = 5 \)**:
\[ |A_5| = \left\lfloor \frac{120}{25} \right\rfloor = 4 \]
4. **For \( p = 7 \)**:
\[ |A_7| = \left\lfloor \frac{120}{49} \right\rfloor = 2 \]

### Step 5: Calculate Intersections
Next, we calculate the intersections:
1. **For \( p = 2 \) and \( p = 3 \)**:
\[ |A_2 \cap A_3| = \left\lfloor \frac{120}{36} \right\rfloor = 3 \]
2. **For \( p = 2 \) and \( p = 5 \)**:
\[ |A_2 \cap A_5| = \left\lfloor \frac{120}{100} \right\rfloor = 1 \]
3. **For \( p = 2 \) and \( p = 7 \)**:
\[ |A_2 \cap A_7| = 0 \quad (\text{since } 4 \times 49 > 120) \]
4. **For \( p = 3 \) and \( p = 5 \)**:
\[ |A_3 \cap A_5| = 0 \quad (\text{since } 9 \times 25 > 120) \]
5. **For \( p = 3 \) and \( p = 7 \)**:
\[ |A_3 \cap A_7| = 0 \quad (\text{since } 9 \times 49 > 120) \]
6. **For \( p = 5 \) and \( p = 7 \)**:
\[ |A_5 \cap A_7| = 0 \quad (\text{since } 25 \times 49 > 120) \]

### Step 6: Apply Inclusion-Exclusion Formula
Using the inclusion-exclusion principle:
\[ |A_2 \cup A_3 \cup A_5 \cup A_7| = |A_2| + |A_3| + |A_5| + |A_7| - |A_2 \cap A_3| - |A_2 \cap A_5| - |A_2 \cap A_7| - |A_3 \cap A_5| - |A_3 \cap A_7| - |A_5 \cap A_7| \]
Substituting the values:
\[ |A_2 \cup A_3 \cup A_5 \cup A_7| = 30 + 13 + 4 + 2 - 3 - 1 - 0 - 0 - 0 - 0 = 45 \]

### Step 7: Calculate Square-Free Integers
Now, the number of square-free integers between 1 and 120 is:
\[ 120 - |A_2 \cup A_3 \cup A_5 \cup A_7| = 120 - 45 = 75 \]

### Final Answer
The number of square-free integers between 1 and 120 is **75**.

---